线性表

什么是线性表

将具有“一对一”关系的数据“线性”地存储到物理空间中，这种存储结构就称为线性表。

使用线性表存储的数据，如同数组中存储数据那样，要求数据类型必须一致。

存储结构和链式存储结构

线性表存储结构可以分为顺序存储结构和链式存储结构。

前驱和后继

数据结构中，一组数据的每个个体被称为“数据元素”（简称“元素”）。

某一元素的左侧相邻元素称为“直接前驱”，位于此元素左侧的所有元素统称为“前驱元素”；某一元素的右侧相邻元素称为“直接后继”，位于此元素右侧的所有元素统称为“后继元素”。

顺序表

顺序表存储数据时，会提前申请一整块足够大小的物理空间，然后将数据一次性存储起来，存储时做到数据元素之间不留一丝缝隙。

顺序表存储数据使用的是数组。

顺序表的初始化

见代码。

顺序表的基本操作

见代码。

链表（单向链表）

与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。

数据元素随机存储，并通过指针表示数据之间逻辑关系的存储结构就是链式存储结构。

链表的结点

链表中每个数据的存储都由以下两部分组成：

数据元素本身，其所在的区域称为数据域
指向直接后继元素的指针，所在的区域称为指针域

头结点、头指针和首元结点

一个完整的链表需要由以下几部分构成：

头指针：一个普通的指针，它的特点是永远指向链表第一个结点的位置。
结点

l 头结点：就是一个不存放任何数据的空结点，通常作为链表的第一个结点。对于链表来说，头结点不是必须的，它的作用只是为了解决某些实际问题。

l 首元结点：由于头结点的缘故，链表中称第一个存有数据的结点为首元结点。首元结点只是对链表中第一个存有数据结点的一个称谓，没有实际意义。

l 其他结点：链表中的其他结点

注意：链表中有头结点时，头指针指向头结点；反之，若链表中没有头结点，则头指针指向首元结点。

链表的初始化

见代码。

链表的基本操作

见代码。

顺序表和链表的优缺点

顺序表和链表同属于线性表，但数据的存储结构有本质的不同：

l 顺序表存储数据，需要预先申请一整块足够大的存储空间，然后将数据按照次序逐一存储，数据之间紧密贴合，不留一丝缝隙。

l 链表的存储方式与顺序表截然相反，什么时候存储数据，什么时候才申请存储空间，数据之间的逻辑关系依靠每个数据元素携带的指针维持。

基于不同的存储结构，顺序表和链表有以下不同：

开辟空间的方式

顺序表存储数据实行的是“一次开辟，永久使用”，即存储数据之前先开辟好足够的存储空间，空间一旦开辟后期无法改变大小（使用动态数组的情况除外）。

而链表则不同，链表存储数据时一次只开辟存储一个结点的物理空间，如果后期需要还可以再申请。

因此，若只从开辟空间的角度去考虑，当存储数据的个数无法提前确定，又或是物理空间使用紧张以致无法一次性申请到足够大小的空间时，使用链表更有助于问题的解决。

空间利用率

从空间利用率的角度上看，顺序表的空间利用率显然要比链表高。

这是因为，链表在存储数据时，每次只申请一个结点的空间，且空间的位置是随机的。这种申请存储空间的方式会产生很多空间碎片，一定程度上造成了空间浪费。此外，由于链表中每个数据元素都至少携带一个指针，因此，链表对所申请空间的利用率也没有顺序表高。

空间碎片：指某些容量很小（1KB 甚至更小）以致无法得到有效利用的物理空间。

时间复杂度

根据顺序表和链表存储结构上的差异，问题类型主要分为以下两类：

l 问题中主要涉及访问元素的操作，元素的插入、删除和移动操作极少

l 问题中主要涉及元素的插入、删除和移动操作，访问元素的操作极少

第一类问题适合使用顺序表，因为，顺序表中存储的元素可以使用数组下标直接访问，无需遍历整个表，因此使用顺序表访问元素的时间复杂度是 O(1)；而在链表中访问数据元素，需要从表头依次遍历，直到找到指定结点，时间复杂度为 O(n)。

第二类问题适合使用链表。链表中数据元素之间的逻辑关系靠的是结点之间的指针，在需要在链表中某处插入或者删除结点时，只需改变相应的结点的指针指向即可，无需大量移动元素，因此链表中插入、删除或移动数据所耗费的时间复杂度是 O(1)
；而顺序表中，插入、删除或移动数据可能会牵涉到大量元素的整体移动，因此时间复杂度至少为 O(n)。

静态链表

静态链表，也是线性存储结构的一种，它兼顾了顺序表和链表的优点于一身，可以看做是顺序表和链表的升级版。

使用静态链表存储数据，数组全部存储在数组中（和顺序表一样），但存储位置是随机的，数据之间“一对一”的逻辑关系通过一个整型变量（称为“游标”，和指针功能类似）维持（和链表类似）。

静态链表中的结点

静态链表中的结点，至少包含以下 2 部分信息：

数据域：用于存储数据元素的值
游标：就是数组下标，表示直接后继元素所在数组中的位置

备用链表

备用链表的作用是回收数组中未使用或之前使用过（目前未使用）的存储空间。也就是说，静态链表在数组申请的物理空间中，存有两个链表，一条连接数据，一条连接数组中未使用的空间。

通常，备用链表的表头位于数组下标为 0（a[0]）的位置，以便数据链表添加新数据时使用。若静态链表中下标为 0 的位置上存有数据，则证明数组已满。

静态链表的实现

见代码。

静态链表基本操作

见代码。

静态链表和动态链表的区别

静态链表和动态链表的共同点是，数据之间“一对一”的逻辑关系都是依靠指针（静态链表中称“游标”）来维持。

l 静态链表

使用静态链表存储数据，需要预先申请足够大的一整块内存空间，也就是说，静态链表存储数据元素的个数从其创建的那一刻就已经确定，后期无法更改。比如，如果创建静态链表时只申请存储 10 个数据元素的空间，那么在使用静态链
表时，数据的存储个数就不能超过 10 个，否则程序就会发生错误。不仅如此，静态链表是在固定大小的存储空间内随机存储各个数据元素，这就造成了静态链表中需要使用另一条链表（通常称为”备用链表”）来记录空闲存储空间的位置，
以便后期分配给新添加元素使用。这意味着，如果你选择使用静态链表存储数据，你需要通过操控两条链表，一条是存储数据，另一条是记录空闲空间的位置。

l 动态链表

使用动态链表存储数据，不需要预先申请内存空间，而是在需要的时候才向内存申请。也就是说，动态链表存储数据元素的个数是不限的，想存多少就存多少。同时，使用动态链表的整个过程，你也只需操控一条存储数据的链表。当表中添
加或删除数据元素时，你只需要通过 malloc 或 free 函数来申请或释放空间即可，实现起来比较简单。

循环链表

把链表的两头连接，使其成为了一个环状链表，称为循环链表。

注意：虽然循环链表成环状，但本质上还是链表，因此在循环链表中，依然能够找到头指针和首元结点等。循环链表和普通链表相比，唯一的不同就是循环链表首尾相连，其他都一样。

循环链表实现约瑟夫环

见代码。

双向链表

虽然使用单链表能
100%解决逻辑关系为“一对一”数据的存储问题，但在解决某些特殊问题时，单链表并不是效率最优的存储结构，比如，如果算法中需要大量地查找某指定结点的前驱结点，使用单链表无疑是灾难性的，因为单链表更适合“从前往后”找，而“从后往前”找并不是它的强项。

双向，指的是各结点之间的逻辑关系是双向的，但通常头指针只设置一个。

双向链表的结点包含以下信息：

指针域：用于指向当前结点的直接前驱结点
数据域：用于存储数据元素
指针域：用于指向当前结点的直接后继结点

双向链表的创建

见代码。

双向链表基本操作

见代码。

双向循环链表

单链表通过首尾连接可以构成单向循环链表。

双向链表也可以进行首尾连接，构成双向循环链表。

当问题中涉及到需要“循环往复”地遍历表中数据时，就需要使用双向循环链表。例如，前面章节我们对约瑟夫环问题进行了研究，其实约瑟夫环问题有多种玩法，每次顺时针报数后，下一轮可以逆时针报数，然后再顺时针……一直到剩下最后一个人。解决这个问题就需要使用双向循环链表结构。

双向循环链表的创建

见代码。