线性表
线性表是最基本、最简单、也是最常用的一种数据结构。一个线性表是n个具有相同特性的数据元素的有限序列。
线性表的分类：线性表中数据存储的方式可以是顺序存储，也可以是链式存储，按照数据的存储方式不同，可以把线性表分为顺序表和链表。
顺序表
顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元，依次存储线性表中的各个元素、使得线性表中再逻辑结构上响铃的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。
| 类名 | SequenceList |
|---|---|
| 构造方法 | SequenceList(int capacity)：创建容量为capacity的SequenceList对象 |
| 成员方法 | 1.public void clear()：空置线性表 |
| 2.publicboolean isEmpty()：判断线性表是否为空，是返回true，否返回false
| 3.public int length():获取线性表中元素的个数
| 4.public T get(int i):读取并返回线性表中的第i个元素的值
| 5.public void insert(int i,T t)：在线性表的第i个元素之前插入一个值为t的数据元素。
| 6.public void insert(T t):向线性表中添加一个元素t
| 7.public T remove(int i):删除并返回线性表中第i个数据元素。
| 8.public int indexOf(T t):返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1。成员变量 | 1.private T[] eles：存储元素的数组
| 2.private int N:当前线性表的长度
代码实现：
1 | todo |
顺序表的遍历: 一般作为容器存储数据，都需要向外部提供遍历的方式，因此我们需要给顺序表提供遍历方式。在java中，遍历集合的方式一般都是用的是foreach循环，如果想让我们的SequenceList也能支持foreach循环，则需要做如下操作：
- 让SequenceList实现Iterable接口，重写iterator方法；
- 在SequenceList内部提供一个内部类SIterator,实现Iterator接口，重写hasNext方法和next方法；
代码实现：
1 | todo |
顺序表的容量可变: 在之前的实现中，当我们使用SequenceList时，先new SequenceList(5)创建一个对象，创建对象时就需要指定容器的大小，初始化指定大小的数组来存储元素，当我们插入元素时，如果已经插入了5个元素，还要继续插入数据，则会报错，就不能插入了。这种设计不符合容器的设计理念，因此我们在设计顺序表时，应该考虑它的容量的伸缩性
考虑容器的容量伸缩性，其实就是改变存储数据元素的数组的大小，那我们需要考虑什么时候需要改变数组的大小？
- 添加元素时：添加元素时，应该检查当前数组的大小是否能容纳新的元素，如果不能容纳，则需要创建新的容量更大的数组，我们这里创建一个是原数组两倍容量的新数组存储元素。
- 移除元素时：移除元素时，应该检查当前数组的大小是否太大，比如正在用100个容量的数组存储10个元素，这样就会造成内存空间的浪费，应该创建一个容量更小的数组存储元素。如果我们发现数据元素的数量不足数组容量的1/4，则创建一个是原数组容量的1/2的新数组存储元素。
代码实现：
1 | todo |
顺序表的时间复杂度:
- get(i):不难看出，不论数据元素量N有多大，只需要一次eles[i]就可以获取到对应的元素，所以时间复杂度为O(1);
- insert(int i,T t):每一次插入，都需要把i位置后面的元素移动一次，随着元素数量N的增大，移动的元素也越多，时间复杂为O(n);
- remove(int i):每一次删除，都需要把i位置后面的元素移动一次，随着数据量N的增大,移动的元素也越多，时间复杂度为O(n);
由于顺序表的底层由数组实现，数组的长度是固定的，所以在操作的过程中涉及到了容器扩容操作。这样会导致顺序表在使用过程中的时间复杂度不是线性的，在某些需要扩容的结点处，耗时会突增，尤其是元素越多，这个问题越明显。
链表
之前我们已经使用顺序存储结构实现了线性表，我们会发现虽然顺序表的查询很快，时间复杂度为O(1),但是增删的效率是比较低的，因为每一次增删操作都伴随着大量的数据元素移动。这个问题有没有解决方案呢？有，我们可以使用另外一种存储结构实现线性表，链式存储结构。
链表是一种物理存储单元上非连续、非顺序的存储结构，其物理结构不能只管的表示数据元素的逻辑顺序，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点（链表中的每一个元素称为结点）组成，结点可以在运行时动态生成。
那我们如何使用链表呢？按照面向对象的思想，我们可以设计一个类，来描述结点这个事物，用一个属性描述这个结点存储的元素，用来另外一个属性描述这个结点的下一个结点。
| 类名 | Node |
|---|---|
| 构造方法 | Node(T t,Node next)：创建Node对象 |
| 成员变量 | T item:存储数据 |
| Node next：指向下一个结点单向链表：单向链表是链表的一种，它由多个结点组成，每个结点都由一个数据域和一个指针域组成，数据域用来存储数据，指针域用来指向其后继结点。链表的头结点的数据域不存储数据，指针域指向第一个真正存储数据的结点。
| 类名 | LinkList |
|---|---|
| 构造方法 | LinkList()：创建LinkList对象 |
| 成员方法 | 1.public void clear()：空置线性表 |
| 2.publicboolean isEmpty()：判断线性表是否为空，是返回true，否返回false
| 3.public int length():获取线性表中元素的个数
| 4.public T get(int i):读取并返回线性表中的第i个元素的值
| 5.public void insert(T t)：往线性表中添加一个元素；
| 6.public void insert(int i,T t)：在线性表的第i个元素之前插入一个值为t的数据元素。
| 7.public T remove(int i):删除并返回线性表中第i个数据元素。
| 8.public int indexOf(T t):返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1。成员内部类 | private class Node:结点类
成员变量 | 1.private Node head:记录首结点
| 2.private int N:记录链表的长度
代码实现：
1 | todo |
双向链表: 双向链表也叫双向表，是链表的一种，它由多个结点组成，每个结点都由一个数据域和两个指针域组成，数据域用来存储数据，其中一个指针域用来指向其后继结点，另一个指针域用来指向前驱结点。链表的头结点的数据域不存储数据，指向前驱结点的指针域值为null，指向后继结点的指针域指向第一个真正存储数据的结点。