数据结构-线性结构-链表

这是一篇关于链表的思维导图，主要内容包括：普通单链表，普通双链表，循环单链表，静态链表，循环双链表。

链表

• 普通单链表
  • 定义
  • 初始化
  • 插入
  • 删除
  • 查找
  • 建立
    • 头插法
    • 尾插法
  • 关于头结点
    • 头结点的好处
      • 由于第一个数据结点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理
      • 无论链表是否为空，其头指针都是指向头结点的非空指针(空表中头结点的指针域为空)，因此空表和非空表的处理也统一
    • 头结点 VS 头指针
      • 不管带不带头结点，头指针都始终指向链表的第一个结点
      • 头结点是带头结点的第一个结点，结点内通常不存储信息
  • 评价
    • 优点
      • 离散的小空间分配方便，改变容量方便
    • 缺点
      • 不可随机存取
      • 存储密度低
• 普通双链表
  • 定义
  • 初始化
  • 插入
  • 删除
• 循环单链表
  • 特点
    • 表尾结点的next指针指向头结点
  • 空表判断
    • L->next=L
  • 优点
    • 与普通单链表相比，可以从表中的任意一个结点开始遍历整个链表
  • 仅设尾指针的好处
    • 若设的是头指针，对在表尾插入元素需要 0(n)的时间复杂度
    • 若设的是尾指针r,r->next 即为头指针
    • 对在表头或表尾插入元素都只需要0(1)的时间复杂度
• 静态链表
  • 特点
  • 定义
  • 初始化
    • 所有next为-2，表示空结点
  • 插入操作
    • 找到一个空的结点，存入数据元素
    • 从头结点出发找到位序为i-1的结点
    • 修改新结点的next
    • 修改i-1号结点的next
  • 删除
    • 从头结点出发找到前驱结点
    • 修改前驱结点的游标
    • 被删除结点next设为-2
  • 评价
    • 优点
      • 增，删操作不需要大量移动元素
    • 缺点
      • 容量固定不变
      • 不能随机存取，只能从头结点开始依次往后查找
• 循环双链表
  • 特点
    • 除了让最后一个节点的后继指向第一个节点外，还要让头节点的前驱指向 最后一个节点
  • 空表判断
    • L->next=L->prior=L
  • 插入
  • 删除