大话数据结构-线性表（2）

1.线性表的链式存储结构

1.1 顺序存储结构不足的解决办法

线性表采用顺序存储方式时，其主要弊端在于执行插入与删除操作时需迁移大量数据元素，这一过程显然会耗费较多的时间资源。本部分内容将探讨链式存储结构，该结构能够有效应对上述问题。

线性表的链式存储结构具有显著特征，即采用一组任意的存储单元来存放线性表中的数据元素。这些存储单元既可以是连续的，也可以是离散的，从而使得数据元素可以分布在内存中任何未被占用的位置。

在传统的顺序存储结构中，每个数据元素只需保存自身的相关信息即可。而在链式存储结构中，除了保存数据元素的信息之外，还需记录其后续元素的存储地址。

因此，为表示每个数据元素a(i)与其直接后继a(i+1)之间的逻辑关联，在存储a(1)时不仅要保留其自身信息，还需附加一个用于指示其直接后继位置的信息。这部分用于保存数据元素信息的区域被称为数据域；而用于保存直接后继位置信息的部分则称为指针域。指针域所包含的内容通常被称为指针或链。这两部分共同构成了元素a(i)在存储空间中的映像，统称为结点。若每个结点仅包含一个指针域，则该结构被称为单链表。单链表正是通过各