7. 采用头插法建立单链表
## 7. 采用头插法建立单链表 该方法从一个空表开始，生成新结点 $^*s$，并将读取的数据存入其数据域。然后，令 $s->next$ 指向头结点当前 next 所指的结点，再将头结点的 next 指向 $^*s$，如图 2.7 所示。重复此过程，新结点始终成为第一个数据结点，最终链表中的元素顺序与输入顺序相反。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图2.7 采用头插法建立单链表 ① 执行 free(q) 的作用是由系统回收一个 LNode 型结点，回收后的空间可供再次生成结点时用。 <!-- page: 47 --> 第2章 线性表 35每插入一个结点的时间复杂度为 $O(1)$，总时间复杂度为 $O(n)$。 ## 思考 若单链表不带头结点，则上述代码中哪些地方需要修改？① ## 8. 采用尾插法建立单链表 若希望输入顺序与链表中的元素顺序一致，则可采用尾插法。该方法将新结点插入当前链表的表尾。为此，需要维护一个尾指针 r，并且始终指向当前的尾结点；插入时，令 r->next 指向新结点*s，再将 r 更新为 s，使其继续指向新的尾结点，如图 2.8 所示。LinkList List_HeadInsert(LinkList &amp;L) { //逆向建立单链表 LNode *s; int x; //设元素类型为整型 L=(LNode*)malloc(sizeof(LNode)); //创建头结点 L-&gt;next=NULL; //初始为空链表 scanf("%d",&amp;x); //输入结点的值 while (x!=9999) { //输入 9999 表示结束 s=(LNode*)malloc(sizeof(LNode)); //创建新结点 s-&gt;data=x; s-&gt;next=L-&gt;next; L-&gt;next=s; //将新结点插入表中，L 为头指针 scanf("%d",&amp;x); } return L; }
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 2.8 采用尾插法建立单链表因为附设了一个尾指针，故无须遍历查找尾部，总时间复杂度仍为 $O(n)$。 ① 主要修改之处：因为在头部插入新结点，每次插入新结点后，都需要将它的地址赋值给头指针 L。 <!-- page: 48 --> 2027年数据结构考研复习指导 # 注意 单链表是链式存储结构的基础，建议读者熟练掌握其基本操作。在设计算法时，可先通过画图理清指针变化逻辑，再编写代码，有助于避免常见错误（如指针丢失、内存泄漏等）。 ## 2.3.3 双链表 单链表的每个结点仅包含一个指向其后继的指针，故只能从前往后依次遍历。若需访问某结点的前驱（插入或删除操作时），则要从头开始遍历，时间复杂度为 $O(n)$。为了克服这一局限，引入了双链表，双链表中的每个结点包含两个指针prior和next，分别指向直接前驱和直接后继，如图2.9所示。其中，头结点的prior为NULL，尾结点的next也为NULL。LinkList List_TailInsert(LinkList &amp;L) { //正向建立单链表 int x; //设元素类型为整型 L=(LNode*)malloc(sizeof(LNode)); //创建头结点 LNode *s,*r=L; //r 为表尾指针 scanf("%d",&amp;x); //输入结点的值 while (x!=9999) { //输入 9999 表示结束 s=(LNode *)malloc(sizeof(LNode)); s-&gt;data=x; r-&gt;next=s; r=s; //r 指向新的表尾结点 scanf("%d",&amp;x); } r-&gt;next=NULL; //尾结点指针置空 return L; }
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图2.9 双链表示意图 双链表结点类型的定义如下： 双链表的按值查找操作和按位查找操作与单链表的相同，通常也需要从头结点开始顺序查找。由于增加了指向前驱的指针，双链表在插入操作和删除操作中要同时维护前驱与后继两个方向的链接，因此其实现方式与单链表的有较大差异。关键在于：修改指针时不能造成断链。得益于对前驱结点的直接访问，在已知目标结点的前提下，双链表的插入和删除操作的时间复杂度可降至 $O(1)$。 ## 1. 双链表的插入操作 **修改指针** 双链表中插入操作的实现（2023） 在双链表的结点*p之后插入新结点*s，其指针变化过程如图2.10所示。代码片段如下：
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图2.10 双链表插入结点过程 上述语句的执行顺序并不是任意的：步骤①必须在步骤④之前，否则p->next被覆盖后，无法访问原后继结点，导致指针丢失，插入失败。其余步骤可在保证逻辑正确的前提下适当调整（例如③可在①前执行）。若问题改成要求在结点*p之前插入结点*s，则要如何处理？请读者自行推导操作步骤。 <!-- page: 49 --> 第2章 线性表 37 # 2. 双链表的删除操作 **特点信息** ➔ 双链表中删除操作的实现（2016） 删除双链表中结点*p的后继结点*q，其指针的变化过程如图2.11所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图2.11 双链表删除结点过程 若问题改成要求删除结点*q的前驱结点*p，请读者尝试写出对应的操作步骤。 建立双链表时，同样可以采用类似单链表的头插法或尾插法，但要注意：每次插入新结点时，要同时正确设置 next 和 prior 两个指针，以维持双向链接的完整性。 ## 2.3.4 循环链表 ### 1. 循环单链表 循环单链表与普通单链表的主要区别在于：表中最后一个结点的next域不再为NULL，而是指向头结点，从而使整个链表形成一个环。这种结构使得从任意一个结点出发均可遍历整个循环单链表，而不仅限于从表头开始，如图2.12所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图2.12 循环单链表
尾结点*r的next指向头结点，因此链表中不存在next为NULL的结点。判空条件不再是检查头指针L是否为空，而是检查头结点的next是否指向自身（L->next==L）。
**特点信息** ➔ 循环单链表中删除首元素的操作（2021）
循环单链表的插入和删除操作与普通单链表基本相同，但有一个关键差异：在表尾进行操作时，需要特别处理以维持链表的循环特性。然而，正是因为循环单链表是一个环，在任何位置上的插入和删除操作都是等价的，因此无须判断是否到达表尾。
为了提高效率，循环单链表有时不设头指针，而仅设置尾指针 $\pmb{r}$。此时，在表头或表尾插入元素的时间复杂度均为 $O(1)$。若使用头指针，则表尾插入需要遍历整个链表，时间复杂度为 $O(n)$。例如，在表尾插入新结点*s时，需要执行以下步骤：令s->next=r->next（使新结点的后继指向头结点，以维持环状结构）；将r->next指向新结点*s；更新r为新结点*s。
### 2. 循环双链表
基于循环单链表的概念，不难推导出循环双链表。不同之处在于：循环双链表中的每个结点不仅包含指向下一个结点的next域，还包含指向前一个结点的prior域。特别地，头结点的prior
<!-- page: 50 -->
2027年数据结构考研复习指导
需要指向表尾结点，从而形成一个完整的环形结构，如图2.13所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图2.13 循环双链表 设尾结点为*p，则p->next应指向头结点L；同时，L->prior应指向*p。当循环双链表为空时，其头结点L的prior和next都指向自身（L->prior==L且L->next==L）。 ## 2.3.5 静态链表 静态链表是用数组来模拟线性表的链式存储结构。每个结点都包含两个域：data域和next域。与动态链表不同的是，这里的指针实际上是结点在数组中的相对地址（数组下标），也称寿标。类似于顺序表，静态链表也需要预先分配一块连续的内存空间。 静态链表和单链表的对应关系如图2.14所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a)静态链表示例 (b)静态链表对应的单链表 图2.14 静态链表和单链表的对应关系 静态链表的结构类型定义如下： 静态链表以 next==-1 作为其结束标志。静态链表的插入、删除操作与动态链表类似，只需修改指针（数组下标），而无须移动元素。尽管静态链表在灵活性上不及动态链表，但在一些不支持指针的编程语言（如 Basic）中，它提供了一种巧妙的设计方案。 ## 2.3.6 顺序表和链表的比较 ### 1. 存取（读/写）方式 顺序表支持随机存取，可通过下标直接访问任意位置元素，时间复杂度为 $O(1)$，同时也支持顺序存取。链表仅支持顺序存取，必须从头结点开始逐个遍历。例如，访问第 $i$ 个元素时，顺序表只需一次操作；而链表需要遍历 $i$ 个结点，平均时间复杂度为 $O(n)$。 ### 2. 逻辑结构与物理结构 顺序存储中，逻辑上相邻的元素在物理内存中也连续存放，其邻接关系由地址自然体现；链式存储中，逻辑相邻的元素在物理上未必相邻，其逻辑关系通过指针显式维护。 <!-- page: 51 --> 第2章 线性表 39 ## 3. 查找、插入和删除操作 对于按值查找，若表无序，则两者的时间复杂度均为 $O(n)$；若表有序，则顺序表可以采用折半查找，时间复杂度为 $O(\log_2 n)$。对于按序号查找，顺序表的时间复杂度为 $O(1)$，链表则为 $O(n)$。对于插入/删除操作，顺序表平均需移动约一半的元素，开销较大；链表只需修改指针，无须移动元素，但前提是已知操作位置（否则仍需 $O(n)$ 的时间定位）。 ## 4. 空间分配 顺序表在静态分配下需预先设定容量：过大造成内存浪费，过小则易在插入时溢出。动态分配虽支持运行时扩容，但需要申请新的连续内存块并复制全部原有数据，不仅耗时，还可能因系统缺乏足够连续空闲空间而失败。相比之下，链表采用动态结点分配，按需扩展，灵活性高，但每个结点需额外存储指针域，导致存储密度小于1，空间利用率较低。 在实际应用中，该如何选择合适的存储结构呢？ ### 1. 基于存储的考虑 当线性表的长度或规模难以预估时，顺序表因需预先分配固定容量而不适用；而链表无须预设容量，可按需动态扩展，但每个结点需额外存储指针，带来一定的空间开销。 ### 2. 基于运算的考虑 若应用中频繁进行按序号访问（随机访问），顺序表具有 $O(1)$ 的优势，明显更高效；而对于以插入和删除为主的操作，链表在定位目标位置后仅需调整指针，开销较小。尽管定位过程本身仍需 $O(n)$ 时间，但在增删密集的场景下，链表的整体性能通常更优。 ### 3. 基于环境的考虑 顺序表基于数组实现，几乎所有高级语言都支持，实现简单；链表则依赖指针操作，在部分环境中实现较为复杂。因此，开发语言和运行环境也是重要的考量因素。 综上所述，两种结构各有优劣。对于规模稳定、以随机访问为主的场景，宜采用顺序存储；而动态性强、频繁进行插入和删除操作的场景，则更适合链式存储。 **注意** 只有熟练掌握线性表的顺序存储和链式存储，才能深刻理解它们的优缺点。 ## 2.3.7 本节试题精选 ### 一、单项选择题 01. 下列关于线性表的存储结构的描述中，正确的是（）。 I. 线性表的顺序存储结构优于其链式存储结构 II. 链式存储结构比顺序存储结构能更方便地表示各种逻辑结构 III. 若频繁使用插入和删除结点操作，则顺序存储结构更优于链式存储结构 IV. 顺序存储结构和链式存储结构都可以进行顺序存取 A. I、II、III B. II、IV C. II、III D. III、IV 02. 对于一个线性表，既要求能进行较快速地插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（）。 A. 顺序存储方式 B. 链式存储方式 C. 散列存储方式 D. 以上均可以 03. 链式存储设计时，结点内的存储单元地址（）。 <!-- page: 52 --> 2027年数据结构考研复习指导 A. 一定连续 B. 一定不连续 C. 不一定连续 D. 部分连续，部分不连续 04. 下列关于线性表的说法中，正确的是（ ）。 I. 顺序存储方式只能用于存储线性结构 II. 在一个设有头指针和尾指针的单链表中，删除表尾元素的时间复杂度与表长无关 III. 带头结点的循环单链表中不存在空指针 IV. 在一个长度为 $n$ 的有序单链表中插入一个新结点并仍保持有序的时间复杂度为 $O(n)$ V. 若用单链表来表示队列，则应该选用带尾指针的循环链表 A. I、II B. I、III、IV、V C. IV、V D. III、IV、V 05. 设线性表中有 $2n$ 个元素，（ ）在单链表上实现要比在顺序表上实现效率更高。 A. 删除所有值为 $x$ 的元素 B. 在最后一个元素的后面插入一个新元素 C. 顺序输出前 $k$ 个元素 D. 交换第 $i$ 个元素和第 $2n - i - 1$ 个元素的值 $(i = 0, \dots, n - 1)$ 06. 在一个单链表中，已知 $q$ 所指结点是 $p$ 所指结点的前驱结点，若在 $q$ 和 $p$ 之间插入结点 $s$，则执行（ ）。 A. $s \rightarrow next = p \rightarrow next; p \rightarrow next = s$; B. $p \rightarrow next = s \rightarrow next; s \rightarrow next = p$; C. $q \rightarrow next = s; s \rightarrow next = p$; D. $p \rightarrow next = s; s \rightarrow next = q$; 07. 给定有 $n$ 个元素的一维数组，建立一个有序单链表的最低时间复杂度是（ ）。 A. $O(1)$ B. $O(n)$ C. $O(n^{2})$ D. $O(n \log_{2} n)$ 08. 将长度为 $n$ 的单链表链接在长度为 $m$ 的单链表后面，其算法的时间复杂度采用大 $O$ 形式表示应该是（ ）。 A. $O(1)$ B. $O(n)$ C. $O(m)$ D. $O(n + m)$ 09. 单链表中，增加一个头结点的目的是（ ）。 A. 使单链表至少有一个结点 B. 标识表结点中首结点的位置 C. 方便运算的实现 D. 说明单链表是线性表的链式存储 10. 在一个长度为 $n$ 的带头结点的单链表 $h$ 上，设有尾指针 $\tau$，则执行（ ）操作与链表的表长有关。 A. 删除单链表中的第一个元素 B. 删除单链表中的最后一个元素 C. 在单链表第一个元素前插入一个新元素 D. 在单链表最后一个元素后插入一个新元素 11. 对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）；对于不带头结点的单链表，判定空表的条件为（ ）。 A. head==NULL B. head->next==NULL C. head->next==head D. head!=NULL 12. 在线性表 $a_0, a_1, \dots, a_{100}$ 中，删除元素 $a_{50}$ 需要移动（ ）个元素。 A. 0 B. 50 C. 51 D. 0 或 50 13. 通过含有 $n (n > 1)$ 个元素的数组 $a$，采用头插法建立单链表 $L$，则 $L$ 中的元素次序（ ）。 A. 与数组 $a$ 的元素次序相同 B. 与数组 $a$ 的元素次序相反 <!-- page: 53 --> 第2章 线性表 41 C. 与数组 $a$ 的元素次序无关 D. 以上都错误 14. 下面关于线性表的一些说法中，正确的是（）。 A. 对一个没有头指针和尾指针的单链表执行删除最后一个元素的操作与链表长度无关 B. 线性表中每个元素都有一个直接前驱和一个直接后继 C. 为了方便插入和删除数据，可以使用双链表存放数据 D. 取线性表第 $i$ 个元素的时间与 $i$ 的大小有关 15. 在双链表中向 $\mathbb{P}$ 所指的结点之前插入一个结点 $\mathbb{q}$ 的操作为（）。 A. $p \rightarrow prior = q; q \rightarrow next = p; p \rightarrow prior \rightarrow next = q; q \rightarrow prior = p \rightarrow prior;$ B. $q \rightarrow prior = p \rightarrow prior; p \rightarrow prior \rightarrow next = q; q \rightarrow next = p; p \rightarrow prior = q \rightarrow next;$ C. $q \rightarrow next = p; p \rightarrow next = q; q \rightarrow prior \rightarrow next = q; q \rightarrow next = p;$ D. $p \rightarrow prior \rightarrow next = q; q \rightarrow next = p; q \rightarrow prior = p \rightarrow prior; p \rightarrow prior = q;$ 16. 在双链表存储结构中，删除 $\mathbb{P}$ 所指的结点时必须修改指针（）。 A. $p \rightarrow prior \rightarrow next = p \rightarrow next; p \rightarrow next \rightarrow prior = p \rightarrow prior;$ B. $p \rightarrow prior = p \rightarrow prior \rightarrow prior; p \rightarrow prior \rightarrow next = p;$ C. $p \rightarrow next \rightarrow prior = p; p \rightarrow next = p \rightarrow next \rightarrow next;$ D. $p \rightarrow next = p \rightarrow prior \rightarrow prior; p \rightarrow prior = p \rightarrow next \rightarrow next;$ 17. 在如下图所示的双链表中，已知指针 $\mathbb{P}$ 指向结点 $A$，若要在结点 $A$ 和 $C$ 之间插入指针 $\mathbb{q}$ 所指的结点 $B$，则依次执行的语句序列可以是（）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
① $q \rightarrow next = p \rightarrow next;$
② $q \rightarrow prior = p;$
③ $p \rightarrow next = q;$
④ $p \rightarrow next \rightarrow prior = q;$
A. ①②④③
B. ④③②①
C. ③④①②
D. ①③④②
18. 在双链表的两个结点之间插入一个新结点，需要修改（）个指针域。
A. 1
B. 3
C. 4
D. 2
19. 在长度为 $n$ 的有序单链表中插入一个新结点，并仍然保持有序的时间复杂度是（）。
A. $O(1)$
B. $O(n)$
C. $O(n^{2})$
D. $O(n\log_2 n)$
20. 与单链表相比，双链表的优点之一是（）。
A. 插入、删除操作更方便
B. 可以进行随机访问
C. 可以省略表头指针或表尾指针
D. 访问前后相邻结点更灵活
21. 对于一个带头结点的循环单链表 $L$，判断该表为空表的条件是（）。
A. 头结点的指针域为空
B. $L$ 的值为 NULL
C. 头结点的指针域与 $L$ 的值相等
D. 头结点的指针域与 $L$ 的地址相等
22. 对于一个带头结点的循环双链表 $L$，判断该表为空表的条件是（）。
A. $L \rightarrow prior == L \& L \rightarrow next == NULL$
B. $L \rightarrow prior == NULL \& L \rightarrow next == NULL$
C. $L \rightarrow prior == NULL \& L \rightarrow next == L$
D. $L \rightarrow prior == L \& L \rightarrow next == L$
23. 一个链表最常用的操作是在末尾插入结点和删除结点，则选用（）最节省时间。
A. 带头结点的循环双链表
B. 循环单链表
C. 带尾指针的循环单链表
D. 单链表
24. 设对 $n (n > 1)$ 个元素的线性表的运算只有 4 种：删除第一个元素；删除最后一个元素；在第一个元素之前插入新元素；在最后一个元素之后插入新元素，则最好使用（）。
<!-- page: 54 -->
2027年数据结构考研复习指导
A. 只有尾结点指针没有头结点指针的循环单链表
B. 只有尾结点指针没有头结点指针的非循环双链表
C. 只有头结点指针没有尾结点指针的循环双链表
D. 既有头结点指针又有尾结点指针的循环单链表
25. 有两个长度为 $n$ 的循环单链表，若要求两个循环单链表头尾相接的时间复杂度为 $O(1)$，则对应两个循环单链表各设置一个指针，分别指向（）。
A. 各自的头结点
B. 各自的尾结点
C. 各自的首结点
D. 一个表的头结点，另一个表的尾结点
26. 有一个长度为 $n$ 的循环单链表，若从表中删除首元结点的时间复杂度达到 $O(n)$，则此时采用的循环单链表的结构可能是（）。
A. 只有表头指针，没有头结点
B. 只有表尾指针，没有头结点
C. 只有表尾指针，带头结点
D. 只有表头指针，带头结点
27. 某线性表用带头结点的循环单链表存储，头指针为 head，当 head->next->next== head 成立时，线性表的长度可能是（）。
A. 0
B. 1
C. 2
D. 可能为 0 或 1
28. 有两个长度都为 $n$ 的双链表，若以 $h_1$ 为头指针的双链表是非循环的，以 $h_2$ 为头指针的双链表是循环的，则下列叙述中正确的是（）。
A. 对于双链表 $h_1$，删除首结点的时间复杂度是 $O(n)$
B. 对于双链表 $h_2$，删除首结点的时间复杂度是 $O(n)$
C. 对于双链表 $h_1$，删除尾结点的时间复杂度是 $O(1)$
D. 对于双链表 $h_2$，删除尾结点的时间复杂度是 $O(1)$
29. 一个链表最常用的操作是在最后一个元素后插入一个元素和删除第一个元素，则选用（）最节省时间。
A. 不带头结点的循环单链表
B. 双链表
C. 单链表
D. 不带头结点且有尾指针的循环单链表
30. 需要分配较大连续空间，插入和删除不需要移动元素的线性表，其存储结构为（）。
A. 单链表
B. 静态链表
C. 顺序表
D. 双链表
31. 下列关于静态链表的说法中，正确的是（）。
I. 静态链表兼具顺序表和单链表的优点，因此存取表中第 $i$ 个元素的时间与 $i$ 无关
II. 静态链表能容纳的最大元素个数在表定义时就确定了，以后不能增加
III. 静态链表与动态链表在元素的插入、删除上类似，不需要移动元素
IV. 相比动态链表，静态链表可能浪费较多的存储空间
A. I、II、III
B. II、III、IV
C. I、III、IV
D. I、II、IV
32.【2016 统考真题】已知一个带有表头结点的循环双链表 L，结点结构为 prev data next，其中 prev 和 next 分别是指向其直接前驱和直接后继结点的指针。现要删除指针 p 所指的结点，正确的语句序列是（）。
A. p->next->prev=p->prev; p->prev->next=p->prev; free(p);
B. p->next->prev=p->next; p->prev->next=p->next; free(p);
C. p->next->prev=p->next; p->prev->next=p->prev; free(p);
D. p->next->prev=p->prev; p->prev->next=p->next; free(p);
33. 【2016 统考真题】已知表头元素为 c 的单链表在内存中的存储状态如下表所示。
<!-- page: 55 -->
第2章 线性表
43
| 地址 | 元素 | 链接地址 |
| --- | --- | --- |
| 1000H | a | 1010H |
| 1004H | b | 100CH |
| 1008H | c | 1000H |
| 100CH | d | NULL |
| 1010H | e | 1004H |
| 1014H | | |
现将f存放于1014H处并插入单链表，若f在逻辑上位于a和e之间，则a、e、f的“链接地址”依次是（）。
A. 1010H、1014H、1004H
B. 1010H、1004H、1014H
C. 1014H、1010H、1004H
D. 1014H、1004H、1010H
34. 【2021统考真题】已知头指针h指向一个带头结点的非空循环单链表，结点结构为data next，其中next是指向直接后继结点的指针，p是尾指针，q是临时指针。现要删除该链表的第一个元素，正确的语句序列是（）。
A. h->next=h->next->next;q=h->next;free(q);
B. q=h->next;h->next=h->next->next;free(q);
C. q=h->next;h->next=q->next;if(p!=q) p=h;free(q);
D. q=h->next;h->next=q->next;if(p==q) p=h;free(q);
35. 【2023统考真题】现有非空双链表L，其结点结构为prev data next，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;
36. 【2024统考真题】已知带头结点的非空单链表L的头指针为h，结点结构为data next，其中next是指向直接后继结点的指针。现有指针p和q，若p指向L中非首且非尾的任意一个结点，则执行语句序列“q=p->next; p->next=q->next; q->next=h->next; h->next=q;”的结果是（）。
A. 在p所指结点后插入q所指结点
B. 在q所指结点后插入p所指结点
C. 将p所指结点移至L的头结点之后
D. 将q所指结点移动到L的头结点之后