C语言有了\"链表\"还用\"数组\"干嘛?被问懵了......

1、聊一聊

本文主要跟大家分享一下数组和链表两种内存组织类型的异同，帮助大家正确理解好这两种数据结构并合理应用。

2、数组和链表的简介

1. 数组

数组---一种有序、连续且有着相同元素的存储结构。

特点：

•  相同的元素类型；
•  依次连续顺序存放；
•  通过下标可以直接访问。

2.  链表

链表---一种不一定有序、不一定连续、不一定相同元素的存储结构。

特点：

•  元素不一定相同，只需要存在链接信息；
•  不需要内存连续；
•  非下标访问，通过链接信息遍历。

3、数组和链表的异同

1.  相同点

相同点比较少，两者都是内存数据的一种组织方式，数组通过连续相同元素分配的特点来进行节点的访问，而对于链表是通过链接关系(一般通过指针链接)来进行索引访问。(下面所有的数组项和链表项都统一叫节点)

2.  不相同点

相同点相对比较少，不然其中一方必定替代另外一方，所以这里重点谈谈不同点:

1)动态扩容

通过前面两者的特点我们知道，数组属于连续分配，一般都在定义的时候分配给定的大小，而链表却可以实现动态的节点插入和移除，这样对于一些内存利用空间多变的情况，使用链表会带来更多的灵活度和内存的利用率。如下图所示:

如果分配的数组之前仅仅只有7个节点空间，当需要插入7节点的时候，需要把所有的内存copy到一个更大的内存空间，然后再把7插入。

对于链表其实就不存在扩大容量的问题，如果空间足够且指针能够索引到，便可以"无限"扩充。

2)更好的利用Cache

在含有Cache的系统中，由于CPU的访问速度相对普通内存而言不在一个数量等级，为了不拖累CPU都会在其中间通过Cache来作为一个缓冲，可以大大提高CPU访问主存的速度。

那么数组作为连续的内存组织方式，更容易被同时加载到Cache中从而提高CPU对内存数据的命中，并提高运算速度和效率。

3)访问节点方式

这样就很明显了，数组通过下标可以直接访问到对应的节点，而链表需要通过头指针不断的进行遍历从而找到对应的节点。例如:我们想直接访问数组的第三个节点，直接通过Array[2]即可，而对于链表则通过头指针，不断的找下一个节点最终找到第三个节点的位置，这样链表的时间复杂度就比数组大。

4)节约内存

对于数组由于其固定的顺序存储格式特点所以直接可以通过下标访问，然而对于链表的不连续性，其每个节点必须要存储其前驱或者后继的链接信息，这样就需要使用额外的内存空间进行信息保存，当节点比较多时可是一笔不小的内存开支。

4、一个讨论点分析

一问到数组和链表的应用，大家一般都会想到一句话:"查询修改用数组，插入删除用链表"，那么bug菌就在这里跟大家分析分析这句话:

1.  情况1   

上图数组在第四个元素后面插入一个节点，这样需要把4,5,6节点依次向后面移动一个节点，然后把新的元素加入。

上图链表中在4个位置插入一个新节点，首先需要通过遍历知道第四个节点，然后直接通过改变指针进行新节点的链表插入。

情况1总结：

• 对于该情况下数组和链表的复杂度相差不大，数组需要后移新插入点后的所有节点，然后再插入新节点，而对于链表需要首先遍历找到对应的节点，然后进行插入。

2.  情况2   

上图数组在数据1后面插入一个新的节点，首先数组需要遍历知道数据1，然后移动3,5,6数据节点，并插入新节点。

上图数组在数据1后面插入一个新的节点，首先链表需要遍历知道数据1，然后直接插入新节点。

情况2总结：

•  所以对于该情况链表的复杂度比数组要低，所以具体情况具体分析，比如直接在头结点插入新节点的情况，链表比数组更优。仅仅只是查找和修改，其两者相差不大，不过数组更加方便。