本章节介绍数据结构中的线性表。
概述
线性表是最基本、最简单、也是最常用的一种数据结构。一个线性表是n个具有相同特性的数据元素的有限序列。
前驱元素：若A元素在B元素的前面，则称A为B的前驱元素
后继元素：若B元素在A元素的后面，则称B为A的后继元素
特征
数据元素之间具有一种“一对一”的逻辑关系。
- 第一个数据元素没有前驱，这个数据元素被称为头结点；
- 最后一个数据元素没有后继，这个数据元素被称为尾结点；
- 除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继。
如果把线性表用数学语言来定义，则可以表示为(a1,…ai-1,ai,ai+1,…an)，ai-1领先于ai,ai领先于ai+1，称ai-1是ai的前驱元素，ai+1是ai的后继元素。
分类
线性表中数据存储的方式可以是顺序存储，也可以是链式存储，按照数据的存储方式不同，可以把线性表分为顺序表和链表。
顺序表
顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元，依次存储线性表中的各个元素、使得线性表中再逻辑结构上响铃的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。
API设计
| 类名 |
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
2
3
4
5
6
7
8
9
10
11
12
13
14
| ```
## 遍历
一般作为容器存储数据，都需要向外部提供遍历的方式，因此我们需要给顺序表提供遍历方式。
在java中，遍历集合的方式一般都是用的是foreach循环，如果想让我们的SequenceList也能支持foreach循环，则需要做如下操作：
1. 让SequenceList实现Iterable接口，重写iterator方法；
2. 在SequenceList内部提供一个内部类SIterator,实现Iterator接口，重写hasNext方法和next方法；
代码：
```java
|
容量可变
在之前的实现中，当我们使用SequenceList时，先new SequenceList(5)创建一个对象，创建对象时就需要指定容器的大小，初始化指定大小的数组来存储元素，当我们插入元素时，如果已经插入了5个元素，还要继续插入数据，则会报错，就不能插入了。这种设计不符合容器的设计理念，因此我们在设计顺序表时，应该考虑它的容量的伸缩性。
考虑容器的容量伸缩性，其实就是改变存储数据元素的数组的大小，那我们需要考虑什么时候需要改变数组的大小？
添加元素时
添加元素时，应该检查当前数组的大小是否能容纳新的元素，如果不能容纳，则需要创建新的容量更大的数组，我们这里创建一个是原数组两倍容量的新数组存储元素。
移除元素时
移除元素时，应该检查当前数组的大小是否太大，比如正在用100个容量的数组存储10个元素，这样就会造成内存空间的浪费，应该创建一个容量更小的数组存储元素。如果我们发现数据元素的数量不足数组容量的1/4，则创建一个是原数组容量的1/2的新数组存储元素。
顺序表的容量可变代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| ```
## 时间复杂度
1. `get(i)`：不难看出，不论数据元素量N有多大，只需要一次eles[i]就可以获取到对应的元素，所以时间复杂度为O(1);
2. `insert(int i,T t)`：每一次插入，都需要把i位置后面的元素移动一次，随着元素数量N的增大，移动的元素也越多，时间复杂为O(n);
3. `remove(int i)`：每一次删除，都需要把i位置后面的元素移动一次，随着数据量N的增大,移动的元素也越多，时间复杂度为O(n);
由于顺序表的底层由数组实现，数组的长度是固定的，所以在操作的过程中涉及到了容器扩容操作。这样会导致顺序表在使用过程中的时间复杂度不是线性的，在某些需要扩容的结点处，耗时会突增，尤其是元素越多，这个问题越明显
## java中ArrayList实现
java中ArrayList集合的底层也是一种顺序表，使用数组实现，同样提供了增删改查以及扩容等功能。
1. 是否用数组实现；
2. 有没有扩容操作；
3. 有没有提供遍历方式；
# 链表
之前我们已经使用顺序存储结构实现了线性表，我们会发现虽然顺序表的查询很快，时间复杂度为O(1),但是增删的效率是比较低的，因为每一次增删操作都伴随着大量的数据元素移动。这个问题有没有解决方案呢？有，我们可以使用另外一种存储结构实现线性表，链式存储结构。
链表是一种物理存储单元上非连续、非顺序的存储结构，其物理结构不能只管的表示数据元素的逻辑顺序，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点（链表中的每一个元素称为结点）组成，结点可以在运行时动态生成。
`：创建Node对象 |
| 成员变量 | 1、`T item`：存储数据<br/>2、`Node next`：指向下一个结点 |
## 代码实现
## 单向链表
单向链表是链表的一种，它由多个结点组成，每个结点都由一个数据域和一个指针域组成，数据域用来存储数据，指针域用来指向其后继结点。链表的头结点的数据域不存储数据，指针域指向第一个真正存储数据的结点。
`：创建LinkList对象 |
| 成员方法 | 1、`public void clear()`：空置线性表<br/>2、`publicboolean isEmpty()`：判断线性表是否为空，是返回true，否返回false<br/>3、`public int length()`：获取线性表中元素的个数<br/>4、`public T get(int i)`：读取并返回线性表中的第i个元素的值<br/>5、`public void insert(T t)`：往线性表中添加一个元素；<br/>6、`public void insert(int i,T t)`：在线性表的第i个元素之前插入一个值为t的数据元素。<br/>7、`public T remove(int i)`：删除并返回线性表中第i个数据元素。<br/>8、`public int indexOf(T t)`：返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1。 |
| 成员内部类 | `private class Node`：结点类 |
| 成员变量 | 1、`private Node head`：记录首结点<br/>2、`private int N`：记录链表的长度 |
### 代码实现
```java
|
双向链表
栈
队列
