软考-软件设计师：数据结构-线性结构-线性表-链表（链式存储）和单链表 作者：马育民 • 2026-02-08 16:56 • 阅读：10005 # 链表 链表，也称为链式存储。链表的 **内存是不连续的**，不像数组那样连续存储在内存中，而是由一系列 **节点** 组成 ### 节点 每个节点包含两部分： - `数据域`（存储实际值） - `指针域`（指向下一个节点的地址） 如下图：  ### 分类 - 单链表 - 双向链表 - 循环链表 # 单链表 单链表是最简单的链表  ### 指针 除了最后一个结点，每个结点的指针，指向下一个结点 ### 不带头结点单链表（很少） 如下图，没有头结点，很少  ### 普通单链表（默认带头结点）  - **头结点：**第一个有效结点之前的那个结点，存放链表首地址。 - **作用：**方便对链表的操作，如：在链表头部执行删除结点、插入结点。 - **头指针：**指向 **头结点** 的 **指针变量** ### 首结点 第一个有效结点(存有数据的结点） ### 尾结点 尾结点：最后一个有效结点。尾结点的指针域指向 `null`，表示链表结束。 ### 优点 - 不需要连续空间，对内存友好。可以零散分布，内存利用率更高 - 插入、删除效率高。不需要移动大量元素，只需要修改指针，时间复杂度 `O (1)`（不算找到位置的时间） - 适合频繁增删的场景 - 长度动态可变，可随时扩展。不像数组那样，要预先设置大小 ### 缺点 - 耗费更多空间，存储下一个元素的地址 - 随机访问效率极低，时间复杂度：`O (n)`（要访问第 `k` 个节点，必须从头节点开始，**顺着指针逐个遍历到第 k 个**，不能像数组那样，通过索引访问）。 - 遍历效率低于数组，链表的节点是不连续的，分散在内存各处，每次访问节点都要重新寻址 ### 特点 - n个结点离散分布，彼此通过指针相联系。 - 除头结点和尾结点外，每个结点 **只有一个前驱结点** 和 **一个后继结点**。头结点没有前驱结点，尾结点没有后继结点。 - **头结点不存放数据**，**只存放链表首节点的地址**。其头结点的数据类型和首结点类型一样 ### 对比数组 | 操作 | 数组（顺序表） | 单链表 | |--------------|------------------------------|----------------------------| | 插入/删除 | 需移动大量元素，效率低 O(n) | 仅改指针，效率高 O(1) | | 存储空间 | 必须连续，预先固定大小 | 可不连续，动态申请 | | 长度变化 | 固定或扩容麻烦 | 随时增减，灵活 | | 按序号访问 | 随机访问，O(1) | 只能从头遍历，O(n) | # 单链表的操作 ### 头部插入 把新节点添加到链表最开头（**注意：**头结点的指针指向新节点） **操作：**新节点的指针指向原头节点，再把链表的头结点的指针指向新节点。 **时间复杂度：** `O(1)`，无需遍历，是单链表最高效的插入方式。 ### 头部删除 移除链表第一个节点（不是头结点），让第二个节点成为新的头节点。 **操作：**直接把head指针指向第二个节点 **时间复杂度：** `O(1)`，无需遍历，仅修改head指针的指向， ### 尾部插入 把新节点添加到链表的末尾，成为新的尾节点 **操作：**遍历找尾节点（从head开始，顺着每个节点的next指针往后走，直到找到当前尾节点），把尾节点指针指向新节点 **时间复杂度：**`O(n)`，必须遍历整个链表找到尾节点，节点数越多，遍历步数越多（最多走 `n` 步）。 ### 尾部删除 移除链表的最后一个节点，让倒数第二个节点成为新的尾节点。 **操作：** **遍历找倒数第二个节点**（从头结点开始遍历，直到找到倒数第二个节点），把倒数第二个节点的指针置为 `null` **时间复杂度：**`O(n)`，必须遍历整个链表找到尾节点，节点数越多，遍历步数越多（最多走 `n-1` 步）。 ### 中间位置插入 [](https://www.malaoshi.top/upload/0/0/1GWtigXgYJm.png) ### 删除节点 [](https://www.malaoshi.top/upload/0/0/1GWtihOdbar.png) # 总结 链式存储的空间密度 `<1`，因为存储指向下一个节点的指针 [](https://www.malaoshi.top/upload/0/0/1GWtikTSx1B.png) # 题 设有一个包含n个元素的有序线性表。在等概率情况下删除其中的一个元素，若采用 **顺序存储结构**，则平均需要移动（）个元素；若采用 **单链表存储**，则平均需要移动（）个元素。 A、1 B、(n-1)/2 C、logn D、n A、0 B、1 C、(n-1)/2 D、n/2 ### 答案 B A，因为是单链表，不需要移动元素，只需要改指针 原文出处：http://www.malaoshi.top/show_1GW2k45p6iAw.html