• 解决顺序存储结构不足的问题
    • 顺序存储结构最大的缺点是插入和删除时需大量移动元素，其原因在于相邻两元素的存储位置也相邻。为了解决这一问题提出链式存储结构。
  • 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，存储元素既可以是连续的，也可以是不连续的。这意味着这些数据元素可以存在于内存未被占用的任意位置。
  • 在链式结构中，除了要存数据元素信息外，还要存储它的后继元素的存储地址。
    • 为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系，对数据元素ai来说除了存储本身信息以外，还需存储一个指示其直接后继的信息。我们把存储元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域存储的信息称为指针或者链。这两部分信息组成数据元素ai的存储映象，称为结点（Node）。
    • n个结点链结成一个链表，此链表的每个结点只包含一个指针域，所以叫做单链表。
    • 头指针：链表中的第一个结点的存储位置。
    • 头结点：在单链表的第一个结点前附设一个结点。头结点可以不存储任何信息，也可以存储如线性表的长度等附加信息。头结点的指针域存储指向第一个结点的指针。
  • 至此，我们也就知道，结点是由存放数据元素的数据域和存放后继结点地址的指针域组成。
  • 顺序存储结构与单链表对比：
    • 在查询时，顺序存储结构的时间性能O（1），单链表O（n）
    • 在插入和删除时，顺序存储结构的时间性能O（n），单链表O（1）
    • 单链表的空间性能强于顺序存储结构，无需预分配存储空间。