2.6 小结

线性表是最常用，也是最简单的数据结构。

线性表是一种可以在任意位置进行插入和删除操作，由n个同类型的数据元素组成的一种线性数据结构。线性表中的每个数据元素只有一个前驱元素且只有一个后继元素。其中，第一个数据元素没有前驱元素，最后一个数据元素没有后继元素。

线性表通常有两种存储方式：顺序存储和链式存储。采用顺序存储结构的线性表称为顺序表，采用链式存储结构的线性表称为链表。

顺序表中数据元素的逻辑顺序与物理顺序一致，因此可以随机存取。但是顺序表在插入元素和删除元素时，需要移动大量的数据元素。

链表中的结点由两部分组成：数据域和指针域。数据域存放元素值信息，指针域存放元素之间的地址信息。链表根据结点之间的链接关系分为单链表和双向链表，这两种链表又可以构成单循环链表、双向循环链表。单链表只有一个指针域，指针域指向直接后继结点。单链表的最后一个结点的指针域为空，循环链表的最后一个指针域指向头结点或链表的第一个结点。双向链表有两个指针域，一个指向直接前驱结点，另一个指向直接后继结点。

为了链表操作的方便，往往在链表的第一个结点之前增加一个结点，称为头结点。头结点的设置，在进行插入和删除操作时不需要改变头指针的指向，头指针始终指向头结点。

顺序表的算法实现比较简单，存储空间利用率高。但是需要预先分配好存储空间，插入和删除操作需要移动大量元素。而链表不需要事先确定存储空间的大小，插入和删除操作不需要移动大量元素，实现较为复杂。