数组和链表的区别？「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。

今天来说下两种最基本的数据结构——数组和链表，它们无处不在！下面我们来一一介绍下他们，首先了解下内存分配的！

内存的工作原理

假设你去看演出，需要将东西寄存。寄存处有一个柜子，柜子有很多抽屉。

每个抽屉可放一样东西，你有两样东西要寄存，因此要了两个抽屉。

现在你可以去看演出了！这大致就是计算机内存的工作原理。计算机就像是很多抽屉的集合体，每个抽屉都有地址。
在这里插入图片描述
fe0ffeeb是一个内存单元的地址。需要将数据存储到内存时，你请求计算机提供存储空间，计算机给你一个存储地址。需要存储多项数据时，有两种基本方式——数组和链表。但它们并非都适用于所有的情形，因此知道它们的差别很重要。接下来介绍数组和链表以及它们的优缺点。

数组

数组怎么在储存在内存中呢？举个例子，我们将待办事项存储在数组中。使用数组意味着所有待办事项在内存中都是相连的（紧靠在一起的）。

现在假设你要添加第四个待办事项，但后面的那个抽屉放着别人的东西！
在这里插入图片描述

这就像你与朋友（假如3人）去看电影，找到地方就坐后又来了一位朋友，但原来坐的地方没有空位置（你们4人想坐一起），只得再找一个可坐下所有人的地方。在这种情况下，你需要请求计算机重新分配一块可容纳4个位置的内存。如果又来了一位朋友，而当前坐的地方也没有空位，你们就得再次转移！真是太麻烦了。同样，在数组中添加新元素也可能很麻烦。如果没有了空间，就得移到内存的其他地方，因此添加新元素的速度会很慢。假如在数组中间插入一个待办事项（买茶叶）
在这里插入图片描述
如果没有足够的空间，可能还得将整个数组复制到其他地方！同理！要删除待办事项（吃午饭），删除后，必须将后面的元素都向前移，也是很费时间的！那么数组有没有优势的地方，优势在哪里呢？看下图5个元素的数组：
在这里插入图片描述

只需执行简单的数学运算就知道，需要随机地读取元素时，数组的效率很高，因为可迅速找到数组的任何元素。

链表

链表中的元素可存储在内存的任何地方。链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。
在这里插入图片描述
这犹如寻宝游戏。你前往第一个地址，那里有一张纸条写着“下一个元素的地址为123”。因此，你前往地址123，那里又有一张纸条，写着“下一个元素的地址为847”，以此类推。在链表中添加元素很容易：只需将其放入内存，并将其地址存储到前一个元素中。使用链表时，根本就不需要移动元素。这还可避免另一个问题。假设你与五位朋友去看一部很火的电影。你们六人想坐在一起，但看电影的人较多，没有六个在一起的座位。使用数组时有时就会遇到这样的情况。假设你要为数组分配10 000个位置，内存中有10 000个位置，但不都靠在一起。在这种情况下，你将无法为该数组分配内存！链表相当于说“我们分开来坐”，因此，只要有足够的内存空间，就能为链表分配内存。

那么链表有没有缺点？

当读取链的最后一个元素时，你不能直接读取，因为你不知道它所处的地址，必须先访问元素#1，从中获取元素#2的地址，再访问元素#2并从中获取元素#3的地址，以此类推，直到访问最后一个元素。需要同时读取所有元素时，链表的效率很高：你读取第一个元素，根据其中的地址再读取第二个元素，以此类推。但如果你需要跳跃，链表的效率真的很低。
在这里插入图片描述
使用链表时，插入元素很简单，只需修改它前面的那个元素指向的地址。而使用数组时，则必须将后面的元素都向后移。因此，当需要在中间插入元素时，链表是更好的选择。假如在链表中删除某个元素，只需修改前一个元素指向的地址即可。而使用数组时，删除元素后，必须将后面的元素都向前移。

总结

下面是数组和链表操作的运行时间：
在这里插入图片描述
数组和链表哪个用得更多呢？显然要看情况。但数组用得很多，因为它支持随机访问。有两种访问方式：随机访问和顺序访问。顺序访问意味着从第一个元素开始逐个地读取元素。链表只能顺序访问：要读取链表的第十个元素，得先读取前九个元素，并沿链接找到第十个元素。随机访问意味着可直接跳到第十个元素。本书经常说数组的读取速度更快，这是因为它们支持随机访问。很多情况都要求能够随机访问，因此数组用得很多!