软考-软件设计师:数据结构-线性结构-线性表-链表(链式存储)和单链表 作者:马育民 • 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