双向链表插入结点操作：更新指针详解

现有非空双向链表 L，其结点结构为：fig2.jpg，prev 是指向直接前驱结点的指针，next 是指向直接后继结点的指针。若要在 L 中指针 p 所指向的结点（非尾结点）之后插入指针 s 指向的新结点，则在执行了语句序列 s->next = p->next; p->next = s; 后，下列语句序列中还需要执行的是：

A. s->next->prev = p; s->prev = p;

B. p->next->prev = s; s->prev = p;

C. s->prev = s->next->prev; s->next->prev = s;

D. p->next->prev = s->prev; s->next->prev = p;

我认为选 C，你觉得呢？如果不选 C 给我讲解一下内容：

你的选择是正确的，答案是 C. s->prev = s->next->prev; s->next->prev = s;。

在执行了语句序列 s->next = p->next; p->next = s; 后，我们需要更新指针 s 的前驱指针和后继指针。

首先，s->prev = s->next->prev; 这一步将 s 的前驱指针更新为 p。因为在插入 s 之前，p 是 s 的前一个结点，所以将 p 赋给 s 的 prev。

然后，s->next->prev = s; 这一步将 s 的后继结点（原来是 p->next）的前驱指针更新为 s。因为在插入 s 之后，s 成为 p 的后一个结点，所以将 s 赋给 p->next 的 prev。

这样，链表的结构就正确地更新了，保持了双向链表的连接关系。选项 C 中的这两个语句序列是插入操作中必须要执行的。