链表介绍

• 链表是一种通过指针串联在一起的线性结构，链表的入口节点称为链表的头结点/head。链表的各个节点不一定是连续存储.链表内还有一种特殊的节点称为哨兵（Sentinel）节点，也叫做哑元（ Dummy）节点，它不存储数据，通常用作头尾，用来简化边界判断

• 链表分类：

  • 单链表：每一个节点由两部分组成，一个是数据域一个是指向下一个节点的指针的指针域，最后一个节点的指针域指向null（空指针的意思）。只能向后查询，不能自我删除，需要靠辅助节点temp（待删除节点的前一个节点）
  • 双链表：比单链表多一个指向上一个节点的指针域。向前后查询都可以。可以自我删除，
  • 环形链表：首尾相连。可以用来解决约瑟夫环问题。

• 使用场景

  • 列表、队列和堆栈实现。
  • 循环列表。
  • 模拟现实世界中的对象，例如火车
  • 链地址法处理哈希冲突。
  • 图的邻接列表的实现

• 算法复杂度