概要
线性表：是一种逻辑结构，相同数据类型的n个数据元素的有限序列，除第一个元素外，每个元素有且仅有一个直接前驱，除最后一个元素外，每个元素有且仅有一个直接后继（大部分情况，循环链表不是）。
线性表特点
- 元素个数有限
- 逻辑上元素有先后次序
- 数据类型相同
- 仅讨论元素间的逻辑关系
从存储层面讲：线性表分为顺序存储和链式存储。
顺序存储
顺序表
使用数组实现，一组地址连续的存储单元，数组大小有两种方式指定，一是静态分配，二是动态扩展。
线性表从1开始，而数组从0开始。
优点：随机访问特性，查找O(1)时间，存储密度高；逻辑上相邻的元素，物理上也相邻；
缺点：插入删除需移动大量元素。
顺序表相关的操作跟数组有关，一般都是移动数组元素。
这里说一下插入和删除时的边界条件，首先线性表从1开始，数组从0开始，单纯的文件说明不够直接，来看图说话吧。
插入时：对于线性表来说最小能插入的位置是1，最大能插入的位置是8（=7+1），所以1<=index<=(7+1)；移动数组元素时要注意，for (int i = count; i >= index; i--) { items[i] = items[i-1];}
删除时：只能在蓝色方块之间寻找节点删除，即1<=index<=7。移动元素，for (i = index; i < count; i++) { items[i-1] = items[i];}
链式存储
链表的定义是递归的，它或者为空null，或者指向另一个节点node的引用，这个节点含有下一个节点或链表的引用。
与顺序存储相比，允许存储空间不连续，插入删除时不需要移动大量的元素，只需修改指针即可，但查找某个元素，只能从头遍历整个链表。
单链表
抽象数据类型：
typedef struct Node {
// 链表节点的嵌套类
ElemType data; // 数据域
struct Node *next; // 指针域
} Node;
单链表分为带头结点和不带头结点两种，不管有没有头结点，头指针都指向链表的第一个节点（有头结点指向头结点）。
头结点：数值域可不设任何信息，头结点的指针域指向链表的第一个元素。
带头节点的好处有：
（1）链表第一元素节点上的操作和其它位置上的操作一致
（2）无论链表是否为空，头指针都指向头结点（非空），空表和非空表处理一样
链表麻烦的地方是插入和删除时指针的修改，保证不断链，一般先断后链。
头插法
将新节点插入到当前链表的表头，（头结点之后），插入的顺序与链表中的顺序相反，关键点就是记住旧的表头，生成一个新的放到旧表头前面，如图：
核心代码
public void headInsert(T item) {
Node old = first;
first = new Node();
first.item = item;
first.next = old;
}
尾插法
增加一个尾指针，新节点插到链表的尾部，插入的顺序和链表的顺序一致，如图：
核心代码
public void tailInsert(T item) {
Node old = last;
last = new Node();
last.item = item;
last.next = null;
if (isEmpty()) {
first = last;
} else {
old.next = last;
}
}
插入节点
节点的插入和删除，要点是先断后连，关键就是不要断链了，以插入为例（把s插入p和q之间），先断意思是先把p->q断了，变成s->q，后连，最后再把p和s连接起来。
待插入节点为s，一般采用后插法，即先找到插入位置节点的前驱节点，然后插入，时间复杂度O(n)。
核心代码
p=getNodeByIndex(i-1);
s.next = p.next;
p.next = s;
删除节点
待删除节点为q，也是先找到前驱节点，修改指针域即可，时间复杂度O(n)。
核心代码
p = getNodeByIndex(i-1);
q = p.next;
p.next = q.next;
q = null;
面试题：寻找未知长度单链表的中间点
- 循环遍历找出链表长度，再找中间点
- 用快慢指针法
双链表
单链表节点的缺点是只有一个后继节点，访问前驱节点只能从头遍历（如插入、删除），时间复杂度为O(n)。双链表，即添加一个指向前驱的节点，节点类型如下：
typedef struct Node {
// 链表节点的嵌套类
ElemType data; // 节点内容
struct Node *prior, *next; // 前驱节点和后继节点
} Node， *LinkList；
双链表的查找和单链表的相同再次不在赘述，双链表的构造也分为头插和尾插，与单链表唯一不同的是修改前驱指针prior，具体见源码。插入和删除时不同，因为需要修改两个指针，如果给定要操作的节点，插入和删除的时间复杂度为O(1)。
插入节点
在p节点后插入s节点，先断后连，先把p和原后继节点的链条给断了，使后继节点只跟s节点有关：
核心代码
s.next = p.next;
p.next.prior = s;
s.prior = p;
p.next = s;
删除节点
删除节点p的后继节点q，也是先断后连，把q和其后继节点的关系，转让给p即可：
核心代码
q.next.prior = p;
p.next = q.next;
q = null;
循环链表
判断链表是否有环
- p和q两个指针，p每次向前走一步，q每次从头开始走，当p和q相等，但步数不同则有环；
- 快慢指针，当p==q，则有环
循环单链表
与单链表的区别在于，表中最后一个节点的指针不为null，而改为指向头结点（第一个节点），从而整个链表形成一个环。判断循环单链表是否为空，head.next是否等于head。
只有一个尾指针的循环单例表，可以很方便的操作表头和表尾，因为尾指针的后继就是头指针O(1) 。
循环双链表
与双链表的区别在于，头结点的prior指针指向尾节点，尾节点的next指针指向头结点。
静态链表
静态链表是借助数组来描述线性表的链式存储结构，节点也有数据域和指针域，这里的指针是节点的相对地址（数组下标），也需要预先分配一块连续的内存空间。
#define MAXSIZE 1000
typedef struct {
ElemType data; // 数据
int cur; // 游标(Cursor)
} Component, StaticLinkList[MAXSIZE]
- 注意
- 数组第一个和最后一个元素做特殊处理，他们的data不存放数据
- 未使用的数组元素成为备用链表
- 数组第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下标
- 数组最后一个元素，即下标为MAXSIZE - 1的cur则存放第一个有数值的元素的下标，相遇与单链表中头结点的作用
静态链表的插入操作：
- 通过数组的第一个元素获取备用链表的第一个元素位置，将数据存入进去，备用链表后移一位
- 通过数组的最后一位及游标链接，查找到要插入的位置
- 将位置之前的游标位置赋值给当前插入的元素，当前元素的位置赋值给之前元素的游标
静态链表的删除操作：
- 获取要删除的元素的游标赋值给该元素的上一个元素的游标
- 将该元素的游标赋值为备用链表的第一个元素即数组第一个元素的游标
- 将数组的第一个元素的游标设定为该元素的下标
栈
栈（Stack）是一个后进先出（LIFO）的线性表，他要求只在表尾(栈顶)进行插入（push）和删除（pop）操作。
栈分为顺序存储结构和链式存储结构,一般用顺序存储。
栈的清空操作：将s->top赋值为s->base,只是单纯的将指针数据改变并没有清空数据，可以恢复数据。
栈的销毁操作：需要释放内容。
栈的空间计算操作：s->top - s->base。
逆波兰表达式
队列
队列（queue）是只允许在一端进行插入操作在另一端进行删除操作的线性表，先行先出（FIFO）。
队列也分为顺序存储结构和链式存储结构,一般用链式存储，称链队列。
