线性表是一种按顺序储存数据是的常用结构，大多数的线性表都支持以下的典型操作：
从线性表提取插入删除一个数据；
找出线性表中的某一个元素；
找出线性表中的元素；
确定线性表中是否包含某一个元素，确定线性表是否为空；
实现线性表的方法有两种：
1、数组(arry)，数组是动态的创建的，如果元素超过了数组的容量，就会创建一个新的数组并且把当前的数组元素复制到更大的数组里；
2、连式结构(linked structure)。连式结构有节点构成，节点是动态创建的。
方便起见，把数组称为MyArrayList，把连式结构称为MylinkedList，他们有相同的操作，却有这不同的实现。
设计一个好用的线性表，通常把一些通用的操作归纳为一个接口和抽象类，抽象类提供接口实现的框架，以更好地实现接口。把这样的接口叫MyList，把这样的抽象类叫MyAbstractList。
以下是接口MyList的代码：
publicinterfaceMyList{publicvoidadd(Ee);publicvoidadd(intindex,Ee);publicvoidclear(); //清除所有元素publicbooleancontains(Ee);publicEget(intindex);publicintindexOf(Ee);publicbooleanisEmpty();publicintlastIndexOf(Ee);publicbooleanremove(Ee);publicEremove(intindex); //删除指定元素publicObjectset(intindex, Ee); //在指定位置插入元素publicintsize(); }
下面是MyAbstractList代码(实现了各方法)：
publicabstractclassMyAbstractListimplementsMyList{protectedintsize=0; //声明sizeprotectedMyAbstractList(){}protectedMyAbstractList(E[] objects){for(inti=0;iadd(objects[i]); } }publicvoidadd(Ee){ add(size,e); }publicbooleanisEmpty(){returnsize==0; }publicintsize(){returnsize; }publicbooleanremove(Ee){if(indexOf(e) >=0){ remove (indexOf(e));returntrue; }elsereturnfalse; } }
下面先讲数组的线性表示：
数组是一种固定大小的数据结构，一旦创建就无法改变，但仍然可以用数组来实现动态的数据结构，方法是当数组大小不够用的时候，就创建一个更大的数组类来替换当前数组。
初始状态时，默认大小，创建一个类型为E[ ] 的数组data。向数组中插入一个新的元素时，首先确认数组是否有足够的空间，若不够，则创建一个为当前数组两倍的数组，然后复制元素到新的数组里面。现在在指定的下标处插入新的元素，并且要将指定下标后面的所有元素的下标都增加一。若是删除元素，则要把后面元素下标都减少一。
大体思路是：
- MyArrayList() 创建默认数组
+MyArrayList(E[ ] objects) 由对象数组创建一个数组
—ensureCapacity() 如果需要就扩大数组
+trimToSize() 将数组大小缩小至线性表的当前大小
下面是MyArrayList实现MyAbstractList的代码：
publicclassMyArrayListextendsMyAbstractList{publicstaticfinalintINITIAL_CAPACITY=16; //定义初始容量privateE[] data= (E[])newObject[INITIAL_CAPACITY];//创建默认数组publicMyArrayList() { }//由对象数组创建一个数组publicMyArrayList(E[] objects) {for (inti=0; i<objects.length; i++) add(objects[i]);//Warning: don抰 use super(objects)!}//在指定下标处增加元素publicvoidadd(intindex, Ee) {//如果需要调用数组增加两倍的方法ensureCapacity();//把指定下标后面的数的下标全部加一for (inti=size-1; i>=index; i--) data[i+1] =data[i]; data[index]=e; size++; }//如果需要,数组增加两倍的方法privatevoidensureCapacity() {if (size>=data.length) { E[] newData= (E[])(newObject[size*2+1]); System.arraycopy(data,0, newData, 0, size); data=newData; } }//清空元素publicvoidclear() { data= (E[])newObject[INITIAL_CAPACITY]; size=0; }//是否包含某一元素的方法publicbooleancontains(Ee) {for (inti=0; i<size; i++)if (e.equals(data[i])) returntrue;returnfalse; }//给定下标，获得下标所指定的元素publicEget(intindex) {returndata[index]; }//从第一个元素开始搜索某一元素 ，有则返回下标值，否则返回-1publicintindexOf(Ee) {for (inti=0; i<size; i++)if (e.equals(data[i])) returni;return-1; }//从最后一个元素开始publicintlastIndexOf(Ee) {for (inti=size-1; i>=0; i--)if (e.equals(data[i])) returni;return-1; }//删除元素publicEremove(intindex) { Ee=data[index];for (intj=index; j<size-1; j++) data[j]=data[j+1];//最后一个元素为空data[size-1] =null; size--;returne; }//替换publicEset(intindex, Ee) { Eold=data[index]; data[index]=e;returnold; }//重写Object中的方法，返回一个表示包含数组中全部元素的字符串publicStringtoString() { StringBuilderresult=newStringBuilder("[");for (inti=0; i<size; i++) { result.append(data[i]);if (i<size-1) result.append(", "); }returnresult.toString() +"]"; }//将数组大小缩小至线性表的当前大小publicvoidtrimToSize() {if (size!=data.length) { E[] newData= (E[])(newObject[size]); System.arraycopy(data,0, newData, 0, size); data=newData; } } }
测试的一个事例：
publicclassTestList {publicstaticvoidmain(String[] args) {//创建一个线性表MyListlist=newMyArrayList();//加入一个元素list.add("喜欢"); list.add(0,"我"); list.add("你"); System.out.println(list); list.add(1,"非常"); list.add(1,"很"); System.out.println(list); list.remove(1); System.out.println(list); list.set(3, "你 ，爱你一万年"); System.out.println(list); } }
