深入理解链表 - 哈喽比特 - https://www.hellobit.com.cn

387次阅读 | 发布于2年以前

链表是一种基本的线性表数据结构，它使用非连续的内存空间来存储一组数据。

与数组的连续内存空间相比，链表中的每个元素是可以存储在内存中的任意位置的，它通过指针将一组零散的内存块串联起来使用。

Next 是指针或引用类型，它存储的是所指对象的内存地址。正因为要存储下一个结点的内存地址，所以链表所需的整体内存空间要比数组的大。

链表的这种灵活的内存存储结构，让它的插入和删除变得比较高效。

当要在特定位置插入新结点时，需要 2 次赋值操作，所以时间复杂度是 O(1)。

当要删除给定结点时，需要 1 次赋值操作，所以时间复杂度是 O(1)。

我们知道，当要插入和删除结点的时候，需要知道它的上一个结点，所以单链表在执行真正的插入和删除操作之前，得先花 O(n) 的时间复杂度来进行遍历查找。为了更快地得到上一个结点，我们可以把其内存地址也存起来，这就是双向链表了。

上一个结点 ~ 前驱结点下一个结点 ~ 后继结点

双向链表可以 O(1) 地找到前驱结点，正是这样的特点使得双向链表在某些情况下的插入和删除操作都要比单链表高效，比如在指定结点前插入一个新结点或删除特定结点。所以双向链表的应用也挺广泛的，比如 Java 里的 LinkedHashMap 容器，就是用双向链表这种数据结构实现的。

不过，无论是单链表还是双向链表，当要随机访问第 i 个元素时，都没有数组那么高效，由于内存空间的不连续致使它没法靠索引来直接寻址，只能从头开始遍历，所以时间复杂度是 O(n)。

注意：这里是借时间复杂度来直观地理解特定数据结构的基本操作，重点是“特定数据结构”和“基本操作”。比如我们说链表可以 O(1) 地删除一个结点是指“删除”这一原子操作，倘若是删除单链表中的指定结点或是删除“值为X”的特定结点那链表还需要先 O(n) 地查询才能再 O(1) 地删除。

linked list double linked list

除了上面介绍的单链表和双向链表之外，还有一种非常常见的链表结构，那就是循环链表。

循环链表的特点是从链尾又重新指回了链头，这非常适用于具有环型结构特点的数据，比如著名的约瑟夫问题。

实战

链表的理论虽然不难，但要写好链表的代码也是不容易的，因为这里到处都是指针操作和边界处理，稍不留神就容易出 bug。

1 . 警惕指针丢失和内存泄露

2 . 链表的边界条件处理

3 . 善用保护结点，即带头的链表

在实际开发中，需要根据具体情况来权衡，究竟是选数组还是链表。

1 . 数组更省内存，且不易产生内存碎片

2 . 数组大小固定，而链表天然支持动态扩容

3 . 结合具体场景

本文重点介绍了链表的原理，包括其内存模型和基本操作的时间复杂度（随机访问/查询/插入/删除），当然这些都是基于特定的链表结构展开的（单链表/双向链表/循环链表）。最后简要说明了下写链表代码的注意事项，以及在实际开发中选择数组还是链表的几个参考点。