2/8 线性表(下)
2.5 线性表的链式表示和实现
2.5.3 下面介绍循环链表:
最大的优点是:从表中任一结点出发均可找到表中其他结点
- 终止条件: 判断指针是否等于头指针
对循环链表进行优化,更方便寻找首尾位置
两个带尾指针的循环链表的合并:时间复杂度是O(1)
2.5.4 下面介绍双向链表:
双向列表中仅插入和删除时,因为需要同时修改两个方向上的指针,两者的操作时间复杂度均为O(n)。和单链略有不同。
- 双向链表的插入:
- 双向列表的删除,仅删除O(1),但是查找O(n)
2.5.5 链表的比较
2.6 顺序表和链表的比较
2.7 线性表的应用
2.8 顺序表和链表的应用
- 多项式相加适合用顺序表
- 稀疏多项式适合用链表
- 图书管理系统
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ClancyCC!
评论