线性表

Nahida大约 4 分钟

定义

线性表是最常用且最简单的一种数据结构。
线性表是n个数据元素的有限序列。
若将线性表记为 $(a_1, ..., a_{i-1}, a_i, a_{i+1}, ..., a_n)$ , 则称： $a_{i-1}$ 是 $a_i$ 的直接前驱， $a_{i+1}$ 是 $a_i$ 的直接后继。

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。
线性表的第i个数据元素 $a_i$ 的存储位置为： $LOC(a_i) = LOC(a_1) + (i - 1) * l$ ，其中 $l$ 是每个元素占用的存储单元的个数。
只要确定了存储线性表的起始位置，线性表任何一个数据元素都可以随机读取，即线性表的顺序存储结构是一种随机存取的存储结构。

线性表的链式存储结构不需要逻辑上相邻的元素存储在相邻的物理位置上，不可随机存取。下面将以新的章节介绍链表。

线性链表，也称为单链表。

线性表的链式存储结构是用一组任意存储单元存储线性表的数据元素。
每个数据元素除了存储本身的信息之外，还需要存储一个指示其直接后继的信息。即包括两个域： 数据域 和 指针域。
链表的最后一个结点的指针为空（NULL）。
可以在单链表的第一个结点前增加一个结点，称为头结点。这个结点的数据域可以没有信息，当然也可以用来存储线性表的长度等一些信息，而指针域指向第一个元素结点的存储位置。

单链表存储结构实现：

单链表获取第i个元素的值的实现：

从起始位置开始，不断访问next，直到计数器归零。

以上算法最坏情况下需要 $n$ 次才能找到结果，因此时间复杂度为 $O(n)$ 。

单链表插入元素的实现：

从起始位置开始不断访问next，到要插入的位置，在它和它之前的一个结点中间创建一个新的结点，将前一个元素的next指向新结点，新结点指向原本前一个元素的next，并写入data到新结点中。

单链表删除元素的实现：

在单链表中，每个结点只能找到直接后继的结点，而无法找到直接前驱的结点。单链表寻找下一个结点的时间复杂度为 $O(1)$ ，而寻找上一个结点的时间复杂度为 $O(n)$ 。
双向链表的结点中有两个指针域，一个指向直接后继，另一个指向直接前驱。

循环链表的实现：