链表

• 大内存空间分配

由于数组空间的连续性，如果要为数组分配 500M 的空间，这 500M 的空间必须是连续的，未使用的，所以在内存空间的分配上数组的要求会比较严格，如果内存碎片太多，分配连续的大空间很可能导致失败。而链表由于是非连续的，所以这种情况下选择链表更合适。

• 元素频繁删除和插入

如果涉及到元素的频繁删除和插入，用链表就会高效很多，对于数组来说，如果要在元素间插入一个元素，需要把其余元素一个个往后移（如图示），以为新元素腾空间（同理，如果是删除则需要把被删除元素之后的元素一个个往前移），效率上无疑是比较低的。

(在 1，2 间插入 5，需要把2，3，4 同时往后移一位)

而链表的插入删除相对来说就比较简单了，修改指针位置即可，其他元素无需做任何移动操作

如果数据以查为主，很少涉及到增和删，选择数组，如果数据涉及到频繁的插入和删除，或元素所需分配空间过大，倾向于选择链表。

说了这么多理论，相信读者对数组和链表的区别应该有了更深刻地认识了，尤其是 程序局部性原理，是不是开了不少眼界^_，如果面试中问到数组和链表的区别能回答到程序局部性原理，会是一个非常大的亮点！