典型应用与总结
前面两节讲清了顺序表与链表的存储差异,这一页把它们放回真实选择:任务队列、浏览历史、购物车、编辑器的撤销重做,底层都是线性表,只是「要不要频繁随机访问」决定了该选顺序表还是链表。最后的易错点提醒单链表插入时「先接后断」的顺序不能颠倒,这是最容易写错的一行代码。
- 作为其他数据结构的基础:栈、队列、字符串、稀疏矩阵的链式存储,本质上都是在链表结点上换不同的连接规则。
- 任务队列 / 浏览历史 / 购物车:这些场景里元素会频繁在两端增删,中间很少按序号访问,链表(或以链表为基础的队列、栈)能避免顺序表搬移元素的代价。
- 文本编辑器的撤销与重做:每次编辑生成一条记录,用栈组织就能自然支持「撤销最近一次、恢复被撤销的操作」。
| 应用场景 | 推荐结构 | 原因 |
|---|---|---|
| 需要频繁随机访问 | 顺序表 | 下标到地址是一次乘法加法,访问 |
| 需要频繁插入删除 | 链表 | 已知前驱即可 插入删除,不必搬移后续元素 |
| 只在两端操作 | 双端链表 | 两端都能 插入与删除 |
| 元素个数频繁变化且要求连续存储 | 顺序表 | 链表有结点额外开销,且缓存局部性差 |
| 中文术语 | 英文术语 | 要点 |
|---|---|---|
| 顺序表 | Sequential List | 元素存放在一段连续空间中,按下标计算地址 |
| 链表 | Linked List | 结点由数据域与指针域组成,靠指针串联 |
| 首元结点 | First Node | 链表的第一个结点,指针域指向它 |
| 尾元结点 | Last Node | 链表的最后一个结点,指针域为空 |
| 头指针 | Head Pointer | 指向首元结点的指针,链表的入口 |
| 头结点 | Head Node | 附设在首元结点之前的结点,便于统一空表与插入删除操作 |
| 长度 | Length | 链表中结点的个数 |
单链表插入时,「先接后断」的顺序不能颠倒:必须先将新结点 s 的 next 指向 p 的后继,再让 p 的 next 指向 s。若顺序颠倒,会丢失后继结点。
另外两个高频错误:一是带头结点与不带头结点混用——带头结点时 p 指向头结点,插入的第一个元素要插在头结点之后;不带头结点时则要考虑空表这一种特例。二是判断表空的条件:带头结点时空表是 head->next == NULL,不带头结点时是 head == NULL。
