链表 Linked List

数据结构 · 用指针把节点串起来的序列

什么是链表

和数组把元素挤在连续内存里不同，链表的节点散落各处，每个节点除了存值，还存一根指向下一个节点的 next 指针，像手拉手一样把它们串成一条链。开头有个 head 指针指向第一个节点，最后一个节点的 next 指向 ∅（null）表示结束。

正因为不连续，想取第 i 个节点没法直接跳——只能从 head 出发，顺着 next 一个一个走过去，所以按位置访问是 O(n)。但反过来，增删节点时只需改几根指针、谁也不用搬，是 O(1)。正好和数组互为镜像。点一个节点选中它，再操作看看。

点中一个靠后的节点按「查找」——看游标从 head 一跳一跳走过去，走了几步才到，这就是 O(n)。再按「在其后插入」，新节点当场接进链里，只有相邻的两根 next 被改写（高亮那两根），其余节点纹丝不动，O(1)；删除同理，让前一个节点的 next 直接跳过它即可。这正是数组（访问快、增删慢）与链表（访问慢、增删快）的取舍。

双向链表：再加一根 prev 指针

上面的链表每个节点只有一根 next，只能从 head往后走。给每个节点再加一根指向前一个节点的 prev 指针，就成了双向链表。

多出来的 prev 换来两件单链表做不到的事：① 反向遍历——能从 tail 沿 prev 一路往回走；②给定任意一个节点就能 O(1) 删除它——单链表只拿到一个节点，得先从 head 走 O(n) 找到它的前驱才能删；双向链表的节点自带 prev，直接 prev.next = next、next.prev = prev 两步接线就行。点「反向遍历」，或点一个节点删除看看。

代价也很实在：每个节点要多存一根指针，增删时要多维护一根。如果再把尾节点的 next 接回头、头的 prev 接到尾，链就首尾相连成了循环链表——环状结构，适合轮询调度、轮转缓冲这类「转圈」的场景。

链表在哪里用

链表牺牲了随机访问，换来增删的灵活。下一篇进入树——节点不再排成一条线，而是长出层次分明的分叉。