链表

• 基本概念：

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的；链表存在多种形式

循环链表

• 基本实现和特性：

1. 尾结点指针指向头结点的链表
2. 可以是单链表，也可以是双链表

• 操作
  1.有点是从链表到链头十分方便
  2.经典问题：约瑟夫问题

单链表

• 基本实现和特性
  每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点指针地址的指针域，只有一个后继结点
• 操作
  1.建立链表
  2.插入结点
  3.删除结点
  4.遍历链表
  5.查找结点——时间复杂度O(n)
  双向链表
• 基本概念和特性：
  不同于单向链表只有一个方向，结点只有一个后继指针next指向后面的结点；
  双向链表，支持两个方向，每个结点不止有一个后继指针next指向后面的结点，还有一个前驱指针prev指向前面的结点；
  占用更多空间的同时插入和删除效率更高。
• 操作：
  插入删除快速
  1.删除给定指针指向的结点，直接获取前驱结点，不要遍历，时间复杂度为O(1)，插入的情况类似删除；
  2.实际使用例子：LinkedHashMap
  3.空间换时间的思想
  静态链表
• 基本概念和特性
  用数组描述的链表，即称为静态链表