线性表的定义
线性表为 $n$ ($n \ge 0$) 个数据元素的有限序列。记为 $$L = (a_1, a_2, \cdots, a_i, \cdots, a_n)$$
其中 $L$ 为表名，$a_i$ 为表中的元素，是不可再分的源自数据，亦称为结点或记录。 $n$ 是表中元素的个数，称为表长。当 $n=0$ 时，称为空表。
线性表中的第一个元素称为 表头（head），最后一个元素称为 表尾（tail）。
线性表的特点
- 有穷性：线性表中元素个数有限。
- 有序性：线性表中元素有序，即元素之间存在一对一的前驱后继关系。
- 表中相邻的两个元素 $a_i, a_{i+1}$ 构成序对，$a_i$ 是 $a_{i+1}$ 的直接前趋，$a_{i+1}$ 是 $a_i$ 的直接后继。
- 存在唯一的第一个元素（表头）和最后一个元素（表尾）。
- 相同性：线性表中的元素类型相同。
顺序表
- 既可以顺序访问，也可以随机访问（即通过下标访问）。
- 通过数组实现，可以是静态数组或动态数组。
- 数组的大小要大于等于线性表的长度。
- 第 $i$ 个元素存储在第 $i - 1$ 个物理位置上，即数组下标为 $i - 1$ 的位置。
设顺序表的起始存储位置为 $LOC(1)$，第 $i$ 个元素的存储位置为 $LOC(i)$，则有： $$LOC(i) = LOC(1) + (i - 1) \times sizeof(DataType)$$
顺序表的性能
| 操作 | 时间复杂度 | 空间复杂度 | 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|---|---|
初始化initList |
$O(1)$ | $O(1)$ | 清空clearList |
$O(1)$ | $O(1)$ |
求长度length |
$O(1)$ | $O(1)$ | 取值getElem |
$O(1)$ | $O(1)$ |
插入insert |
$O(n)$ | $O(1)$ | 删除delete |
$O(n)$ | $O(1)$ |
查找search |
$O(n)$ | $O(1)$ | 复制copyList |
$O(n)$ | $O(n)$ |
单链表
单链表是一种链式存储结构，由一系列结点组成。每个结点包括两部分：数据域data和指针域link。数据域存储数据元素，指针域存储下一个结点的地址。
链表中的最后一个节点没有后继，其指针域为 NULL。
单链表的特点
- 表中的数据元素的逻辑顺序和物理顺序不一定相同。
- 单链表的长度可以动态变化。
- 遍历和查找只能从头指针指示的第一个结点开始，逐个结点依次查找。
- 即不能随机访问，只能顺序访问。
- 插入和删除操作只需修改指针域，不需要移动结点。
- 由于链接表的每个结点带有指针域，所以占用的存储空间比顺序表大。
头节点：链表中第一个结点称为头节点，它是头指针指向的结点。头节点不存储数据，只是为了方便操作而引入的。
尾结点：链表中最后一个结点称为尾结点，为了方便插入到尾部而建立，其指针域为 NULL
单链表的性能
| 操作 | 时间复杂度 | 空间复杂度 | 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|---|---|
初始化initList |
$O(1)$ | $O(1)$ | 清空clearList |
$O(n)$ | $O(1)$ |
求长度length |
$O(n)$ | $O(1)$ | 取值getElem |
$O(n)$ | $O(1)$ |
插入insert |
$O(n)$ | $O(1)$ | 删除delete |
$O(n)$ | $O(1)$ |
查找search |
$O(n)$ | $O(1)$ | 复制copyList |
$O(n)$ | $O(n)$ |
循环链表
循环链表是一种特殊的单链表，其尾结点指向首结点，形成一个环。
可以带头结点，也可以不带头结点。 若带头结点，遍历到头节点的时候需要跳过。
双向链表
拥有两个指针域lLink和rLink，分别指向前驱和后继。
顺序表和单链表的比较
存储方面
- 顺序表的存储密度高，存储密度为 $1$，而链表的存储密度小于 $1$。
- 顺序表的存储空间是静态分配的，链表的存储空间是动态分配的。
存取方面
- 顺序表支持随机存取，时间复杂度为 $O(1)$，而链表只支持顺序存取，时间复杂度为 $O(n)$。
- 插入和删除操作，顺序表的时间复杂度为 $O(n)$，链表的时间复杂度为 $O(1)$。
安全方面
在顺序表的情形，只要知道数组的名字和下标，就可以访问任何元素。
而在单链表中如果找不到结点的地址，结点所保护的数据就是安全的。
故单链表的安全保密性比顺序表好。