前言：顺序表与链表是非常基本的数据结构，它们可以被统称为线性表。他们是学好数据结构的基础。而对于学习Java编程语言来说，也有着提高代码量和思维方式的好处，所以本篇我们来介绍顺序表和链表。
每文一图：
画图带你从顺序表到链表：- 一.线性表
- 二.顺序表
- 1.概念及结构
- 2.接口实现
- ① 打印和获取顺序表长度
- ② 新增元素
- ③判定包含某个元素及查找元素
- ④获取 pos 位置的元素
- ⑤给 pos 位置的元素更新
- ⑥ 删除第一次出现的值
- ⑦ 清空顺序表
- 3.顺序表的问题及思考
一.线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。
线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
线性表就主要了解一下概念就好了，我们主要学习的是顺序表和链表。
二.顺序表
什么是顺序表？
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
有同学会是那不就是数组吗，是也不是，我们把数组做成顺序表的样子可以让我们更好的面向对象，在数组上完成增删查改。接下来就让我们进入顺序表的世界。
1.概念及结构顺序表一般可以分为：
静态顺序表：使用定长数组存储。
动态顺序表：使用动态开辟的数组存储。
静态顺序表适用于确定知道需要存多少数据的场景，静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以对于顺序表，相比之下动态顺序表更灵活, 根据需要动态的分配空间大小。
所以这里我们学习的也是动态的顺序表，定长的可没动态的有意思。
2.接口实现
Description:顺序表
我们来实现一个动态顺序表，也就是说，我们要用数组做一个动态的能增删查改的顺序表，以下是需要支持的接口，：
public class MyArrayList {
public int [] elem;//用这个数组去做顺序表
public int useSize;//数组中元素的个数
public MyArrayList(){
int [] elem = new int[10];//定义数组个数
}
// 打印顺序表
public void display() { }
// 获取顺序表长度
public int size() { return 0; }
// 在 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 void clear() { }
}
也就是说，我们在创建一个对象，而这个对象它具有增删查改的动态顺序表的功能，我们可以在对象中使用它，接下来我们可以逐一实现。
我们先做一点准备工作：
首先是在main方法中创建这个对象。
//在main方法中创建这个对象
public class TestDemo {
public static void main(String[] args) {
MyArrayList myArrayList = new MyArrayList();
}
}
然后是把我们的数组给画出来，待会我们就是用这个数组去举例说明写代码了：
在这里，我们已经做好了前面的准备，就是创建对象和类：
然后就可以进入我们实现顺序表的模块了。
① 打印和获取顺序表长度
这两个比较简单就直接放在一起写了，首先是打印顺序表，我们已经定义好了数组和一个整形作为它的元素个数，所以对于打印就直接像打印数组一样就好了。
代码实现：
// 打印顺序表
public void display() {
for (int i = 0; i < useSize; i++) {
System.out.println(elem[i]+" ");
}
System.out.println();
}
而获取顺序表长度，只需要打印我们的useSize就好了。
代码实现：
// 获取顺序表长度
public int size() {
return useSize;
}
② 新增元素
对于新增元素，就需要我们分析一下了，什么时候可以增加，什么时候不能增加，我们都要考虑好。
首先，我们定义的add方法来新增元素，有两个参数，一个是pos为增加元素的位置，另一个是data表示增加的元素值。
然后就是我们需要考虑的东西了，在一个数组里面插入元素，要注意什么地方呢？首先是能不能放，有以下两种问题：
第一种是pos的位置问题，当我们的pos小于0或者pos大于useSize，就不是我们数组范围内了，就不能直接放入元素了。第二种是把数组放满了下一个怎么放，我们这里的写法是一个简单的扩容，直接扩大成两倍的元素个数。
然后就是放的问题了，在考虑完能放之后，我们就要考虑怎么放，这里我们放的可能有两种，第一种是直接放到后面的位置，第二种就是插入在数组中间，所以我们要先移动数据然后再插入。
总结起来就是：
1.判断是否可以存放数据
2.把原有数据挪好
3.把data放到pos位置
代码实现：
// 在 pos 位置新增元素
public void add(int pos, int data) {
if(pos < 0 || pos >useSize){
System.out.println("pos位置不合法！");
return;//判断是否合法
}
if(isFull()){
Arrays.copyOf(elem,elem.length * 2);//扩容
}
for (int i = this.useSize-1; i >= pos; i--) {
elem[i+1]=elem[i];//挪数组
}
this.elem[pos]=data;//把元素放进对应位置
this.useSize++;//增加了一个元素
}
public boolean isFull(){
return this.useSize == this.elem.length;
}
③判定包含某个元素及查找元素
对于判断是否包含某个元素和查找某个元素对应的位置，同样是类似的，在这里，要判断我们只需要遍历数组就好了，一一对比：
// 判定是否包含某个元素
public boolean contains(int toFind) {
for (int i = 0; i < useSize; i++) {
if(elem[i] == toFind){
return true;//是就返回true
}
}
return false;//不是就返回false
}
然后对于如果是想查找某一个元素，同样只需要遍历数组，找到那一个就返回他的下标，找不到就返回-1，因为数组下标中没有-1。
代码实现：
// 查找某个元素对应的位置
public int search(int toFind) {
for (int i = 0; i < useSize; i++) {
if(elem[i] == toFind){
return i;
}
}
return -1;
}
④获取 pos 位置的元素
对于获取pos位置的元素，同样的要先判断是否有这个位置，然后在获取，所以也是实现把小于大于的抛掉，还有一直可能就是顺序表为空，也要判断。然后是获取，获取就总结返回下标对于的值就可以了。
代码实现：
// 获取 pos 位置的元素
public int getPos(int pos) {
if(pos < 0 || pos >useSize){
System.out.println("pos位置不合法！");
return -1;
//在这里，确实有可能值是-1，但是为了对新手友好，这里暂且写为返回-1
}
if(isEmpty()){
System.out.println("顺序表为空！");
return -1;
}
return elem[pos];
//返回pos 位置的元素
}
⑤给 pos 位置的元素更新
给 pos 位置的元素更新其实也相当于是找到这个元素然后赋值，所以跟上面的获取 pos 位置的元素很类似，直接找到就赋值就好了。
代码实现：
// 给 pos 位置的元素设为 value
public void setPos(int pos, int value) {
if(pos < 0 || pos >useSize){
System.out.println("pos位置不合法！");
return ;
}
if(isEmpty()){
System.out.println("顺序表为空！");
return ;
}
elem[pos] = value;
}
⑥ 删除第一次出现的值
首先我们对于删除第一次出现的关键字key，也就是值，是怎么删呢，直接把他置空？那肯定不行，为0也是占了这个位置了，所以我们应该要把他覆盖，也就是将它后面的元素往前移，一个接一个覆盖，这样子就相当于删除了。
那么覆盖到哪一个元素呢，这里要注意，如果我们覆盖到useSize-1的元素，那么我们就已经越界了，因为我们是访问i+1的位置去覆盖到i的位置。所以我们不用去覆盖掉useSize-1的元素，即使它存在，对我们的打印，更新等操作都不影响。
所以，我们对于删除的代码，应该是：
1.查看顺序表是否存在
2.寻找要删除数字的下标
3.数据前移覆盖
代码实现：
//删除第一次出现的关键字key
public void remove(int toRemove) {
if(isEmpty()){
System.out.println("顺序表为空");
return;
}
int index = search(toRemove);
if(index == -1) {
System.out.println("没有你要删除的数字！");
return;
}
for (int i = index; i < this.useSize-1; i++) {
this.elem[i+1]=this.elem[i];//覆盖掉
}
this.useSize--;//减少一个元素
}
⑦ 清空顺序表
对于清空顺序表，大家首先想到的是不是遍历然后删除，其实不用，对于我们现在这个基本的顺序表数组来说，存放的都是值，我们可以直接把useSize置为0，顺序表就访问不了元素了，然后输入数组没有清理，但是功能已经完成了。
代码实现（出奇的简单哈哈）：
// 清空顺序表
public void clear() {
useSize =0;
}
但是这里也要注意，为什么是基本的顺序表数组来说呢，如果我们数组中存放的是引用类型，也就是地址，那么我们清空顺序表要做的就是要把所有的元素都置为空。
代码：
public void clear() {
this.usedSize = 0;
for (int i = 0; i < usedSize; i++) {
this.elem[i] = null;
}
this.usedSize = 0;
}
到这里我们的顺序表就写完了！
大家可以在main方法中测试一下，比如：
public static void main(String[] args) {
MyArrayList myArrayList = new MyArrayList();
myArrayList.add(0,1);
myArrayList.add(1,2);
myArrayList.add(2,3);
myArrayList.add(3,4);
myArrayList.search(2);
myArrayList.display();
System.out.println("==============");
myArrayList.clear();
myArrayList.display();
//这里并没有全测，只是举例子
}
}
3.顺序表的问题及思考
虽然我们现在实现了一个顺序表，但是顺序表的问题我们不得不提一下，对于我们刚刚写的代码，其中：
- 顺序表中间/头部的插入删除，必须移动元素，时间复杂度为O(N)。
- 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
- 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续
插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
那么这些错误怎么处置呢，这时候链表就出现了。对于顺序表，其在物理上和逻辑上都是连续的，而链表则在物理上不一定连续，而逻辑是是连续的，也就是说链表可以实现更多顺序表实现不了的东西。
这就是本篇Java中的画图带你从顺序表到链表1的全部内容啦，如果觉得还不错或者感觉对你有帮助，不妨点赞关注一键三连，下一篇我们就来到链表中和链表对线了！！！欢迎关注。一起学习，共同努力！也可以期待这个系列接下来的博客噢。
链接：都在这里！ Java SE 带你从零到一系列
还有一件事：
