数据结构：线性表(list)

零个或多个数据元素的有限序列。

1. 定义

1.1 定义

序列，即元素之间是有序的
第一个元素无前驱，最后一个元素无后继，其他元素有且只有一个前驱，有且只有一个后继
有限的

1.2 数学定义

若将线性表记为 (a_1, ... , a_{i-1}, a_i, a_{i+1}, ..., a_n) \\ 则表中 a_{i-1} 领先于 a_i, a_i 领先于 a_{i+1}, \\ 称 a_{i-1} 为 a_i 的直接前驱元素， \\ a_{i+1} 为 a_i 的直接后继元素。 \\ 线性表元素的个数 n(n>0) 定义为线性表的长度，当 n=0 时，称为空表。

2. 线性表的抽象数据类型

ADT
ADT 线性表（List）
Data
  若将线性表记为 （a1, a2, ... , an）,每个元素的类型均为 DataType 。其中，除第一个元素a1外，每个元素都有且只有一个直接前驱元素，除了最后一个元素 an 外，每一个元素都有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
	InitList(*L): 初始化操作,建立一个空的线性表L。
	ListEmpty(L): 若线性表为空,返回true,否则返回false。
	ClearList(*L): 将线性表清空。
	GetElem(L,i,*e): 将线性表工中的第i个位置元素值返回给e。
	LocateElem(L,e): 在线性表工中查找与给定值e相等的元素,如果查找成功,返回该元素在表中序号表示成功；否						 则,返回0表示失败。
	ListInsert(*L,i,e): 在线性表工中的第i个位置插入新元素e。
	ListDelete(*L,i,*e): 删除线性表工中第i个位置元素,并用e返回其值。
	ListLength(L): 返回线性表工的元素个数。
endADT

3. 线性表的顺序存取

3.1 顺序存储结构定义与存储方法

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
存储方法：
- 初始化大小，占用固定的连续空间
- 使用高级语言中（如C， java）使用一维数组表示
线性表长度和数据长度
- 数据长度：指存储线性表的空间大小，初始化大小，固定大小（高级语言中可动态分配），
- 线性表长度：指线性表的数据长度，随着数据的插入和删除变化，必须小于或等于数据长度

3.2 寻址计算方式

假设一个数据元素占用的是 c 个存储单元，那么线性表中第 i+1 个双据元素的存储位置和第 i 个数据元素的存储位置满足下列关系（LOC表示获得存储位置的函数）。

由： LOC(a_{i+1}) = LOC(a_i)+1 \\ 可得： LOC(a_i)=LOC(a_1)+(i-1)*c

3.3 获取，插入和删除

3.3.1 获取

直接通过寻址获取，时间复杂度为 O(1)

3.3.2 插入和删除

变更相应节点，需要改节点以后所有节点进行变更（前进或者后退一步），时间复杂度为O(n)

3.4 顺序存取得优缺点

优点
- 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
- 可以快速地存取表中任一位置的元素
缺点
- 插入和删除操作需要移动大量元素
- 当线性表长度变化较大时，难以确定存储空间的容量
- 造成存储空间的“碎片”

4. 线性表的链式存取

4.1 结构定义

每一个元素称之为节点（Node）
每一个节点由数据域和指针域组成
- 数据域：存储数据元素信息
- 指针域：存储直接后继位置的域
n 个节点链节成一个链表，即称为链表
因为每个节点只有一个指针域，所以称之为单链表

4.2 头指针和头结点

头指针：
- 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
- 头指针具有标识作用，所以常用头指针冠以链表的名字
- 无论链表是否为空，头指针均不为空。头指针是链表的必要元素
头节点：
- 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）
- 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了
- 头结点不一定是链表必须要素

4.3 单链表的读取

获得链表第i个数据的算法思路：

声明一个结点p指向链表第一个结点，初始化 j 从1开始；
当 j<i 时，就遍历链表，让 p 的指针向后移动，不断指向下一结点，j 累加 1；
若到链表末尾 p 为空，则说明第 i 个元素不存在；
否则查找成功，返回结点 p 的数据。

最坏的情况时间复杂度为O(n)

4.4 单链表的插入和删除

单链表第 i 个数据插入结点的算法思路：：
1. 声明一结点 p 指向链表第一个结点，初始化j从1开始；
2. 当j < i时，就遍历链表，让 p 的指针向后移动，不断指向下一结点，j 累加1；
3. 若到链表末尾 p 为空，则说明第 i 个元素不存在；
4. 否则查找成功，在系统中生成一个空结点s；
5. 将数据元素e 赋值给 s->data；
6. 单链表的插入标准语句 s->next=p->next; p->next=s；
单链表第i个数据删除结点的算法思路：
1. 声明一结点p指向链表第一个结点，初始化 j 从 1 开始；
2. 当 j < i 时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j 累加1；
3. 若到链表末尾 p 为空，则说明第 i 个元素不存在；
4. 否则查找成功，将欲删除的结点 p->next 赋值给 q；
5. 单链表的删除标准语句p->next=q->next；
6. 将q结点中的数据赋值给e，作为返回；
单链表插入和删除一个节点的时间复杂度也是 O(n)
对于单个节点的操作来讲，单链表和顺序链表的时间复杂度并没有区别，但是如果一次性插入或者删除多个元素，单链表需要的时间更低

5. 顺序存取和链式存取得区别

存储分配方式
- 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
- 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
时间性能
- 查找
  - 顺序存储结构O(1)
  - 单链表O(n)
- 插入和删除
  - 顺序存储结构需要平均移动表长一半的元素，时间为 O(n)
  - 单链表在线出某位置的指针后，插入和删除时间仅为 O(1)
空间性能
- 顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生上溢
- 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制

6 其他链表结构

6.1 静态链表

静态链表是为了没有指针的高级编程语言实现单链表能力的方法

思路：
- 使用数据保存节点，节点需要包含数据和一个指向下个节点的数组下标（指针域）。

6.2 循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表（circular linked list）。

6.3 双向链表

双向链表（double linked list）是在单链表的每个结点中，再设置一个指向其前驱结点的指针。

目录