线性表
定义
- 零个或多个数据元素的有限序列 有序，头无前驱，尾无后驱，其他只有一个前驱和后驱。 有限，每个元素有自己确定的位置 星座排序可以看成一个线性表
Java中，数据结构中的线性表，对应着Collection中的List接口。
List
int size();//Returns the number of elements in this list.大小
boolean isEmpty();//Returns {@code true} if this list contains no elements.是否空
boolean contains(Object o);//是否包含
Iterator<E> iterator();//返回一个迭代器，没有用过。。原理待会儿继续看
Object[] toArray();//将列表变为数组返回
boolean add(E e);//在列表末尾增加一个元素
boolean remove(Object o);//移除第一个o元素，没有就不更改
boolean containsAll(Collection<?> c);//是否所有都在
boolean addAll(Collection<? extends E> c);//全部添加
default void sort(Comparator<? super E> c)//排序
void clear();//清空
boolean equals(Object o);//判断相等
int hashCode();//获得hash指
E get(int index);//
E set(int index, E element);//
void add(int index, E element);//添加到指定位置，后续元素向后移
E remove(int index);//移除第index个元素
int indexOf(Object o);//返回第一个元素o第下标
int lastIndexOf(Object o);//返回最后一个元素o第下标
List<E> subList(int fromIndex, int toIndex);//截取列表并返回
大致常用的就这些（第一次看源码诶）
顺序存储结构
- 用一段地址连续的存储单元一次存储线性表的数据单元 大小固定，起始位置固定。等于占了一块地。
- 三个属性：
1.存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置
2.线性表的最大存储容量
3.线性表的当前长度
数组的长度与线性表的长度
数组的长度是存放线性表存储空间的长度，存储分配后这个表是不变的。 线性表的长度是线性表中数据元素的个数，随着线性表的插入和删除操作的进行会改变 线性表的长度应该永远小于等于数组的长度
ArrayList
``` private int size;//表示数组大小 private static final int DEFAULT_CAPACITY = 10;//初始长度为10 private static final Object[] EMPTY_ELEMENTDATA = {};//有定义长度的实例初始化new ArrayList(0) private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//没有定义大小的new ArrayList() //创建 public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException(“Illegal Capacity: “+ initialCapacity); } } public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } //插入元素实现（ add(E e)调用下面这个 ），如果满了就扩充 private void add(E e, Object[] elementData, int s) { if (s == elementData.length) elementData = grow(); elementData[s] = e; size = s + 1; } //在指定位置插入 public void add(int index, E element) { rangeCheckForAdd(index); modCount++; final int s; Object[] elementData; if ((s = size) == (elementData = this.elementData).length) elementData = grow(); System.arraycopy(elementData, index, elementData, index + 1, s - index); elementData[index] = element; size = s + 1; }
//获得元素 public E get(int index) { Objects.checkIndex(index, size);//判断下标是否合法 return elementData(index); }
//删除元素 public E remove(int index) { Objects.checkIndex(index, size); final Object[] es = elementData; @SuppressWarnings(“unchecked”) E oldValue = (E) es[index]; fastRemove(es, index); return oldValue; } private void fastRemove(Object[] es, int i) { modCount++; final int newSize; if ((newSize = size - 1) > i) System.arraycopy(es, i + 1, es, i, newSize - i); es[size = newSize] = null; }
### 优点
* 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
* 可以快速存取表中任一位置的元素
### 缺点
* 插入和删除操作需要移动大量元素
* 当线性表长度变化很大时，难以确定存储空间容量
* 造成存储空间的碎片
## 链式存储结构
### 头指针与头结点的异同
头指针：
* 头指针是指链表中指向第一个结点的指针，若链表有头指针，则是指向头结点的指针
* 头指针具有标示作用，所以常用头指针冠以链表名字
* 无论链表是否为空，头指针均不为空。头指针是链表**必要元素**
头结点：
* 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据意一般无意义（或者放链表长度）。
* 有了头结点，对在第一元素结点前插入元素和删除第一结点，其操作与其他结点的操作就统一起来了。
* 头结点**不是必要元素**
因为单链表比较熟悉，就不多写了。
### 单链表结构与顺序存储的优缺点
* 存储分配方式 ：顺序用一段连续的存储单元一次存储线性表的数据元素；单链表采用链式结构，用一组任意的存储单元存放线性表元素。
* 时间性能：查找 顺序O(1),单链表O(n);插入和删除 顺序平均移动表长一半的元素O(n),单链表 在找出某位置的指针后只要O(1)
* 空间性能： 顺序需要预分配存储空间，分大了浪费，分小了易发生上溢；单链表不需要分配存储空间，元素个数也不受限制
## 静态链表
* 用数组实现的链表，首位存第一个结点的下标相当于头指针，最后一个元素村第一个插入的元素下标，相当于头结点。
## 循环链表
* 将单链表中端结点端指针端由空结点改为指向头结点，就使整个单链表形成一个环，简称循环链表。
## 双向链表
* 在单链表中的每个结点，在设置一个指向其前驱结点的指针域。
//结点定义
private static class Node
### LinkedList各种方法的实现
transient int size = 0;//大小
transient Node
//在中间某处添加——–
//在某结点前添加
void linkBefore(E e, Node
//删除元素
E unlink(Node
