本节我们讨论常见和常用的数据结构-表。如果要简单的说什么是表格，可以这样说：元素按顺序排列的集合就是表格。表的概述抽象数据类型是一些对象与一组操作的组合1.定义：线性表是一种线性结构，它是一个包含n≥0个节点的有限序列。对于其中的节点，只有一个没有前驱节点有后继节点的起始节点，只有一个没有后继节点有前驱节点的终结节点，其他节点只有一个前驱节点节点和后继节点。2.Features/属性1)集合中必须有唯一的***元素2)集合中必须有唯一的***元素3)除***元素外，必须有唯一的后继者4)除了第一个元素，还有一个唯一的前身。上图中，a1是a2的前驱，ai+1是ai的后继，a1没有前驱，an没有后继，n是线性表的长度，如果n==0时，线性表是一个空表。下图是一个标准的线性表。线性表分为以下几种：顺序存储方式线性表如果每个元素占用C个存储单元，则：Loc(An)=Loc(An-1)+C，则：Loc(An)=Loc(A1)+(i-1)*C；优点：查询速度快缺点：插入删除效率慢。虽然创建的数组具有固定大小，但如果需要，可以创建容量加倍的不同数组。下面是展开的伪代码：int[]aar=newint[10];//展开aarint[]newArr=newint[aar.length*2];for(inti=0;inext=p->nextp-next=s;执行删除操作，只需要如下代码：p->next=p->next->next循环链表将单向链表中终结节点的指针end由空指针改为指向head节点，使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。双向循环链表是双向循环链表。在单向循环链表的每个节点中，设置一个指向其前驱节点的指针域。对于一个空的双向循环链表，在Java中插入一个双向循环链表。表1.CollectionApi中的IteratorIterator接口的思想，通过Iterator方法，每个集合创建并返回给客户端一个实现了Iterator接口的对象，并在对象内部存储当前所在位置的概念。publicinterfaceIterator{booleanhasNext();Enext();defaultvoidremove(){thrownewUnsupportedOperationException("remove");}}Iterator中的方法有限，所以很难用Iterator做除了遍历Collection之外的任何工作。迭代器还包含一个remove()方法。该方法的作用是删除next()***返回的item（remove()之后才能调用，直到下次调用next()）。如果对正在迭代的集合进行了结构更改（即对集合使用添加、删除或清除），迭代器将不再有效（后续使用迭代器将导致抛出ConcurrentModificationException），为了避免迭代器准备将一个项目作为下一个项目给出，然后该项目可能会被删除，我们应该只在需要立即使用迭代器时才获取迭代器。但是，如果迭代器调用自己的remove方法，它仍然有效。2.List接口publicinterfaceListextendsCollection{intsize();booleanisEmpty();Iteratoriterator();Object[]toArray();T[]toArray(T[]a);booleanadd(Ee);booleanremove(Objecto);booleancontainsAll(Collectionc);booleanaddAll(Collectionc);booleanaddAll(intindex,Collectionc);booleanremoveAll(Collectionc);booleanretainAll(Collectionc);voidclear();booleanequals(Objecto);inthashCode();Eget(intindex);Eset(intindex,Eelement);voidadd(intindex,Eelement);Eremove(intindex);intindexOf(Objecto);intlastIndexOf(Objecto);ListIteratorlistIterator();}ListATD有两个流行的实现，ArrayList和LinkedList。ArrayList的优点是get和set调用需要固定时间。缺点是插入新项和删除现有项的开销很大，除非更改ArrayList的末尾。LinkedList的优点是在表的前端进行增删改查需要常数时间。缺点是不容易索引，除非靠近表的端点，否则get的调用开销很大。publicstaticvoidmakeList1(Listlst,intn){lst.clear();for(inti=0;ilst,intn){lst.clear();for(inti=0;ilst){inttotal=0;for(inti=0;ilst){inti=0;while(ilst){for(Integerx:lst){if(x%2==0){lst.remove(x);}}}为了解决上面的问题，我们可以直接使用迭代器的remove方法，这是合法的publicstaticvoidremovEventVer3(Listlst){Iteratoritr=lst.iterator();while(itr.hasNext()){if(itr.next()%2==0){itr.remove();}}}使用Iterator后，LinkedList的remove操作消耗O(n)时间，因为Iterator已经在需要删除的节点上了。即使有了Iterator，ArrayList的remove方法还是O(n^2)，因为数组的个数还是因为删除需要移动。ListIterator接口ListIterator接口扩展了Iterator、hasNext和hasPrevious方法，使其可以从过去或尾部遍历，add在当前位置插入一个新项，set方法改变Iterator调用返回的当前值hasNext或hasPrevious。publicinterfaceListIteratorextendsIterator{booleanhasNext();booleanhasPrevious();voidremove();voidset(Ee);voidadd(Ee);实现一个ArrayList下面，我们自己手写一个ArrayList，并支持泛型，代码如下：publicclassMyArrayListimplementsIterable{privatestaticfinalintDEFAULT_CAPACITY=10;privateT[]mArray;privateintmArraySize;@OverridepublicIteratoriterator(){returnnewArrayIterator();}privateclassArrayIteratorimplementsIterator{privateintcurrentPositon;@OverridepublicbooleanhasNext(){returncurrentPositonmArraySize){thrownewArrayIndexOutOfBoundsException();}returnmArray[position];}publicTset(Tt){returnset(t,mArraySize-1);}publicTset(Tt,intposition){if(position<0||position>mArraySize){thrownewArrayIndexOutOfBoundsException();}Told=mArray[position];mArray[position]=t;returnold;}}值得一提的是，我们不能直接newT[]，而是需要通过下面的代码创建一个泛型数组T[]newArray=(T[])newObject[新容量]；还有一点值得注意的是，在ArrayIterator中使用MyArrayList.this.remove是为了避免和迭代器自己的remove冲突@Overridepublicvoidremove(){MyArrayList.this.remove(--currentPositon);}实现LinkedList，在LinkedList中，最前面节点称为头节点，最后一个节点称为尾节点。这两个附加节点的存在消除了许多特殊情况并大大简化了编码。例如：如果不使用头节点，那么删除第一个节点是一种特殊情况，因为删除时需要重新调整链表到第一个节点的链，并且因为删除算法一般需要访问之前的那个删除的节点Node（如果没有头节点，第一个节点会出现前面没有节点的特殊情况）。publicclassMyLinkedListimplementsIterable{privateNodeheadNote;privateNodeendNote;privateintmSize;privateintmodCount;publicMyLinkedList(){init();}privatevoidinit(){headNote=newNode<>(null,null,null);endNote=newNode<>(null,headNote,null);headNote.mNext=endNote;mSize=0;modCount++;}publicintsize(){returnmSize;}publicbooleanisEmpty(){returnmSize==0;}publicbooleanadd(Tt){addBefore(t,size());returntrue;}publicTget(intindex){Nodetemp=getNode(index,0,size());returntemp.mData;}publicTremove(intposition){NodetempNode=getNode(位置);returnremove(tempNode);}privateTremove(NodetempNode){tempNode.mPre.mNext=tempNode.mNext;tempNode.mNext.mPre=tempNode.mPre;mSize--;modCount++;returntempNode.mData;}publicTset(intindex,Tt){NodetempNode=getNode(index);Told=tempNode.mData;tempNode.mData=t;returnold;}privateNodegetNode(intindex){returngetNode(index,0,size()-1);}私有节点<T>getNode(intindex,intlower,intupper){NodetempNode;if(lower<0||upper>mSize){thrownewIndexOutOfBoundsException();}if(indexindex;i--){tempNode=tempNode.mPre;}}returntempNode;}privatestaticclassNode{privateNodemNext;privateTmData;privateNodemPre;publicNode(Tdata,Nodepre,Nodenext){mData=data;mPre=pre;mNext=next;}}privateclassLinkedListIteratorimplementsIterator{privateNodecurrentNode=headNote.mNext;privateintexpectedModCount=modCount;privatebooleanokToMove;@OverridepublicbooleanhasNext(){returncurrentNode!=endNote;}@OverridepublicTnext(){if(modCount!=expectedModCount){thrownewConcurrentModificationException();}if(!hasNext()){thrownewNoSuchElementException();}Tt=currentNode.mData;currentNode=currentNode.mNext;okToMove=true;returnt;}@Overridepublicvoidremove(){if(modCount!=expectedModCount){thrownewConcurrentModificationException();}if(!okToMove){thrownewIllegalStateException();}MyLinkedList.this.remove(currentNode.mPre);expectedModCount++;okToMove=false;}@OverridepublicIteratoriterator(){returnnewLinkedListIterator();}}1.modCount表示链表自构造以来的变化次数每次调用add或remove都会更新modCount。这个想法是，当创建迭代器时，它将存储集合的modCount。迭代器方法（next或remove）的每次调用都会根据存储在迭代器中的modCount检查链表中的当前modCount，并在两个计数不匹配时抛出ConcurrentModificationException。2、在LinkedListIterator中，currentNode表示包含调用next返回的item的节点。注意当currentNode位于endNote时调用next是非法的。在LinkedListIterator的remove方法中，currentNode保持不变，因为currentNode节点不受前一个节点删除的影响，这一点与ArrayIterator不同。（在ArrayIterator中，item被移动，需要更新current）
