directions · 单向 / 双向

指针方向：单向与双向链表

链表的第一条分类轴是每个节点存几个指针。单向 (singly) 节点只有一个 next，整条链只能从头往尾走；双向 (doubly) 节点额外存一个 prev，既能向前也能向后。多出来的那个指针决定了「拿到一个节点后，能否 $O(1)$ 地操作它」。下面用查找 / 插入 / 删除三种操作看这条轴的影响：查找（按值） 单、双向都得逐个比，都是 $O(n)$ ；而在已知节点之前插入、或删除该节点要先拿到它的前驱——单向得从 head 找（在已知节点之后插入则单向也是 $O(1)$ ）( $O(n)$ )，双向 x.prev 当场可达 ( $O(1)$ )。

图 1 · 单向与双向链表在查找、插入、删除三种操作上的对照，可逐步观察指针改写的次数。

**为什么单向的插入 / 删除是 $O(n)$ ?**在一个已知节点 $x$ 之前插入、或删除 $x$ ，本质都要让它的前驱改写 next（插到 $x$ 之后则不必，那是 $O(1)$ ）。单向节点不记得谁指向自己，只能从 head 顺着 next 一路找到「p.next === x」的那个 $p$ ——这段查找就是 $O(n)$ 。改指针本身永远是 $O(1)$ ，贵的是「找到前驱」。

**双向链表用空间换前驱。**每个节点多存一个 prev 指针（64 位机上多 8 字节），换来 x.prev 当场可达——插入 / 删除一个已知节点都降到 $O(1)$ ，还能从尾向头反向遍历。代价是每次增删要多维护一根指针：双向删除改 2 处（前驱的 next、后继的 prev）、插入改 4 处（新节点两根加左右邻各一）；单向对应是删除 1 处、插入 2 处。工程里的 LRU 缓存、Linux 内核 list_head 几乎都用双向循环形态，正是图这份 $O(1)$ 增删。

单向与双向链表按值查找都是 $O(n)$ 。插入 / 删除的 $O(1)$ 指的是已经拿到节点引用（单向还需前驱）时。若只知道值、要先找到那个节点，单向、双向都得逐个扫描；链表家族里查找更快的是跳表那样另加索引层的变体——链表放弃的正是数组的随机访问。所以链表的真正优势场景：已持有节点位置、频繁就地增删；而非按值检索。

指针方向：单向 与 双向链表

指针方向：单向与双向链表