线性表

线性表的定义

线性表为 $n$ ($n\ge 0$) 个数据元素的有限序列。记为

$$L=(a_1,a_2,\cdots ,a_i,\cdots ,a_n)$$

其中 $L$ 为表名，$a_i$ 为表中的元素，是不可再分的源自数据，亦称为结点或记录。 $n$ 是表中元素的个数，称为表长。当 $n=0$ 时，称为空表。
线性表中的第一个元素称为 表头（head），最后一个元素称为 表尾（tail）。

线性表的特点

1. 有穷性：线性表中元素个数有限。
2. 有序性：线性表中元素有序，即元素之间存在一对一的前驱后继关系。

• 表中相邻的两个元素 $a_i,a_{i+1}$ 构成序对，$a_i$ 是 $a_{i+1}$ 的直接前趋，$a_{i+1}$ 是 $a_i$ 的直接后继。
• 存在唯一的第一个元素（表头）和最后一个元素（表尾）。

3. 相同性：线性表中的元素类型相同。

顺序表

1. 既可以顺序访问，也可以随机访问（即通过下标访问）。
2. 通过数组实现，可以是静态数组或动态数组。
3. 数组的大小要大于等于线性表的长度。
4. 第 $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。

单链表的特点

1. 表中的数据元素的逻辑顺序和物理顺序不一定相同。
2. 单链表的长度可以动态变化。
3. 遍历和查找只能从头指针指示的第一个结点开始，逐个结点依次查找。

• 即不能随机访问，只能顺序访问。

4. 插入和删除操作只需修改指针域，不需要移动结点。
5. 由于链接表的每个结点带有指针域，所以占用的存储空间比顺序表大。

头节点：链表中第一个结点称为头节点，它是头指针指向的结点。头节点不存储数据，只是为了方便操作而引入的。 尾结点：链表中最后一个结点称为尾结点，为了方便插入到尾部而建立，其指针域为 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$，而链表的存储密度小于 $1$。
2. 顺序表的存储空间是静态分配的，链表的存储空间是动态分配的。

存取方面

1. 顺序表支持随机存取，时间复杂度为 $O(1)$，而链表只支持顺序存取，时间复杂度为 $O(n)$。
2. 插入和删除操作，顺序表的时间复杂度为 $O(n)$，链表的时间复杂度为 $O(1)$。

安全方面

在顺序表的情形，只要知道数组的名字和下标，就可以访问任何元素。
而在单链表中如果找不到结点的地址，结点所保护的数据就是安全的。 故单链表的安全保密性比顺序表好。