顺序表
概念
顺序表是一段用物理地址的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数字的增删查改。
顺序表一般可分为：
- 静态顺序表：使用定长数组存储
- 动态顺序表：使用动态开辟的数组村粗
顺序表的实现
静态顺序表使用于确定知道需要存多少数据的场景
静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用
如何实现循序表？
- 第一步首先定义类的属性
我们根据定义知道顺序表的底层是一个数组，所以我们首先要定义数组这个属性，但怎么来记录数组中已经存了几个数呢？所以这里我们需要重新定义一个属性就是usedSize来记录数组中的数的个数。
public class List { public int[] elem; public int usedSize; public List() { this.elem = new int[10];//构造方法，详情看类和对象 } }
- 第二步
实现各种接口
打印顺序表
public void display() { for(int i = 0; i < this.usedSize; i++) { System.out.print(this.elem[i] + " "); } System.out.println(); }
在pos位置新增元素
假如，如图所示
我们可以看到在POS=2位置添加元素，需要将pos=2之后的数据全部向后移动一位，才能将pos=2的位置腾出来，全部移动一位之后变为：
具体代码如何实现：
从后往前遍历
public void add(int pos, int date) { for(int i = this.usedSzie; i >= pos; i--) { elem[i+1] = elem[i]; } this.elem[pos] = date; this.usedSzie ++; }
判定是否包含某个元素
遍历这个顺序表如果存在就返回true，否则返回false
public boolean contains(int date) { for(int i = 0; i < this.usedSize; i++) { if(elem[i] == date) { return true; } } return false; }
查找某个元素的位置
像刚才查找是否存在一样，只不过放回的是下标
public int search(toFind) { for(int i = 0; i < this.usedSize; i++) { if(this.elem[i] == toFind) { return i; } } return -1; }
获取pos位置的元素
public int getPos(int pos) { return this.elem[pos]; }
给pos位置的元素设为value
public void setPos(int pos,int value) { this.elem[pos] = value; }
删除第一次出现的关键字key
只需要找到第一次出现这个关键字的下标，然后让后面的数字都往前移动一位
初始位置是这样：
假设这里删除66
这样66就没有了
public void remove(int key) { int pos = search(key); for(int i = pos; i < this.usedSize; i++) { this.elem[i] = this.elem[i+1]; } this.usedSize --; }
获取顺序表的长度
public int size() { return this.usedSize; }
清空顺序表
直接让usedSize为0即可
public void clear() { this.usedSize = 0; }
顺序表的问题
- 顺序表中间（头部）的增减（删除）时间复杂度为O(N)
- 增容需要申请空间，拷贝数据，释放旧空间。会有不小的消耗
这些问题如何解决，单链表应运而生。
