前言：
顺序表是线性表的一种，线性表除了顺序表还有链表。一般我们可以将ArrayList看成一种顺序表。所谓顺序表就是逻辑上相邻的元素在存储空间的位置上也是相邻的。顺序表就是采用顺序存储结构存储的线性表，那么线性表的定义也是适用于顺序表的了。线性表：开始节点没有前驱，终端节点没有后继，其他所有节点有且仅有一个前驱和后继，这就是线性表，他是我们最常用的一种数据结构。这篇文章总结下怎么使用java语言中的数组来实现一个自己的顺序表。
一、相关概念
第一部分主要介绍下和单链表有关的相关概念，这里给出的概念都是书本上的官方定义，并不是作者胡诌的，为什么给出这些官方的定义呢 ？因为笔者认为官方给出的定义，是对一个概念最本质的解释，它的解释经过了时间的考验，被认为是解释的最合理深入简明扼要的。
1.什么是线性表
线性表是由n个数据元素构成的有限序列，n为线性表的表长，当n为0时表示当前线性表是空表。线性表有且仅有一个开始结点和终端节点。且开始结点没有前驱，终端节点没有后继，其余节点有且仅有一个前驱和后继。线性表一般分为顺序表和链表。单链表的实现
2.什么是顺序表
采用顺序存储结构存储数据元素的线性表被称为顺序表，顺序表，要求逻辑上相邻的数据元素在物理内存的存储上也是相邻的，当在顺序表的第i（0<=i<=n）插入一个数据元素时，需要后移n-i+1个数据元素，当删除第i个元素时需要移动n-i个数据元素。
3.什么是链表
采用链式存储结构存储数据元素的线性表被称为链表，链表不要求逻辑上相邻的数据元素内存上必须相邻，链表的每个节点都包含两部分，一部分是数据域用以存储数据，一部分是指针域用以存储指向相邻结点的指针或者引用。链表通过每个节点的指针域将一串数据串联成链。当结点只有一个指针域时，被称为单链表。
4.单链表、双链表、循环单链表、循环双链表
当链表的结点只有一个指针域时被称为单链表，循环单链表是单链表的一种特殊变化，只是将尾结点又指向了头结点（也可能是首结点）。
当链表的结点有两个时，一个指向前驱，一个指向后继这种链表便是双链表，循环双链表是双链表的一种特殊变化，只是将尾结点又指向了头结点（也可能是首结点）。
所有的链表的实现均有两种方式，一种是带有头结点，一种是不带有头结点的实现方式，两种实现略有区别。
5.头结点和首结点
首节点：真正存储第一个数据元素的结点被称为首节点。
头结点：当链表采用带头结点方式实现时，会创建一个数据域为null的节点，该节点的指针域存储的指针指向首节点的指针，他的唯一作用是标识链表的开始，带有头结点的链表更易于操作。
6.常见的栈和队列与线性表的关系
栈和队列也是常见的数据结构，但是栈和队列并不是线性表的一种，线性表只包含了顺序表和链表。不过我们可以将栈和队列看成是特殊的线性表。怎么特殊呢，栈是被限制了只能在一端进行插入和删除操作的线性表，所以栈的特性是先入后出，队列是被限制了只能在一端插入另一端删除的线性表，所以队列的特性是先入先出。既然栈和队列都是特殊的线性表，那么栈和队列自然就可以使用线性表来实现了，通常可以使用线性表中的顺序表和队列来实现栈和队列。
二、实现过程
下面我们根据一个存顺序表应该拥有的方法，一个个去实现顺序表的结构。
1.创建一个顺序表类:TestShunxuTable
我们需要一个类来作为顺序表的实现类，数据载体就使用数组来实现即可，此外必须需要提供一个顺序表有效数据的个数的属性，暂且就叫他length好了，length是衡量顺序表中存储数据个数的。他和私有属性数组中的长度是两个感念，数组长度可能是n但是里面可能只存储了x个值，那么x就是length的值。同时我们提供一个构造器来对数组进行初始化。
public class TestShunxuTable { private Object[] objectArray; private int length; //提供一个构造函数 public TestShunxuTable(int length){ objectArray = new Object[length]; } }
2.提供插入方法：insert(Object obj)
首先需要明确的是，若数组长度为n，插入位置为i，那么我们在i位置作插入操作，i往后的数组元素都需要后移一位。所以根据这个思想我们来实现插入操作，这里涉及顺序表的判空、判满方法，因为都很简单就不详细阐述了。
//插入 /** * 1.判断是否已满 * 2.判断i是否有效 * 3.在指定位置进行插入:插入位置的后方所有元素向后移动一位 * 4.对length+1 * @param obj * @param i */ public void insert(Object obj,int i) throws Exception{ boolean flag=false; if(isFull()) throw new Exception("已满"); if(isEmptry()){ length++; objectArray[0]=obj; return; } if(1<=i && i<=objectArray.length) length++; for(int j=length-1;j>i;j--){ objectArray[j]=objectArray[j-1]; } objectArray[i] = obj; } //判空方法 public boolean isEmptry(){ if (length==0) return true; else return false; } //判满方法 public boolean isFull(){ if(length==objectArray.length) return true; return false; }
2.提供根据下标获取方法：get(int i)
顺序表中，有了数据下一步肯定是想要获取到顺序表中的值，这就需要我们根据下标去获取到顺序表中的值。思路很简单我们就是去根据下标获取真正存储数据的数组中的值即可。
//根据下标获取 public Object get(int i) throws Exception{ if(i<0 || i>length-1) throw new Exception("下标越界"); return objectArray[i]; }
这里我们便可以初步测试下了，如下所示，可以看到插入和获取都是正常的。
3.提供根据下标删除方法：remove（int i）
删除方法，实现思路：我们在确定顺序表有效长度（length）不为空，传入的下标有效以后，即可将i位置以后的所有元素直接前移一位即可。移动完成后将有效长度进行减一即可实现，代码如下：
//删除 /** * 1.判断是否为空 * 2.判断i是否有效 * 3.将指定位置元素删除，并将指定位置后方所有元素前移1位 * 4.length-1 * @param i */ public void remove(int i) throws Exception{ if(isEmptry()) throw new Exception("表为空"); if(0<=i && i<length-1) for(int j=i;j<length-1;j++) objectArray[j]=objectArray[j+1]; objectArray[length-1]=null; length--; }
再来测试下删除方法的使用，是否好用，我们就来删除下刚刚测试时的第一个元素好了。
可以看到，删除下标为0的元素实现正常，删除后遍历顺序表，发现已经没有该值了。
4.提供获取某元素第一次出现的下标方法：indexOf(Object obj)
该方法也是线性表的实现中比较常用的一种方法，这里也实现下该方法，思路其实很简单，先判断传入值是否有效，再判断顺序表是否为空，不空则遍历顺序表与传入值比对，比对成功返回下标，否则返回-1.
//获取第一次出现某值的下标 /** * 1.判断obj是否有效 * 2.判断表是否有值 * 3.遍历表查询是否有obj，有返回下标，无返回-1 * @param obj * @return */ public int indexOf(Object obj){ if(null != obj) if(length>0) for(int i=0;i<length;i++) if(objectArray[i].equals(obj)) return i; return -1; }
然后我们再来测试下该方法的实现是否正确，此时为了严谨性，我们再往顺序表中插入一个张三2，下标就为2好了，这样顺序表中就有了两个张三2，一个是下标为0，一个是下标为2，我们调用indexOf方法传入张三2测试下，结果如下：
很明显第一次的输出是0，0是张三2第一次出现的下标正确，第二次输出-1，是因为顺序表中没有张三22这个值，也是正确的。
5.提供获取顺序表有效长度的方法：length()
该方法实现很简单，我们直接返回length属性即可。
//长度 public int length(){ return this.length; }
由前面几步可以知道，此时顺序表的有效长度应该是3，我们调用length方法返回的应该是3才是正确的。测试下该方法如下，可以看到顺序表长度是3，没有问题。
6.提供清空顺序表方法：clear()
在线性表（包含顺序表、链表）的实现类中，清空方法也是使用频率较高的一种，该方法应用场景是：在存储结构完成作用后，为了下次虚拟机触发GC时可以更好更快的回收线性表中存储的对象，使使用clear方法是有效的一种策略。这里就实现该方法，思路也很简单，既然这里的顺序表底层是使用数组实现，那么我们就清空数组的有效数据就行，代码如下：
//清空 public void clear(){ Arrays.stream(objectArray).forEach(obj ->obj=null); length = 0; }
下面测试下清空方法是否好用，正常情况下，清空后顺序表中是不包含任何元素的，结果如下图，可以看到调用clear()方法后，顺序表中已经没有任何元素了。
7.附上实现顺序表的完整代码
public class TestShunxuTable { private Object[] objectArray; private int length; //提供一个构造函数 public TestShunxuTable(int length){ objectArray = new Object[length]; } //清空 public void clear(){ Arrays.stream(objectArray).forEach(obj ->obj=null); length = 0; } //判空 public boolean isEmptry(){ if (length==0) return true; else return false; } //判满 public boolean isFull(){ if(length==objectArray.length) return true; return false; } //长度 public int length(){ return this.length; } //根据下标获取 public Object get(int i) throws Exception{ if(i<0 || i>length-1) throw new Exception("下标越界"); return objectArray[i]; } //插入 /** * 1.判断是否已满 * 2.判断i是否有效 * 3.在指定位置进行插入:插入位置的后方所有元素向后移动一位 * 4.对length+1 * @param obj * @param i */ public void insert(Object obj,int i) throws Exception{ boolean flag=false; if(isFull()) throw new Exception("已满"); if(isEmptry()){ length++; objectArray[0]=obj; return; } if(1<=i && i<=objectArray.length) length++; for(int j=length-1;j>i;j--){ objectArray[j]=objectArray[j-1]; } objectArray[i] = obj; } //删除 /** * 1.判断是否为空 * 2.判断i是否有效 * 3.将指定位置元素删除，并将指定位置后方所有元素前移1位 * 4.length-1 * @param i */ public void remove(int i) throws Exception{ if(isEmptry()) throw new Exception("表为空"); if(0<=i && i<length-1) for(int j=i;j<length-1;j++) objectArray[j]=objectArray[j+1]; objectArray[length-1]=null; length--; } //获取第一次出现某值的下标 /** * 1.判断obj是否有效 * 2.判断表是否有值 * 3.遍历表查询是否有obj，有返回下标，无返回-1 * @param obj * @return */ public int indexOf(Object obj){ if(null != obj) if(length>0) for(int i=0;i<length;i++) if(objectArray[i].equals(obj)) return i; return -1; } }
三、总结
1.顺序表的优点
顺序表是一种最基础，应用广泛的数据结构。当根据下标查找数据元素时他的查找时间复杂度是O(1)，效率是很高的，当不知道下标时需要遍历，他的查找效率是O(n),这个效率就不算高了。
2.顺序表的缺点
如果我们需要在i位置做插入操作，就需要将i和i位置以后的n-i+1个元素后移一位，这是很耗费时间的操作，若是将i位置的数据元素进行删除操作，同样的i位置以后的n-i个元素 进行前移一位，也是一种耗时的操作。所以在插入和删除操作时，顺序表的效率是不高的，无论是插入还是删除他的时间复杂度都是O(n)。这也是顺序表的缺点所在了。
综合顺序表的优点与缺点，我们可以发现，线性表适合用于存储“静态”的数据，即那种创建了以后就不会在有删除和插入操作的数据。而线性表的另一种实现：链表，则就是更适合插入和删除的操作，但是链表的遍历的时间复杂度是O(n),所以在查询上顺序表优于链表，但是在插入和删除上顺序表不及链表。
3.全文总结
到这里就已经实现了顺序表中常用的功能了，其实仔细一看就可以发现这里实现的顺序表怎么和List中的ArrayList这么相似，没错其实ArrayList也是一种顺序表，他的底层就是使用的数组来实现的，而且ArrayList的删除、插入、清空等方法与此处实现原理上基本一致，此处顺序表可当成破产版的ArrayList来看。学习这些原理，其实不是为了再写一个ArrayList出来，JDK的开发者已经将集合的性能提升的很高了，我们想要再进行提高花费的人力物力是不值得的，所以学习数据结构是为了更好的理解程序的原理，方便在日常的开发中可以正确的使用这些数据结构，而不是去重复造轮子，当然有能力的人也可以站在巨人的肩膀上对现有的数据结构实现进行优化，还要说一句，数据机构在任何的高级语言中都是存在的，它是一种语言无关性的东西，这里只是使用java语言将其展现出来而已，如果不用java语言，使用c、c++、c#、python等其他语言逻辑也都是一样的，我们学习应该学习的是思想，而不是具体的招式。
