考研笔记

双链表、循环链表与静态链表

这一节的统考题全是指针语句题：2016 双链表删除、2021 循环单链表删除首元素、2023 双链表插入。 另一类高频题是「给一组操作，选最省时的链表」，靠的是同一条推理：每个操作要用到哪个结点，这个结点能不能 找到。

机制

2.3.3 双链表

结点有两个指针 prior 和 next，分别指向直接前驱和直接后继。表头结点的 prior 和尾结点的 next 都是 NULL。

  • 按值查找、按位查找与单链表相同。
  • 插入、删除要多改 prior，关键是保证修改过程中不断链。
  • 可以直接找到前驱，所以插入、删除本身都是 。

在 *p 之后插入 *s（2023 命题追踪）：

s->next=p->next;     // ①
p->next->prior=s;    // ②
s->prior=p;          // ③
p->next=s;           // ④

语句顺序不唯一，但 ① 必须在 ④ 之前，否则 *p 的后继指针就丢了。

删除 *p 的后继 *q（2016 命题追踪）：

p->next=q->next;     // ①
q->next->prior=p;    // ②
free(q);

在双链表的两个结点之间插入一个新结点，要改 4 个指针域：新结点的 prior、next，前一个结点的 next，后一个结点的 prior。

2.3.4 循环链表

循环单链表：尾结点的 next 不是 NULL，而是指向头结点，整个链表形成一个环。

  • 判空条件是 L->next==L，不是头结点的指针是否为空。带头结点的循环单链表中没有空指针。
  • 在任何位置上的插入和删除都是等价的，无须判断是否是表尾。
  • 可以从任意一个结点开始遍历整个链表。
  • 常只设尾指针 r，不设头指针：r->next 就是头结点，在表头和表尾插入都只需 ；只设头指针时，在表尾插入要 。

循环双链表：头结点的 prior 还要指向表尾结点。*p 为尾结点时 p->next==L；空表时头结点的 prior 和 next 都等于 L。

2.3.5 静态链表

用数组描述线性表的链式存储结构。结点也有 data 和 next，但 next 是结点在数组中的相对地址（数组下标），也称游标。

#define MaxSize 50
typedef struct{
    ElemType data;
    int next;          // 下一个元素的数组下标
}SLinkList[MaxSize];
  • 和顺序表一样，要预先分配一块连续的内存空间，最大容量在定义时就确定了。
  • 以 next==-1 作为结束的标志。
  • 插入、删除与动态链表相同，只需修改指针，不需要移动元素。
  • 适用于不支持指针的高级语言（如 Basic）。

2.3.6 顺序表和链表的比较

四个维度（存取方式、逻辑结构与物理结构、查找插入删除、空间分配）和选用原则收在 速查：顺序表与链表。一句话：通常较稳定的线性表选择顺序存储，频繁插入、删除的线性表宜选择链式存储。

手算模板

「选最省时的链表」：把每个操作要找的结点列出来，看哪种结构能 找到它。

操作需要 找到的结点
在表头插入 / 删除第一个元素头结点（或首元结点的前驱）
在表尾插入尾结点
删除尾结点尾结点的前驱——只有双链表能 找到
在循环单链表中删除首元结点首元的前驱：有头结点时是头结点；无头结点时是尾结点

王道 2.3.7 的五道同类题，答案都能用这张表推出来：

题操作组合答案理由
第 23 题末尾插入、删除（末尾）结点带头结点的循环双链表要找尾结点及其前驱
第 24 题删首、删尾、首前插、尾后插只有头结点指针的循环双链表L->prior 即尾结点，尾结点的 prior 即其前驱，四个操作都是
第 29 题在最后插入、删除第一个不带头结点且有尾指针的循环单链表r->next 是首元结点，两个操作都是
第 25 题 把两个循环单链表头尾相接两个指针都指向各自的尾结点未指明谁接在谁后面，要同时 找到两个表的头和尾
第 26 题删除首元结点却要 只有表头指针、没有头结点首元的前驱是尾结点，只能遍历去找

边界

说法判断说明
「双链表的优点是插入、删除更方便」❌两者插入删除都不用移动元素，双链表改指针反而更复杂。优点是访问前后相邻结点更灵活
「双链表可以随机访问」❌仍是顺序存取
「双链表插入的四句可以任意排列」❌顺序不唯一但不任意：① s->next=p->next 必须在 ④ p->next=s 之前
「在双链表两个结点之间插入要改 2 个指针」❌改 4 个
「带头结点的循环单链表判空：头结点的指针域为空」❌判空是 L->next==L，即头结点的指针域与 L 的值相等，不是与 L 的地址相等
「循环双链表判空：L->prior==NULL && L->next==NULL」❌是 L->prior==L && L->next==L
「head->next->next==head 说明表长为 1」❌表长为 0 或 1 都成立
「非循环双链表删除尾结点是 」❌没有尾指针，要走到表尾，；循环双链表才是
「静态链表存取第 个元素与 无关」❌空间是顺序分配的，但元素按游标依次查找，与 有关
「静态链表的最大容量可以增加」❌在定义时就确定，以后不能增加
「静态链表插入删除要移动元素」❌只改游标
「顺序存储只能存线性结构」❌也可以存储图和树（如完全二叉树的顺序存储）

错题复盘：2016 删除循环双链表中的 *p

正确答案 D：p->next->prev=p->prev; p->prev->next=p->next; free(p); 两句各自把 *p 的一侧邻居绕过 *p 接到另一侧邻居上。口诀：后继的前驱 = 我的前驱；前驱的后继 = 我的后继。 选项 A 第二句写成 p->prev->next=p->prev，前驱结点指向它自己；选项 B、C 第一句写成 p->next->prev=p->next，后继结点指向它自己。

错题复盘：2021 删除循环单链表的第一个元素

带头结点的非空循环单链表，h 为头指针，p 为尾指针。答案 D：q=h->next; h->next=q->next; if(p==q) p=h; free(q); 难点是 if(p==q) p=h;：表中只有一个元素时，被删的首元结点同时就是尾结点，删掉后尾指针必须改指向头结点，否则 p 指向已释放的结点。选项 C 把条件写反成 p!=q。 已用模拟跑过：D 在「多个元素」和「只有一个元素」两种情况下都正确；选项 B 漏了这一句，只在只有一个元素时出错。

错题复盘：2023 双链表插入，已执行前两句

已执行 s->next=p->next; p->next=s;，还需执行的是 C：s->prev=s->next->prev; s->next->prev=s; 执行完前两句后，p->next 已经是 s，不再是原后继。选项 B 的 p->next->prev=s 实际是 s->prev=s。原后继只能通过 s->next 找到，而它的 prev 此时还指向 p，所以 s->prev=s->next->prev 正好把 p 赋给 s->prev。 做这类题先画出前两句执行后的状态，再逐个检查选项里的 p->next 实际指向谁。

错题复盘：在 *p 之前插入 *q（2.3.7 第 15、17 题）

第 15 题答案：p->prior->next=q; q->next=p; q->prior=p->prior; p->prior=q;。p->prior 必须最后改，因为前三句都要通过它找到原前驱。 第 17 题（在 、 之间插入 ，p 指向 ，q 指向 ）的约束是：q->next=p->next 和 p->next->prior=q 都要在 p->next=q 之前，否则 p->next 已变成 ，找不到 。

考点

  • 双链表插入、删除的语句顺序：2016、2023。
  • 循环单链表删除首元时维护尾指针：2021。
  • 判空条件：单链表 / 循环单链表 / 循环双链表各不相同。
  • 「选最省时的链表」：看删除尾结点需不需要前驱。
  • 静态链表：数组实现、游标、next==-1、不移动元素、容量固定。

链接

反向链接