链表

#单链表

  • 单链表代码实现
  • 作为你相当熟悉的线性表结构，不必多言
  • 删除和插入的效率提升，但代价是丧失了随机存储能力，只能从头顺序访问
  • 插入删除时间复杂度O(n)

    • #双链表

  • 双链表代码实现
  • 与单链表的区别就是结构中多了一个指向上一个节点的prior指针
  • 可以从后往前遍历链表了
  • 在已知目标结点的情况下，插入和删除的时间复杂度变为O(1)
  • 原因很简单，毕竟知道了前驱节点，就不需要老老实实遍历节点了。

    • #循环链表

  • 与普通链表的区别就是末尾指针指向的是头结点
  • 形成一个环
  • 故在任何位置上的插入和删除操作都是等价的，无需判断是否达到表尾

    • #循环双链表

  • 在循环链表的基础上，增添了一个前驱指针

    • #静态链表

  • 分配一块连续空间用于
  • 结构上两个部分，一个数据，一个存地址的变量
  • 地址变量存入下一个地址
  • 额，总之就是静态，就是一块空间模拟链表