第二章：线性表（链式表示）
前面我们讨论了线性表的顺序表示法——顺序表。虽然顺序表能实现随机存储，但在初始化时需要申请一大块连续的存储空间。进行插入和删除操作时，可能需要移动大量元素，导致时间复杂度较高。接下来，我们将探讨线性表的另一种存储结构：链式存储。
1. 单链表的定义
线性表的链式存储又称为单链表，它是通过一组任意的存储单元来存储线性表中的数据元素。数据元素存储在任意位置，不一定连续，通过指针实现线性逻辑关系。
在单链表中，一个结点包含了数据元素的数据域和下一个结点（数据元素）地址的指针域。
1.1 单链表的基本结构
单链表有两种创建方式：无头结点的单链表和有头节点的单链表。
- 有头节点的单链表：头节点的数据域一般不存储数据，其指针域存储第一个结点的地址。这种结构的优点在于无论是第一个位置还是其他位置的插入或删除操作都能保持一致。
2. 单链表的基本操作
2.1 头插法建立
时间复杂度：O(n)
2.2 尾插法建立
时间复杂度：O(n)
按序号查找和按值查找
无论是按序号查找还是按值查找，都需要遍历整个单链表。
2.3 插入结点
2.4 删除结点
3. 特殊链表
3.1 双链表
双链表的每个结点中有一个指针指向它的前驱结点，这样在执行插入、删除等需要知道前驱结点的操作时，可以直接通过指针找到前驱节点，时间复杂度为O(1)。
双链表的插入和删除操作
3.2 循环链表
循环链表是将单链表的最后一个结点的指针指向头节点，从而形成一个环。这样只需要一个尾指针就能找到整个链表，提高了效率。
静态链表
静态链表是使用数组来实现的链式存储结构。在静态链表中，每个结点既有自己的数据部分，还需要存储下一个结点的位置信息。静态链表的存储实现使用的是结构体数组，包含数据域和游标（存放下一个结点在数组中的位置下标）。