上一篇
线性表链式存储结构是什么？链表和顺序表的区别
线性表的链式存储结构，通常被称为链表（Linked List），是一种通过指针将一组任意存储单元（可以是连续的，也可以是不连续的）链接起来以表示数据元素之间逻辑关系的存储方式，与顺序表（数组）不同，链表不需要在内存中开辟一块连续的存储空间，而是通过每个节点中附加的指针域来指示下一个节点的地址,从而构建起数据元素之间的线性关系。
节点结构与基本组成
链表的基本组成单位是节点（Node），每个节点至少包含两个部分：数据域和指针域，数据域用于存储数据元素本身的信息,而指针域则用于存储指向下一个节点的地址。
| 组成部分 | 功能描述 | 示例类型 |
|---|---|---|
| 数据域 (Data) | 存储实际的数据元素，如整数、字符或复杂对象。 | int, char, Student |
| 指针域 (Next) | 存储下一个节点的内存地址，若为最后一个节点，该域通常指向空（NULL）。 | Node, Link |
在单链表中，每个节点只有一个指针域指向后继节点；而在双链表中，节点包含两个指针域，分别指向前驱节点和后继节点,这使得双向遍历成为可能。
头指针与头节点的概念
为了便于对链表进行操作，通常引入头指针和头节点的概念，尽管它们在物理实现上有所区别,但在逻辑上对操作者而言至关重要。
- 头指针：指向链表中第一个节点（即首元节点）的指针，无论链表是否为空，头指针始终存在，它是访问整个链表的入口，如果链表为空，头指针指向 NULL。
- 头节点：在首元节点之前附加的一个节点，其数据域通常不存储有效数据（或存储链表长度等元数据），指针域指向首元节点，引入头节点的主要好处是统一了空表和非空表的处理逻辑，使得在链表头部插入或删除节点时,不需要特殊判断头指针是否变化。
链式存储的主要操作
链表的核心优势在于其动态性，插入和删除操作的时间复杂度为 O(1)（前提是已知操作位置的前驱节点），而顺序表则需要移动大量元素,以下是单链表中最常见的两种操作逻辑：
插入操作
在链表中插入一个新节点 p 到已知节点 a 之后，关键在于修改指针的指向，且必须注意顺序,以防止断链。
- 将新节点 p 的 next 指针指向 a 的下一个节点（即 p->next = a->next）。
- 将 a 的 next 指针指向新节点 p（即 a->next = p）。
若顺序颠倒，先执行第二步，则 a 原来的后继节点地址将丢失,导致链表断裂。
删除操作
删除已知节点 a 的后继节点 b,同样需要谨慎处理指针。
- 定义一个临时指针 temp 指向待删除节点 b（temp = a->next）。
- 将 a 的 next 指针指向 b 的后继节点（即 a->next = b->next）。
- 释放节点 b 的内存空间（free(temp) 或 delete temp）。
优缺点分析
| 特性 | 链式存储结构 (链表) | 顺序存储结构 (数组) |
|---|---|---|
| 存储空间 | 动态分配，无碎片浪费，但需额外空间存储指针。 | 静态或动态连续分配，无额外指针开销。 |
| 插入/删除 | 效率高，O(1) 时间复杂度（已知位置）。 | 效率低，O(n) 时间复杂度，需移动元素。 |
| 随机访问 | 不支持，必须从头遍历，O(n) 时间复杂度。 | 支持，通过下标直接访问，O(1) 时间复杂度。 |
| 内存利用率 | 较低，因指针占用额外空间。 | 较高，仅存储数据本身。 |
| 适用场景 | 数据量不确定、频繁插入删除的场景。 | 数据量固定、频繁随机访问的场景。 |
循环链表与双向链表
为了克服单链表只能单向遍历且无法快速找到前驱节点的缺点,衍生出了两种常见变体：
- 循环链表：将单链表的尾节点指针域从 NULL 改为指向头节点（或首元节点），形成一个环，这种结构在实现约瑟夫环等问题时非常高效,因为可以从任意节点出发遍历整个链表。
- 双向链表：每个节点包含前驱指针（prior）和后继指针（next），这使得可以从任意节点向前或向后遍历，删除节点时无需再寻找前驱节点,但增加了插入和删除时的指针修改复杂度。
相关问题与解答
问题 1：为什么在链表中插入或删除节点的时间复杂度是 O(1)，而在顺序表中是 O(n)？
解答：
在链表中，一旦通过遍历找到了目标位置的前驱节点，插入或删除操作仅涉及修改少数几个指针的指向（通常只需修改 1-2 个指针），不涉及数据元素的物理移动，因此时间复杂度为 O(1)，而在顺序表中，由于数据元素在内存中是连续存储的，为了保持连续性，插入或删除一个元素后，其后继的所有元素都必须向前或向后移动一位以填补空缺或腾出空间，在最坏情况下（如在表头插入或删除），需要移动 n-1 个元素，因此时间复杂度为 O(n)。
问题 2：如果链表没有头节点，在第一个节点之前插入新节点时，需要如何处理头指针？
解答：
如果没有头节点，头指针直接指向第一个数据节点，当在第一个节点之前插入新节点时，新节点将成为新的首元节点，因此头指针必须指向这个新节点，在函数实现中，通常需要将头指针作为引用传递（在 C++ 中为 Node& head，在 C 语言中为 Node head），或者返回新的头指针，以便调用者能够更新外部的头指针变量，使其指向新插入的节点，如果不这样做，头指针仍将指向旧的第一个节点，导致新插入的节点无法被访问,造成内存泄漏或逻辑错误。
