线性表（二）
1. 简介
一种逻辑结构，相同数据类型的n个数据元素的有限序列，除第一个元素外，每个元素有且仅有一个直接前驱，除最后一个元素外，每个元素有且仅有一个直接后继。
2. 特点
1）元素个数有限
2）逻辑上元素有先后次序
3）数据类型相同
4）仅讨论元素间的逻辑关系
注：线性表是逻辑结构，顺序表和链表是存储结构。
3. 分类
4. 顺序存储
顺序表，使用数组实现，一组地址连续的存储单元，数组大小有两种方式指定，一是静态分配，二是动态扩展。
注：线性表从1开始，而数组从0开始。
4.1 插入
顺序表相关的操作跟数组有关，一般都是移动数组元素。以下图——插入为例：
4.2 删除
4.3 优缺点
5．链式存储
链表的定义是递归的，它或者为空null，或者指向另一个节点node的引用，这个节点含有下一个节点或链表的引用。
与顺序存储相比，允许存储空间不连续，插入删除时不需要移动大量的元素，只需修改指针即可，但查找某个元素，只能从头遍历整个链表。
5.1 单链表
5.1.1 添加
5.1.2 删除
5.1.3 单链表与顺序表分析
5.2 静态链表
对于没有指针的编程语言，可以用数组替代指针，来描述链表。让数组的每个元素由data和cur两部分组成，其中cur相当于链表的next指针，这种用数组描述的链表叫做静态链表，这种描述方法叫做游标实现法。我们对数组的第一个和最后一个元素做特殊处理，不存数据。让数组的第一个元素cur存放第一个备用元素（未被占用的元素）下标，而数组的最后一个元素cur存放第一个有值的元素下标，相当于头结点作用。空的静态链表如下图
当存放入一些数据时（"甲""乙""丁""戊""己""庚"），静态链表为：
第三个位置插入丙：
第三个位置插入丙
删除"甲"后，静态链表如下：
删除"甲"
5.3 循环链表
将单链表中终端节点的指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表
5.3.1 带头节点的空循环链表（左）和带头结点的非空循环链表（右）
5.3.2 循环链表判断结束的条件为：节点是否指向链表的头节点。循环列表访问第一个元素的复杂度为O(1)，但访问最后一个元素的复杂度为O(n)。为了方便最后一个元素的访问，经常使用尾指针指向循环链表的最后一个元素。如下图
5.4 双向链表
双向链表（double linked list）是在单链表的每个节点中，再设置一个指向其前驱节点的指针域。所以，双向链表中都有2个指针，一个指向其直接前驱，另一个指向直接后继。
5.4.1 双向循环链表，与循环链表类似，带头结点的双向循环空链表如下图（左），非空如下图（右边）
5.4.2 双向链表的插入操作如下图
5.4.3 双向链表的删除操作如下图
