一、线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的一条直线。
但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
二、什么是顺序表？
首先顺序表的底层是一个数组
为什么不直接使用数组？？
我们来画一个图：（请问这个数组里面有多少有效数据？？）
有人就会说：不是3个吗？？？ 
我说：不要自己数，让程序来知道？？
别人说：等于0的时候就跳出来嘛 count计数一下！！！
这样是不可行的：
我要是0也是数据呢？对吧，这里就有问题。
那么我们可以定义一个变量：这个变量叫做 useSide （代表当前里面有多少有效数据）
这里代表里面有4个数据：
这里代表里面有4个有效数据：
所以这就是顺序表的引出：一个顺序表不只一个数组就可以实现，还需要其他的变量（比如(usedSize）
代码实现：
首先我们发现这个对象就是一个 顺序表，里面有数组和 有效数组 变量和一个数组容量：
看一些main里面实例化对象在内存的一个布局：
#### 实现顺序表：
基本构成代码：
数组 ，有效数组， 可用容量
public class MyArrayList {
public int[] elem; //数组
public int useSize; //有效数组
public static int capacity = 10; //可用容量
public MyArrayList() { //使用构造方法 初始容量
this.elem = new int[capacity];
}
}三、顺序表的常用操作实现：
要实现的功能：一个个来看
// 打印顺序表
public void display() { }
// 在 pos 位置新增元素
public void add(int pos, int data) { }
// 判定是否包含某个元素
public boolean contains(int toFind) { return true; }
// 查找某个元素对应的位置
public int search(int toFind) { return -1; }
// 获取 pos 位置的元素
public int getPos(int pos) { return -1; }
// 给 pos 位置的元素设为 value
public void setPos(int pos, int value) { }
//删除第一次出现的关键字key
public void remove(int toRemove) { }
// 获取顺序表长度
public int size() { return 0; }
// 清空顺序表
public void clear() { }(1) 在 pos 位置新增元素
给定指定的位置放入指定的数据：
先来说一下思路吧：
- 判断数组是否满
- 判断存放的位置下标是否合法（会不会数组越界）
- 如果满了实现扩容
- 想存放数据在数组，首先要把后面的数组往后面放一步，这样前面才会有位置放
- 存放好数据记住useSize++；（有效数据加1）
我们来看一下图片解析：也是把数组最后的元素往后移动一位
以上是代码思路，我们来看一下代码是怎么样实现的吧！
public boolean isFull(){
//1. 满的情况
return this.useSize==capacity; //判断useSize和最大容量一样吗 一样就满了
}
// 在 pos 位置新增元素
public void add(int pos, int data) {
if(pos<0 || pos>this.useSize){ //判断下标是否合法
System.out.println("下标位置不合法");
return;
}
if(isFull()){ //扩容数组大小数组大小
this.elem = Arrays.copyOf(this.elem,2*capacity); //扩容要新拷贝一份
capacity *=2; //容量也要变大
}
for (int i = useSize-1; i >=pos ; i--) {
this.elem[i+1] = this.elem[i]; //当前元素移动到后i+1的位置
}
this.elem[pos] = data;
this.useSize++;
}
(2) 打印顺序表
思路：遍历数组即可
代码：注意遍历的长度是useSize
// 打印顺序表
public void display() {
for (int i = 0; i < this.useSize; i++) {
System.out.print(elem[i] + " ");
}
System.out.println();
}（4)判定是否包含某个元素
思路：遍历数组即可
代码：注意遍历的长度是useSize
public boolean isEmpty(){
return useSize==0;
}
public boolean contains(int toFind) {
if (isEmpty()){
return false;
}
for (int i = 0; i < this.useSize; i++) {
if (elem[i]==toFind){
return true;
}
}
return false;
}（4)查找某个元素对应的位置
思路：遍历数组即可，找到返回下标
代码：注意遍历的长度是useSize
public int search(int toFind) {
for (int i = 0; i < elem.length; i++) {
if (elem[i]==toFind){
return i;
}
}
return -1;
}（5)获取 pos 位置的元素
思路：直接返回pos下标的数组
代码：
public int getPos(int pos) {
if (pos<0||pos >=useSize){
throw new RuntimeException("当前下标不合法"); //手动抛出异常
}
if (isEmpty()){
throw new RuntimeException("当前顺序表是空的"); //手动抛出异常
}
return this.elem[pos];
}（5)获取顺序表长度
思路：直接返回useSize 即可
public int size() {
return this.useSize;
}（5)给 pos 位置的元素设为 value
思路：直接赋值即可，需要注意下标合法性
public void setPos(int pos, int value) {
if(pos<0 || pos>= this.useSize){
System.out.println("pos不合法");
}
if(isEmpty()){
System.out.println("顺序表");
}
this.elem[pos] =value;
}（6)删除第一次出现的关键字key
思路：代码和add 有点像，大概原理是找到要删除的元素，然后让下一个元素到当前的元素上面就可以了，最后useSize--；
图片演示：
代码：
//删除第一次出现的关键字key
public void remove(int toRemove) {
if (isEmpty()){ //判断是否为空
return;
}
int index =search(toRemove); //找到要删除的下标
if (index==-1){
return;
}
for (int i = index; i <useSize-1; i++) {
elem[i] = elem[i+1]; //让后面的一个值来前面覆盖
}
useSize--; //有效数 --
}思考一个问题为什么要 useSize-1
因为下面的是i+1,如果i走到了 最后一个格子，你在 elem[i] = elem[i+1]; 会 报一个空指针异常：
（7)清空顺序表
思路：遍历让每一个元素都变成0，最后useSize等于0；
代码：
public void clear() {
for (int i = 0; i <useSize; i++) {
this.elem[i]=0;
}
useSize=0;
}
