数据结构（一）基础-线性表
1 简介
线性表，全名为线性存储结构，是一种线性结构，它是具有相同类型的n(n≥0)个数据元素组成的有限序列。
2 特点
1. 对于同一个线性表，其每一个数据元素的值虽然不同，但必须具有相同的数据类型；
2. 数据元素之间具有一种线性的或“一对一”的逻辑关系
- 第一个数据元素没有前驱，这个数据元素被称为开始节点；
- 最后一个数据元素没有后继，这个数据元素被称为终端节点；
- 除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继。
3 存储结构
3.1 简介
线性表包含顺序表和链表，其中顺序表的地址是连续的，链表中的地址不是连续的，是通过指针连起来的。
也就是线性表有两种存储结构，一是顺序存储结构（图3a），二是链式存储结构（图3b）。
3.2 顺序存储结构
顺序表，使用数组实现，一组地址连续的存储单元，数组大小有两种方式指定，一是静态分配，二是动态扩展。
插入删除时需要移动大量的元素。
顺序表的特点：
- 在线性表中逻辑上相邻的数据元素，在物理存储上也是相邻的。
- 存储密度高，但要预先分配“足够应用”的存储空间，这可能会造成存储空间的浪费。
- 便于随机存储。
- 不便于插入和删除操作，这是因为在顺序表上进行的插入和删除操作会引起大量数据元素的移动。
3.3 链式存储结构
3.3.1 简介
链表的定义是递归的，它或者为空null，或者指向另一个节点node的引用，这个节点含有下一个节点或链表的引用。
与顺序存储相比，允许存储空间不连续，插入删除时不需要移动大量的元素，只需修改指针即可，但查找某个元素，只能从头遍历整个链表。
3.3.2 单链表
3.3.2.1 简介
单链表分为带头结点和不带头结点两种，不管有没有头结点，头指针都指向链表的第一个节点（有头结点指向头结点）。
头结点：数值域可不设任何信息，头结点的指针域指向链表的第一个元素。
带头节点的好处有：
（1）链表第一位置节点上的操作和其它位置上的操作一致
（2）无论链表是否为空，头指针都指向头结点（非空），空表和非空表处理一样
3.3.2.2 添加节点
单链表添加节点示意图：
（1）头插法
将新节点插入到当前链表的表头（头结点之后），插入的顺序与链表中的顺序相反，关键点就是记住旧的表头，生成一个新的放到旧表头前面。
（2）尾插法
增加一个尾指针，新节点插到链表的尾部，插入的顺序和链表的顺序一致。
节点的插入和删除，要点是先断后连，关键就是不要断链了，以插入为例（把s插入p和q之间），先断意思是先把p->q断了，变成s->q，后连，最后再把p和s连接起来。
3.3.2.3 删除节点
单链表删除节点示意图：
3.3.3 双链表
3.3.3.1 简介
双向链表(双链表)是链表的一种。和单链表一样，双链表也是由节点组成，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
3.3.3.2 添加节点
双链表添加节点示意图：
3.3.3.3 删除节点
双链表删除节点示意图：
3.3.3.4 双链表java实现
参考：java源码：java.util.LinkedList
参考
1. 数据结构之线性表
2. 线性表
