数据结构之链表【上】

1. 什么是链表

链表是通过指针把一组零散的内存块串联在一起的线性数据结构。

链表和数组的内存分布如下图所示：

可以看出，链表和数组的最大区别在于，数组需要一块连续的内存空间来存储，对内存的要求较高。而链表不需要连续的内存空间，它通过指针将一组零散的内存块串联起来使用。

根据指针的不同使用方式，链表又可以分为单链表、双向链表和循环链表。

• 单链表

  • 结点包括当前数据和后继结点的地址

• 双向链表

  • 结点包括当前数据、前驱结点的地址和后继结点的地址

• 循环链表

  • 结点包括当前数据和后继结点的地址，尾结点的指针指向头结点

• 双向循环链表

  • 结点包括当前数据、前驱结点的地址和后继结点的地址，尾结点的后继结点是头结点，头结点的前驱结点是尾结点

2. 链表的基本操作及其复杂度

2.1 查找

想要随机访问链表的第 k 个元素，就没有数组那么高效了。因为链表中的数据并非连续存储的，不能像数组那样，根据下标和首地址，通过寻址公式就能直接计算出对应的内存地址。而是要根据指针一个结点一个结点的依次遍历。因此，需要 O(n) 的时间复杂度。

特别的，对于双向链表，给定一个结点，要找出其前驱结点时，时间复杂度为 O(1)，单链表则仍为 O(n)。

2.2 插入、删除

在前一篇中我们提到，进行数组的插入、删除操作时，为了保证内存的连续性，需要做大量的数据搬移，所以时间复杂度是 O(n)。

而在链表中插入、删除时，因为不需要为了保持内存的连续性而搬移结点，所以是非常快速的，只需要 O(1) 的时间复杂度。

虽然链表的插入、删除操作时间复杂度只要 O(1)，但是，实际情况下却并非如此。因为，在实际开发中，还需要定位到进行操作的位置。例如，在链表中删除一个数据有可能是这两种情况：

• 删除结点中“值等于某个给定值”的结点
• 删除给定指针指向的结点

对于第一种情况，需要对链表进行遍历，找到相应的位置然后删除，此时删除操作的时间复杂度为 O(n)。

对于第二种情况，已知了要删除的结点，但是删除某个结点需要知道它的前驱结点，对于单链表仍然需要遍历寻找，时间复杂度为 O(n)；而对于双向链表，可以直接找到，所以时间复杂度为 O(1)。这也是双向链表在实际开发中经常使用的原因。

3. 链表和数组的比较

链表和数组是两种截然不同的内存组织方式，正因如此，它们插入、删除、随机访问的时间复杂度正好相反。

数组使用的是连续的内存空间，可以利用空间局部性原理，借助 CPU cache 进行预读，所以访问效率更高。而链表不是连续存储，无法进行缓存，随机访问效率也较低。

数组的缺点是大小固定，一经声明就要占用整块连续的内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间用于分配，就会导致“内存不足（out of memory）”。而如果声明的数组过小，当不够用时，又需要重新申请一块更大的内存，然后进行数据拷贝，非常费时。

而链表则没有大小限制，支持动态扩容。当然，因为链表中每个结点都需要存储前驱 / 后继结点的指针，所以内存消耗会翻倍。而且，对链表频繁的插入、删除操作会导致频繁的内存申请和释放，容易造成内存碎片和触发垃圾回收（Garbage Collection, GC）。

本文是《数据结构与算法之美》的读书笔记，首发于公众号《代码写完了》