链表

定义

链表是一种数据结构，由若干个节点组成，每个节点包含数据和指针两个部分。

Note

实际上,单链表就是链式存储结构，是线性表的一种。

内存中的组织形式

链表在物理存储单元上不是连续的。也就是说，相邻的节点在内存地址中并不相邻，节点与节点之间只通过指针相连（除了头节点 head 以外）。

分类

根据每个节点中指针所指向的节点的数量和位置，链表可以分成单向链表和双向链表。

根据链表中有没有环，链表可以分成有环链表和无环链表，这种分类往往多用于刷题里。

链表的表示

一个链表由其头节点 head 来表示。如有需求，亦可以定义一个长度变量来记录链表的长度

总的来说，头节点 head 有两种定义形式：即哨兵模式和非哨兵模式

非哨兵模式：以第一个节点元素作为头节点

哨兵模式（推荐）：以一个虚拟的节点作为头节点，该头节点称为哨兵 dummy

在非哨兵模式下，进行链表的插入、删除等操作时每次都需要对头结点进行“判空”操作，造成了头节点和其他节点的操作逻辑上的不一致性。

操作

以单链表为例

查找

• 时间复杂度$O(N)$，额外空间复杂度$O(1)$
• 对于链表来说，查找一个元素只能从头节点开始一个一个遍历。

插入

• 时间复杂度$O(N)$（受到插入位置的影响），额外空间复杂度$O(1)$
• 先找到对应插入的位置，再将前一个节点的next指针指向插入的节点，并将插入的节点的next指针指向原来在该位置上的节点。

删除

• 时间复杂度$O(N)$（受到删除位置的影响），额外空间复杂度$O(1)$
• 先找到对应插入的位置，再将前一个节点的next指针指向删除的节点的下一个节点即可。（进一步，我们可以释放掉被删除的节点，防止泄露）

适用场景

• 数据查询少，数据插入和删除的场景比较多
• 元素所需的内存空间分配较大时¹

范围

链式存储结构（链表）, 树

Footnotes

1. 当元素所需分配的内存空间大时，若使用数组，就会对内存的连续性有较高的要求。当内存碎片比较多的时候，可能很难直接分配连续的大内存。 ↩