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 顺序表和链表的应用

  • 多项式相加适合用顺序表
  • 稀疏多项式适合用链表
  • 图书管理系统