数据结构——链表

链式存储结构

• 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻

有关术语

• 结点：数据元素的存储映像。由数据域和指针域两部分组成
  • 数据域：存储元素数值数据
  • 指针域：存储直接后继结点的存储位置
• 链表：n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构
  • 单链表
    • 结点只有一个指针域的链表，称为单链表或线性链表
  • 双链表
    • 有两个指针域的链表，称为双链表
  • 循环链表
    • 首尾相接的链表称为循环链表
• 头指针
  • 指向链表中第一个结点的指针
• 首元结点
  • 指链表中存储第一个数据元素a1的结点
• 头结点
  • 在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息
  • 设置头结点的好处
    • 便于首元结点的处理
      • 首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理;
    • 便于空表和非空表的统一处理
      • 无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

链表的特点

• 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
• 访问时只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等

链表的优缺点

• 优点
  • 数据元素的个数可以自由扩充
  • 插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高
• 缺点
  • 存储密度小
  • 存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问（顺藤摸瓜）