线性表
首先来说明一下什么是抽象数据类型，我们都知道java在默认情况下，所有的基本数据类型(int,float,boolean等)都支持基本运算，如加减法，这是因为系统已帮我们实现了这些基本数据类型的的基本运算。 而对于自定义的数据类型(如类)也需要定义相应的运算，但在实际使用这些自定义的数据类型的运算时需要自己实现相关的运算，也就是说用户自定义的数据类型的运算需要我们自己利用系统提供的基本运算来定义和实现。这些自定义了数据结构(如自定义类)和包含相关运算组合实现的数据类型就称其为抽象数据类型(ADT,Abstract Data Type),因此一个ADT会包含数据声明和运算声明。常用的ADT包含链表、栈、队列、优先队列、二叉树、散列表、图等，所以接下来我们要分析的顺序表和链表也属于ADT范畴。
顺序表
原理概要
顺序存储结构底层是利用数组来实现的，而数组可以存储具有相同数据类型的元素集合，如int，float或者自定义类型等，当我们创建一个数组时，计算机操作系统会为该数组分配一块连续的内存块，这也就意味着数组中的每个存储单元的地址都是连续的，因此只要知道了数组的起始内存地址就可以通过简单的乘法和加法计算出数组中第n-1个存储单元的内存地址，就如下图所示：
通过上图可以发现为了访问一个数组元素，该元素的内存地址需要计算其距离数组基地址的偏移量，即用一个乘法计算偏移量然后加上基地址，就可以获得数组中某个元素的内存地址。其中c代表的是元素数据类型的存储空间大小，而序号则为数组的下标索引。整个过程需要一次乘法和一次加法运算，因为这两个操作的执行时间是常数时间，所以我们可以认为数组访问操作能再常数时间内完成，即时间复杂度为O(1)，这种存取任何一个元素的时间复杂度为O(1)的数据结构称之为随机存取结构。而顺序表的存储原理正如上图所示，因此顺序表的定义如下（引用）：
线性表的顺序存储结构称之为顺序表(Sequential List),它使用一维数组依次存放从a0到an-1的数据元素(a0,a1,…,an-1)，将ai(0< i <> n-1)存放在数组的第i个元素，使得ai与其前驱ai-1及后继ai+1的存储位置相邻，因此数据元素在内存的物理存储次序反映了线性表数据元素之间的逻辑次序。
实现分析
顺序表接口类ISeqList<T>
/*** Created by zejian on 2016/10/30.* 顺序表顶级接口*/publicinterfaceISeqList<T> { /*** 判断链表是否为空* @return*/booleanisEmpty(); /*** 链表长度* @return*/intlength(); /*** 获取元素* @param index* @return*/Tget(intindex); /*** 设置某个元素的值* @param index* @param data* @return*/Tset(intindex, Tdata); /*** 根据index添加元素* @param index* @param data* @return*/booleanadd(intindex, Tdata); /*** 添加元素* @param data* @return*/booleanadd(Tdata); /*** 根据index移除元素* @param index* @return*/Tremove(intindex); /*** 根据data移除元素* @param data* @return*/booleanremove(Tdata); /*** 根据data移除元素* @param data* @return*/booleanremoveAll(Tdata); /*** 清空链表*/voidclear(); /*** 是否包含data元素* @param data* @return*/booleancontains(Tdata); /*** 根据值查询下标* @param data* @return*/intindexOf(Tdata); /*** 根据data值查询最后一个出现在顺序表中的下标* @param data* @return*/intlastIndexOf(Tdata); /*** 输出格式* @return*/StringtoString(); } }
代码中声明了一个Object数组，初始化数组大小默认为64，存储的元素类型为泛型T，length则为顺序表的长度，部分方法实现比较简单，这里不过多分析，我们主要分析get(int index)、set(int index, T data)、add(int index, T data)、remove(int index)、removeAll(T data)、indexof(T data)等方法的实现。
- get(int index) 实现分析从顺序表中获取值是一种相当简单的操作并且效率很高，这是由于顺序表内部采用了数组作为存储数据的容器。因此只要根据传递的索引值，然后直接获取数组中相对应下标的值即可，代码实现如下：
publicTget(intindex){ if (index>=0&&index<this.length) return (T) this.table[index]; returnnull; }
- set(int index, T data) 实现分析在顺序表中替换值也是非常高效和简单的，只要根据传递的索引值index找到需要替换的元素，然后把对应元素值替换成传递的data值即可，代码如下
publicTset(intindex, Tdata){ if (index>=0&&index<this.length&&data!=null) { Told= (T)this.table[index]; this.table[index] =data; returnold; } returnnull; }
add(int index, T data)实现分析在顺序表中执行插入操作时，如果其内部数组的容量尚未达到最大值时，可以归结为两种情况，一种是在头部插入或者中间插入，这种情况下需要移动数组中的数据元素，效率较低，另一种是在尾部插入，无需移动数组中的元素，效率高。但是当顺序表内部数组的容量已达到最大值无法插入时，则需要申请另一个更大容量的数组并复制全部数组元素到新的数组，这样的时间和空间开销是比较大的，也就导致了效率更为糟糕了。因此在插入频繁的场景下，顺序表的插入操作并不是理想的选择。下面是顺序表在数组容量充足下头部或中间插入操作示意图（尾部插入比较简单就不演示了）：
顺序表在数组容量不充足的情况下头部或中间插入操作示意图： 
理解了以上几种顺序表的插入操作后，我们通过代码来实现这个插入操作如下，注释很清晰就过多分析了：
/*** 根据index插入元素* @param index 插入位置的下标,0作为起始值* @param data 插入的数据* @return*/publicbooleanadd(intindex, Tdata){ if (data==null) returnfalse; //插入下标的容错判断,插入在最前面if (index<0) index=0; //插入下标的容错判断,插入在最后面if (index>this.length) index=this.length; //判断内部数组是否已满if (this.length==table.length) { //把原数组赋值给临时数组Object[] temp=this.table; //对原来的数组进行成倍拓容,并把原数组的元素复制到新数组this.table=newObject[temp.length*2]; //先把原数组下标从0到index-1(即插入位置的前一个位置)复制到新数组for (inti=0; i<index; i++) { this.table[i] =temp[i]; } } //从原数组的最后一个元素开始直到index位置,都往后一个位置// 最终腾出来的位置就是新插入元素的位置了for (intj=this.length-1; j>=index; j--) { this.table[j+1] =this.table[j]; } //插入新值this.table[index] =data; //长度加一this.length++; //插入成功returntrue; }
remove(int index) 实现分析顺序表的删除操作和前的插入操作情况是类似的，如果是在中间或者头部删除顺序表中的元素，那么在删除位置之后的元素都必须依次往前移动，效率较低，如果是在顺序表的尾部直接删除的话，则无需移动元素，此情况下删除效率高。如下图所示在顺序表中删除元素ai时，ai之后的元素都依次往前移动：
删除操作的代码实现如下：
/*** 根据index删除元素* @param index 需要删除元素的下标* @return*/publicTremove(intindex) { if (this.length!=0&&index>=0&&index<this.length) { //记录删除元素的值并返回Told= (T)this.table[index]; //从被删除的元素位置开,其后的元素都依次往前移动for (intj=index; j<this.length-1; j++) { this.table[j] =this.table[j+1]; } //设置数组元素对象为空this.table[this.length-1]=null; //顺序表长度减1this.length--; returnold; } returnnull; }
removeAll(T data) 实现分析在顺序表中根据数据data找到需要删除的数据元素和前面分析的根据index删除顺序表中的数据元素是一样的道理，因此我们只要通过比较找到与data相等的数据元素并获取其下标，然后调用前面实现的remove(int index)方法来移除即可。代码实现如下：
publicbooleanremoveAll(Tdata) { booleandone=false; if (this.length!=0&&data!=null) { inti=0; while (i<this.length) //找出数据相同的选项if (data.equals(this.table[i])) { this.remove(i);//根据下标删除done=true; } elsei++;//继续查找 } returndone; }
indexOf(T data) 实现分析要根据data在顺序表中查找第一个出现的数据元素的下标，只需要通过对比数据项是否相等，相等则返回下标，不相等则返回-1，indexOf和lastIndexOf方法实现如下：
/*** 根据数据查询下标* @param data* @return*/publicintindexOf(Tdata) { if (data!=null) for (inti=0; i<this.length; i++) { //相当则返回下标if (this.table[i].equals(data)) returni; } return-1; } /*** 根据data查询最后一个出现在顺序表中的下标* @param data* @return*/publicintlastIndexOf(Tdata) { if (data!=null) for (inti=this.length-1; i>=0; i--) if (data.equals(this.table[i])) returni; return-1; }
以上便是顺序表的主要的操作方法，当然顺序表中还可以实现其他操作，如在初始化构造函数时传入数组来整体初始化顺序表，比较两个信息表是否相等、是否包含某个数据等。
/*** 传入一个数组初始化顺序表* @param array*/publicSeqList(T[] array){ if (array==null){ thrownewNullPointerException("array can\'t be empty!"); } //创建对应容量的数组this.table=newObject[array.length]; //复制元素for (inti=0;i<array.length;i++){ this.table[i]=array[i]; } this.length=array.length; }
在等概率的情况下，插入或者删除一个顺序表的元素平均需要移动顺序表元素总量的一半，其时间复杂度是O(n)。当然如果在插入时，内部数组容量不足时，也会造成其他开销，如复制元素的时间开销和新建数组的空间开销。 因此总得来说顺序表有以下优缺点：
- 优点使用数组作为内部容器简单且易用在访问元素方面效率高数组具有内存空间局部性的特点，由于本身定义为连续的内存块，所以任何元素与其相邻的元素在物理地址上也是相邻的。
- 缺点内部数组大小是静态的，在使用前必须指定大小，如果遇到容量不足时，需动态拓展内部数组的大小，会造成额外的时间和空间开销在内部创建数组时提供的是一块连续的空间块，当规模较大时可能会无法分配数组所需要的内存空间顺序表的插入和删除是基于位置的操作，如果需要在数组中的指定位置插入或者删除元素，可能需要移动内部数组中的其他元素，这样会造成较大的时间开销，时间复杂度为O(n)
