线性表的利用
副标题#e#
线性表的逻辑界说
线性表（Linear List）是由n（n≥0）个数据元素（结点）a1，a2，…，an构成的有限序列。
① 数据元素的个数n界说为表的长度（n=0时称为空表）。
② 将非空的线性表（n＞0）记作：（a1，a2，…，an）
③ 数据元素ai（1≤i≤n）只是个抽象标记，其详细寄义在差异环境下可以差异。
线性表的逻辑布局特征
对付非空的线性表:
① 有且仅有一个开始结点a1，没有直接前趋，有且仅有一个直接后继a2；
② 有且仅有一个终结结点an，没有直接后继，有且仅有一个直接前趋an-1；
③ 其余的内部结点ai（2≤i≤n-1）都有且仅有一个直接前趋ai-1和一个ai+1。
ADT
一个ADT是一个仅由生存的数据范例和大概在这个数据范例长举办的操纵界说的。开拓者们只能通过ADT的操纵要领来会见ADT的属性，并且他们不会知道这个数据范例内部各类操纵是如何实现的。
在Java中，我们经常利用一个接口来给出一个操纵荟萃而不需要透露这些操纵实现的细节。记着一个接口界说了一个要领集而Java类必需实现这个荟萃以便满意它的强制性条件可能实现这个接口的一个实例。
线性表，仓库和行列
当我们谈论ADT的时候，常常会说到线性表，仓库和行列。我们不会接头这些数据布局的细节，但我们会接头为什么它们被称为ADT。
一个线性表是有限个元素的荟萃，其元素以线性的方法举办分列并提供对它的元素的直接会见。一个仓库是一个后进先出（LIFO）的有序线性表，元素从仓库头插手，并从仓库头取出。一个行列是一个先进先出的有序线性表，元素从行列尾插手，并从行列头取出。
线性表，仓库和行列的内部布局可以用很多方法实现。譬喻，我们可以利用一个有序数组可能一个链表来实现每个布局。要害的一点是岂论你如何实现其内部布局，它对外的接口老是稳定的。这使得你可以或许修改可能进级底层的实现进程而不需要改变民众接口部门。
Java 荟萃架构
Java 2软件开拓包（SDK）提供了一些新类来支持大大都常用的ADT。这些类被称为Java荟萃类（雷同于MFC中的荟萃类），它们协同事情从而形成Java 荟萃架构。这个荟萃架构提供了一套将数据暗示成所谓的荟萃抽象数据的接口和类。
java.util.Collection接口被用来暗示任意的成组的工具，也就是元素。这个接口提供根基的诸如添加，删除，和查询这样的操纵。Collection接口还提供了一个iterator要领。iterator要领返回java.util.Iterator接口的一个实例。而Iterator接口又提供了hasNext, next, 和 remove要领。利用Iterator接口提供的要领，你可以从新到尾轮回遍历一个Collection工具中的实例并可以或许安详的删除iterator(游标)所暗示的元素。
java.util.AbstractCollection 是所有荟萃架构类的基本。AbstractCollection 类提供了对 java.util.Collection 接口中除iterator和size要领以外的所有要领的实现。这两个破例的要领由所有担任java.util.AbstractCollection的子类实现。
实现一个接口的类必需提供对所有接口要领的实现。因为荟萃架构中的一些接口要领是可选的，所以必需有一种要领来通知挪用者某种要领没有实现。当一个可选的要领被实现而这个要领又并没有被实现的时候，就会抛出一个UnsupportedOperationException 异常。UnsupportedOperationException 类担任了RuntimeException 类。这使得挪用者可以或许挪用所有的荟萃操纵而不需要把每次挪用都放在一个try-catch对里。
#p#副标题#e#
List线性表
List接口担任了Collection接口并界说了一个答允沟通元素存在的有序荟萃。List接口还附加了一些利用一个数值型索引值并基于元素在线性表中的位置来操纵Collection中元素的要领。这些操纵包罗add,get,set和remove。
List接口还提供了listIterator要领。这个要领返回java.util.ListIterator 接口的一个实例，这个实例可以或许让你从新至尾可能从尾至头的遍历一个线性表。java.util.ListIterator 担任了java.util.Iterator 接口。因此，它支持对它代表的Collection中的元素的添加和修改。
下面的例子演示了如何从后向前遍历一个列表的元素。要完成这个事情，必需在遍历开始之前把ListIterator定位于列表最后一个元素之后。
ListIterator iter = aList.listIterator(aList.size());
while (iter.hasPrevious())
System.out.println(iter.previous().toString());
荟萃架构提供了对List接口的两个实现：LinkedList（链表）和ArrayList（数组列表，即静态列表）。这两个实现都支持对其元素的随时机见。一个ArrayList实例支持数组气势气魄的操纵并支持数组巨细的改变操纵。一个LinkedList的实例则提供了在列表开始和末了添加，删除和提供元素的显式的支持。利用这些新要领，一个措施员可以简朴的把一个LinedList当做仓库可能行列利用，如下：
LinkedList aQueue = new LinkedList(aCollection);
aQueue.addFirst(newElement);
Object anElement = aQueue.removeLast();
LinkedList aStack = new LinkedList(aCollection);
aStack.addFirst(newElement);
Object anElement= aStack.removeFirst();
#p#分页标题#e#
表A中的代码片断利用java.util.ArrayList 和 java.util.LinkedList演示了对java.util.List接口的实现实例的一些常用的操纵。这些操纵包罗添加元素，随时机见元素和显式的在列表尾删除元素。
知其然不知其所以然是大有长处的
ADT提供了一个将工具民众接口中的操纵和其详细的实现分隔的强有力的东西。这使得一个ADT的实现可以不绝变革和演化同时保持其民众接口稳定。Java荟萃架构提供了大量的接口和其实现用来代表根基元素的集归并可以用来建设有用的ADT。
