典型应用与总结

前面两节讲清了顺序表与链表的存储差异,这一页把它们放回真实选择:任务队列、浏览历史、购物车、编辑器的撤销重做,底层都是线性表,只是「要不要频繁随机访问」决定了该选顺序表还是链表。最后的易错点提醒单链表插入时「先接后断」的顺序不能颠倒,这是最容易写错的一行代码。

典型应用

  • 作为其他数据结构的基础:栈、队列、字符串、稀疏矩阵的链式存储,本质上都是在链表结点上换不同的连接规则。
  • 任务队列 / 浏览历史 / 购物车:这些场景里元素会频繁在两端增删,中间很少按序号访问,链表(或以链表为基础的队列、栈)能避免顺序表搬移元素的代价。
  • 文本编辑器的撤销与重做:每次编辑生成一条记录,用栈组织就能自然支持「撤销最近一次、恢复被撤销的操作」。
应用场景推荐结构原因
需要频繁随机访问顺序表下标到地址是一次乘法加法,访问 O(1)O(1)
需要频繁插入删除链表已知前驱即可 O(1)O(1) 插入删除,不必搬移后续元素
只在两端操作双端链表两端都能 O(1)O(1) 插入与删除
元素个数频繁变化且要求连续存储顺序表链表有结点额外开销,且缓存局部性差

术语小结

中文术语英文术语要点
顺序表Sequential List元素存放在一段连续空间中,按下标计算地址
链表Linked List结点由数据域与指针域组成,靠指针串联
首元结点First Node链表的第一个结点,指针域指向它
尾元结点Last Node链表的最后一个结点,指针域为空
头指针Head Pointer指向首元结点的指针,链表的入口
头结点Head Node附设在首元结点之前的结点,便于统一空表与插入删除操作
长度Length链表中结点的个数

易错点小贴士

另外两个高频错误:一是带头结点与不带头结点混用——带头结点时 p 指向头结点,插入的第一个元素要插在头结点之后;不带头结点时则要考虑空表这一种特例。二是判断表空的条件:带头结点时空表是 head->next == NULL,不带头结点时是 head == NULL。

发现内容有问题?

告诉我们哪里需要改进。