directions · 单向 / 双向

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

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

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

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

查找 (query) 永远是 $O(n)$ 。上面插入 / 删除的 $O(1)$ 指的是已经拿到节点引用时。若只知道值、要先找到那个节点（上面的「查找」演示），单向、双向都得逐个扫描——链表放弃的正是数组的随机访问。所以链表的真正优势场景：已持有节点位置、频繁就地增删；而非按值检索。

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

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