数据结构之 “数组与链表”

作者:做好一个程序猿

数组

什么是数组？

数组是有限个相同类型的变量所组成的有序集合，数组中的每一个变量被称为元素。数组是最为简单、最为常用的数据结 构。

以整型数组为例，数组的存储形式如下图所示。

正如军队里的士兵存在编号一样，数组中的每一个元素也有着自己的下标，只不过这个下标从0开始，一直到数组长度-1。

数组的另一个特点，是在内存中顺序存储 ，因此可以很好地实现逻辑上的顺序表 。

数组在内存中的顺序存储，具体是什么样子呢？

内存是由一个个连续的内存单元组成的，每一个内存单元都有自己的地址。在这些内存单元中，有些被其他数据占用了，有些是空闲的。

数组中的每一个元素，都存储在小小的内存单元中，并且元素之间紧密排列，既不能打乱元素的存储顺序，也不能跳过某个存储单元进行存储。

在上图中，橙色的格子代表空闲的存储单元，灰色的格子代表已占用的存储单元，而红色的连续格子代表数组在内存中的位置。

不同类型的数组，每个元素所占的字节个数也不同，本图只是一个简单 的示意图。

那么，。

数组的基本操作

1. 读取元素

对于数组来说，读取元素是最简单的操作。由于数组在内存中顺序存储，所以只要给出一个数组下标，就可以读取到对应的数组元素。

假设有一个名称为array的数组，我们要读取数组下标为3的元素，就写作array[3]；读取数组下标为5的元素，就写作array[5]。需要注意的是，输入的下标必须在数组的长度范围之内，否则会出现数组越界。

像这种根据下标读取元素的方式叫作随机读取 。简单的代码示例如下：

2. 更新元素

要把数组中某一个元素的值替换为一个新值，也是非常简单的操作。直 接利用数组下标，就可以把新值赋给该元素。

简单的代码示例如下：

数组读取元素和更新元素的时间复杂度都是O(1) 。

3. 插入元素

在介绍插入数组元素的操作之前，我们需要补充一个概念，那就是数组

的实际元素数量有可能小于数组的长度，例如下面的情形。

因此，插入数组元素的操作存在3种情况。

尾部插入

中间插入

超范围插入

尾部插入，是最简单的情况，直接把插入的元素放在数组尾部的空闲位置即可，等同于更新元素的操作。

中间插入，稍微复杂一些。由于数组的每一个元素都有其固定下标，所以不得不首先把插入位置及后面的元素向后移动，腾出地方，再把要插入的元素放到对应的数组位置上。

4. 删除元素

数组的删除操作和插入操作的过程相反，如果删除的元素位于数组中间，其后的元素都需要向前挪动1位。

数组的插入和删除操作，时间复杂度分别是多少？

先说说插入操作，数组扩容的时间复杂度是O(n)，插入并移动元素的时间复杂度也是O(n)，综合起

来插入操作的时间复杂度是O(n) 。

至于删除操作，只涉及元素的移动，时间复杂度也是O(n) 。

对于删除操作，其实还存在一种取巧的方式，前提是数组元素没有顺序要求。

例如下图所示，需要删除的是数组中的元素2，可以把最后一个元素复制到元素2所在的位置，然后再删除掉最后一个元素。

这样一来，无须进行大量的元素移动，时间复杂度降低为O(1)。当然，这种方式只作参考，并不是删除元素时主流的操作方式。

数组的优势和劣势

数组这种数据结构有什么优势和劣势呢？

数组拥有非常高效的随机访问能力，只要给出下标，就可以用常量时间找到对应元素。有一种高效查找元素的算法叫作二分查找，就是利用了数组的这个优势。

至于数组的劣势，体现在插入和删除

元素方面。由于数组元素连续紧密地存储在内存中，插入、删除元素都会导致大量元素被迫移动，影响效率。总的来说，数组所适合的是读操作多、写操作少 的场景，下一节我们要讲解的链表则恰恰相反。

链表

单向链表的结构。

链表（linked list）是一种在物理上非连续、非顺序的数据结构，由若干节点（node）所组成。

单向 链表的每一个节点又包含两部分，一部分是存放数据的变量data，

另一部分是指向下一个节点的指针next。

链表的第1个节点被称为头节点，最后1个节点被称为尾节点，尾节点的next指针指向空。

与数组按照下标来随机寻找元素不同，对于链表的其中一个节点A，我们只能根据节点A的next指针来找到该节点的下一个节点B，再根据节点B的next指针找到下一个节点C……

那么，通过链表的一个节点，如何能快速找到它的前一个节点呢？要想让每个节点都能回溯到它的前置节点，我们可以使用双向链表 。

什么是双向链表？

双向链表比单向链表稍微复杂一些，它的每一个节点除了拥有data和next指针，还拥有指向前置节点的prev 指针。

接下来我们看一看链表的存储方式。

如果说数组在内存中的存储方式是顺序存储，那么链表在内存中的存储方式则是随机存储 。

什么叫随机存储呢？

上一节我们讲解了数组的内存分配方式，数组在内存中占用了连续完整的存储空间。而链表则采用了见缝插针的方式，链表的每一个节点分布在内存的不同位置，依靠next指针关联起来。这样可以灵活有效地利用零散的碎片空间。

让我们看一看下面两张图，对比一下数组和链表在内存中分配方式的不同。

数组的内存分配方式

链表的内存分配方式

图中的箭头代表链表节点的next指针。

链表的基本操作

1. 查找节点

在查找元素时，链表不像数组那样可以通过下标快速进行定位，只能从头节点开始向后一个一个节点逐一查找。

例如给出一个链表，需要查找从头节点开始的第3个节点。

第1步，将查找的指针定位到头节点。

第2步，根据头节点的next指针，定位到第2个节点。

第3步，根据第2个节点的next指针，定位到第3个节点，查找完毕。

所以说查找链表节点的时间复 杂度是多少？

链表中的数据只能按顺序进行访 问，最坏的时间复杂度是O(n) 。

2. 更新节点

如果不考虑查找节点的过程，链表的更新过程会像数组那样简单，直接把旧数据替换成新数据即可。

3. 插入节点

与数组类似，链表插入节点时，同样分为3种情况。

尾部插入

头部插入

中间插入

尾部插入，是最简单的情况，把最后一个节点的next指针指向新插入的节点即可。

头部插入，可以分成两个步骤。

第1步，把新节点的next指针指向原先的头节点。

第2步，把新节点变为链表的头节点。

中间插入，同样分为两个步骤。

第1步，新节点的next指针，指向插入位置的节点。

第2步，插入位置前置节点的next指针，指向新节点。

只要内存空间允许，能够插入链表的元素是无穷无尽的，不需要像数组那样考虑扩容的问题。

4. 删除元素

链表的删除操作同样分为3种情况。

尾部删除

头部删除

中间删除

尾部删除，是最简单的情况，把倒数第2个节点的next指针指向空即可。

头部删除，也很简单，把链表的头节点设为原先头节点的next指针即可。

中间删除，同样很简单，把要删除节点的前置节点的next指针，指向要删除元素的下一个节点即可。

这里需要注意的是，许多高级语言，如Java，拥有自动化的垃圾回收机制，所以我们不用刻意去释放被删除的节点，只要没有外部引用指向它们，被删除的节点会被自动回收。

链表的插入和删 除操作，时间复杂度分别是多少？

如果不考虑插入、删除操作之前查找元素的过程，只考虑纯粹的插入和删除操作，时间复杂度都

是O(1) 。

数组VS链表

数组和链表都属于线性的数据结构，用哪一个更好呢？数据结构没有绝对的好与坏，数组和

链表各有千秋。下面我总结了数组和链表相关操作的性能，我们来对比一下。

从表格可以看出，数组的优势在于能够快速定位元素，对于读操作多、写操作少的场景来说，用数组更合适一些。

相反地，链表的优势在于能够灵活地进行插入和删除操作，如果需要在尾部频繁插入、删除元素，用链表更合适一些。