所谓“既生瑜何生亮”，有了链表还要数组干嘛？

既然数组和链表都是数据存储的一种手段，所谓“既生瑜何生亮”，有了"链表"还用"数组"干嘛？有了这个疑问，小编在此主要跟大家分享一下数组和链表两种内存组织类型的异同，帮助大家正确理解好这两种数据结构并合理应用。

一、数组和链表的简介

1. 数组

数组---就是一些列具有相同类型的数据的集合，这些数据在内存中依次挨着存放，彼此之间没有缝隙。简单来说，就是一种有序、连续且有着相同元素的存储结构。一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同，数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。

特点：

相同的元素类型；

依次连续顺序存放；

通过下标可以直接访问。

优点：存取速度快

缺点：

1.需要一个连续的很大的内存（因为数组具有连续性，假设int[30000]arry 即需要分配连续的30000个空间，可能不存在)

2.插入和删除元素的效率低（当删除数组当中的一个元素时，因为数组具有连续性，所以需要后面的元素全部前移一位。同理：插入一位元素时，需要后面的全部后移一位）

2.  链表

链表---由n个节点离散分配，彼此通过指针相连，每个节点只有一个前驱节点和后驱节点，首节点没有前驱节点，尾节点没有后驱节点。简单来说，就是一种不一定有序、不一定连续、不一定相同元素的存储结构。

特点：

元素不一定相同，只需要存在链接信息；

不需要内存连续；

非下标访问，通过链接信息遍历。

优点：

插入删除元素效率高，不需要一个连续的很大内存（链表中一个节点分为两部分，一部分用于存放内容，另一部分用于存放下一节点的地址，指向下一空间，所以不需要连续空间）

缺点：复杂

专业术语：

首节点：存放第一个有效数据的节点

尾节点：存放最后一个有效数据的节点

头节点：1：头结点的数据类型和首节点的类型是一模一样的 2：头节点是首节点前面的节点 3：头节点并不存放有效数据 4：设置头结点的目的是为了方便对链表的操作

头指针：存放头节点的指针变量

二、数组和链表的异同

1.  相同点

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

2.  不相同点

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

1)动态扩容

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

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

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

2)更好的利用Cache

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

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

3)访问节点方式

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

4)节约内存

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

三、一个讨论点分析

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

1.  情况1   

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

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

情况1总结：

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

2.  情况2   

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

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

情况2总结：

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

四、小结

看完本文的小伙伴应该对数组和链表有了更加清晰的认识，其实这些对比对于以后大家进行一些代码上的优化和设计是非常有帮助的。

点赞 关注 走一波，精彩内容不错过。