2.3.3 双链表：用冗余指针换取双向移动

双链表结点同时保存前驱和后继：

typedef struct DNode { int data; struct DNode *prev, *next; } DNode;

它的优势不是按位访问变成 $O(1)$，而是已知某结点时能直接找到前驱；从尾结点向前遍历也无需重新从头开始。代价是每个结点多一个指针，更新时必须维护成对关系。

在 p 后插入 s，稳妥顺序为：先让 s 接住两侧，再让两侧回指 s：

s->next = p->next; s->prev = p;
if (p->next) p->next->prev = s;
p->next = s;

删除 p 的后继 q：p->next=q->next; if(q->next) q->next->prev=p; free(q);。尾部没有后继，因此回写前必须判空；若采用首尾哨兵，可减少边界分支。

核心不变量是：对每条有效的 x->next=y，都有 y->prev=x。调试时从头向后走一遍，再从尾向前走一遍；两次访问结点序列应互为逆序。

陪做：A <-> B <-> C 在 B 后插入 X。若只改 B.next=X 和 X.next=C，从后向前仍有 C.prev=B，链表两种遍历结果不一致。补上 X.prev=B 与 C.prev=X 才完整。

错解反馈：认为多了 prev 就能直接找到第 $i$ 个元素，忽略仍需从端点走链；删除只维护 next 会留下指向已释放结点的 prev；不区分尾结点与中间结点会空指针解引用。

迁移练习：设计校验函数，遍历每个 x->next 并检查 x->next->prev==x。空链和单结点链也必须通过。独立验收：能不看资料写出中间插入四次指针修改，并说明尾插时哪一步需要判空。