典型应用与总结
典型应用
- 作为栈、队列、字符串等数据结构的基础
- 任务队列、浏览历史、购物车、文本编辑器的撤销/重做等
| 应用场景 | 推荐结构 |
|---|---|
| 需要频繁随机访问 | 顺序表 |
| 需要频繁插入删除 | 链表 |
易错点小贴士
单链表插入时，“先接后断”的顺序不能颠倒：必须先将新结点 s 的 next 指向 p 的后继，再让 p 的 next 指向 s。若顺序颠倒，会丢失后继结点。
总结
术语对照表
| 中文术语 | 英文术语 | 说明 |
|---|---|---|
| 线性表 | Linear List | 相同类型元素的有限序列 |
| 顺序表 | Sequential List | 用连续存储单元存储的线性表 |
| 链表 | Linked List | 用指针连接结点存储的线性表 |
| 单链表 | Singly Linked List | 每个结点只有一个后继指针 |
| 双向链表 | Doubly Linked List | 每个结点有前驱和后继两个指针 |
| 循环链表 | Circular Linked List | 首尾相连的链表 |
| 头结点 | Head Node | 链表第一个结点前附加的辅助结点 |
核心要点
- 顺序表随机访问 ，插入删除 ；链表随机访问 ，插入删除 （定位后）
- 单链表插入必须”先接后断”
- 双向链表支持双向遍历，空间开销更大
- 循环链表可从任一结点出发遍历全部结点