链表：解决顺序存储的缺点，实现灵活存储

数据结构与算法的第2章介绍了链表这种存储结构，并详细讨论了顺序存储的缺点，以及链表的特点和存储结构。顺序存储需要移动大量元素，同时需要预分配最大存储空间，导致存储空间不能得到充分利用，而且表的容量难以扩充。为了解决这些问题，可以采用链表这种存储结构。 链表是用一组任意的存储单元存储线性表的元素。为了表示每个元素和其直接后继之间的逻辑关系，除了存储元素本身的信息外，还需要存储一个指向直接后继的信息。这两部分信息组成了数据元素的存储映射，也称为结点。结点包括数据域和指针域两个部分，数据域存储具体的数据元素信息，指针域存储直接后继存储位置的信息。 在链表中，n个结点通过指针域链接起来，形成了一个链表，这就是线性表的链式存储结构。由于每个结点中只包含一个指针域，所以也称为线性链表或单链表。例如，线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)的线性链表存储结构如下图所示： ``` 存储地址 数据域 指针域 1 LI 4 3 QIAN 31 13 SUN 119 25 WANG NULL ``` 这个链表中的每个结点都有一个数据域存储具体的数据元素信息，并通过指针域链接到下一个结点。例如，数据域为"LI"的结点的指针域值为4，表示其直接后继存储位置在存储地址为4的结点。 链表这种存储结构相比于顺序存储具有很多优点。首先，链表不需要预分配最大存储空间，可以根据需要动态分配存储空间，充分利用存储空间。其次，插入和删除操作在链表中非常高效，只需要修改指针域的值即可，而不需要移动大量元素。此外，链表还允许存储结构的容量动态扩充，只需要修改指针域的值即可添加新的结点。 但是，链表也存在一些缺点。首先，链表访问某个特定位置的元素时，需要从头结点开始，按照指针域的指向一个个寻找，所以时间复杂度较高。其次，链表需要额外的存储空间来存储指针域，占用了额外的存储空间。另外，由于链表中每个结点只有一个指针域，无法直接访问前驱结点，所以在进行某些操作时可能会不方便。 综上所述，链表是一种灵活、高效的存储结构，可以解决顺序存储的一些缺点。它的特点是每个结点通过指针域链接形成了一个链表，可以动态分配存储空间并且支持高效的插入和删除操作，但访问和查找操作较为耗时。在实际应用中，根据具体的需求和数据特点选择适合的存储结构，综合考虑各种因素来选择使用链表还是顺序存储。