双链表和循环链表

在单链表基础上扩展出双链表（加前驱指针）和循环链表（首尾相连），以换取更灵活的操作或减少边界判断。

一、双链表

每个结点含 prior、data、next，可双向遍历。在 p 之后插入 s 的四步：

s->next = p->next;      // ①
p->next->prior = s;   // ②（需 p->next != NULL）
s->prior = p;          // ③
p->next = s;           // ④

二、循环单链表

尾结点 next 指向头结点而非 NULL。判空：$L->next == L$。

三、循环双链表

头结点 prior 指向尾结点、尾结点 next 指向头结点；不存在 NULL 指针，插入删除无需判边界。

双链表后插：L ⇄ [1] ⇄ [2] ⇄ [3]，在 [1] 后插 [4]：

$s->next=[2]$，$[2]->prior=s$，$s->prior=[1]$，$[1]->next=s$ → L ⇄ [1] ⇄ [4] ⇄ [2] ⇄ [3]。

循环单链表尾插：输入 1,2,3，尾指针 r 始终指向末结点，$r->next=L$。