一、线性表简单介绍
1.1、描述
线性表是数据结构中最基础的一种结构，一个线性表是由n个具有相同特性的数据元素组成的有限序列，并且数据元素之间是1对1的关系。
例如：线性表（a1,a2,a3,...,ai-1,ai,ai+1）
根据其定义分析：
1.1.1、a1~ai+1，每个对象都必须是相同的数据元素；
1.1.2、取其中三个元素(ai-1,ai,ai+1),ai-1是ai的前驱，ai+1是ai的后继，相邻两个节点的关系必须是1对1的。
1.2、线性表物理分类
线性表顺序存储结构：
线性表链式存储结构：
二、线性表顺序的存储结构
线性表的顺序存储结构是在计算机内存分配一块连续的空间依次存储线性表的数据元素。我们经常使用的数组就是这样一种数据结构。
线性表顺序存储-数组分析：
2.1、指定数组初始大小，分配一块连续的内存空间
当我们给定的初始大小偏小时，数组容易上溢，如果添加新增元素判断逻辑，当数组没有剩余空间，重新申请一块连续的内存，空间是原来的1.5倍，然后将数据从原来的数组移动到新数组，Copy数组是个很耗时的操作。比如数组初始空间是1G，现在已经存储1G数据，当有新数据来是，发生扩容操作，压力是很大的。
当我们给定的初始大小偏大时，如果实际用不到这么多内存，就会造成空间浪费。
public class ArrayList<T> {
private Object[] data;
private int length;//数组长度
private int size;//数据长度
public ArrayList(int length) {
data = new Object[length];
this.length = length;
this.size = 0;
}
public ArrayList() {
this(16);
}
}
2.2、向下标为i的位置，插入数据
当我们需要在下标i插入数据，需要将下标>=i的数据全都往后移动一次，数组(数组长度为n)插入操作的时间复杂度是O(n)
2.3、删除下标为i的数据
当我们需要删除下标为i的数据，需要将>i的数据全都往前移动一次,数组(数组长度为n)删除操作的时间复杂度是O(n)
2.4、查询下标为i的数据
假定数组的第一个数据的地址是base_address,当我们需要查询下标为i的数据时，直接查询地址为base_address+i*sizeof(data)，sizeof(data)表示元素类型的字节长。
总结：
1、按下标查找数据，数组的时间复杂是O(1),查询快；
2、插入、删除数组数据，时间复杂度是O(n),耗时；
3、连续的存储空间如果分配太大，容易造成空间浪费，分配太小，动态扩容，时间复杂度高。
三、线性表的链式存储结构
线性表的链式存储结构是一组任意的内存空间存储数据元素，用引用将数据元素关联，数据元素包含数据域和指针域，指针域存放下一个元素的地址，同一种数据元素用链表比数组占用更多的空间。
线性表链式存储-单链表分析
3.1、运用哨兵机制，创建头结点，构造链表
在构造方法创建哨兵头结点，便于操作链表，之后所有节点都是基于头结点操作的。头结点的数据域不存放数据，指针域存放头指针。
public class SingleLinkList<T> {
private Node<T> head;
private int count;
public SingleLinkList() {
this.head = new Node<T>(null);
this.count = 0;
}
public static class Node<T>{
private T data;
private Node next;
public Node(T data) {
this.data = data;
this.next = null;
}
}
}
3.2、运用头插法，插入数据
头插法指的是new一个新节点，将头结点的指针域的值赋值给新节点的指针域，将新节点的地址赋值给头结点的指针域，这样就是通过头插法插入一个新节点，插入一个节点的时间复杂度是O(1)。
3.3、删除指定节点
例如连续的三个节点a1,a2,a3，现在需要将a2节点删除，链表可以直接将a2节点指针域的值赋值给a1节点的指针域，删除一个节点时间复杂度是O(1)
3.4、查询某个节点的数据
链表查询指定节点的数据，不能像数组一样直接通过计算地址找到数据，链表需要从头结点开始，一个节点接着一个节点往下找，所以链表的查询没有数组快，时间复杂度是O(n)
总结：
1、通过节点地址，查询数据，链表的时间复杂度是O(n);
2、插入删除链表节点，时间复杂度是O(1);
3、链表不需要连续的内存空间，如果大数据量需要插入和删除操作，链表的优势就很明显。
双向链表的节点有两个指针域和一个数据域，前面的指针域指向前一个节点，后面的指针域指向下一个节点，对比单链表，存储相同的数据，占用更多的空间，但是在任何一个节点，都可以很快找到它的前一个节点。
