ADT
一個(gè)ADT是一個(gè)僅由保存的數(shù)據(jù)類(lèi)型和可能在這個(gè)數(shù)據(jù)類(lèi)型上進(jìn)行的操作定義的。開(kāi)發(fā)者們只能通過(guò)ADT的操作方法來(lái)訪問(wèn)ADT的屬性，而且他們不會(huì)知道這個(gè)數(shù)據(jù)類(lèi)型內(nèi)部各種操作是如何實(shí)現(xiàn)的。
在Java中，我們常常使用一個(gè)接口來(lái)給出一個(gè)操作集合而不需要透露這些操作實(shí)現(xiàn)的細(xì)節(jié)。記住一個(gè)接口定義了一個(gè)方法集而Java類(lèi)必須實(shí)現(xiàn)這個(gè)集合以便滿(mǎn)足它的強(qiáng)制性條件或者實(shí)現(xiàn)這個(gè)接口的一個(gè)實(shí)例。
線(xiàn)性表，堆棧和隊(duì)列
當(dāng)我們談?wù)揂DT的時(shí)候，經(jīng)常會(huì)說(shuō)到線(xiàn)性表，堆棧和隊(duì)列。我們不會(huì)討論這些數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)，但我們會(huì)討論為什么它們被稱(chēng)為ADT.
一個(gè)線(xiàn)性表是有限個(gè)元素的集合，其元素以線(xiàn)性的方式進(jìn)行排列并提供對(duì)它的元素的直接訪問(wèn)。一個(gè)堆棧是一個(gè)后進(jìn)先出（LIFO）的有序線(xiàn)性表，元素從堆棧頭加入，并從堆棧頭取出。一個(gè)隊(duì)列是一個(gè)先進(jìn)先出的有序線(xiàn)性表，元素從隊(duì)列尾加入，并從隊(duì)列頭取出。
線(xiàn)性表，堆棧和隊(duì)列的內(nèi)部結(jié)構(gòu)可以用許多方式實(shí)現(xiàn)。例如，我們可以使用一個(gè)有序數(shù)組或者一個(gè)鏈表來(lái)實(shí)現(xiàn)每個(gè)結(jié)構(gòu)。關(guān)鍵的一點(diǎn)是不論你如何實(shí)現(xiàn)其內(nèi)部結(jié)構(gòu)，它對(duì)外的接口總是不變的。這使得你能夠修改或者升級(jí)底層的實(shí)現(xiàn)過(guò)程而不需要改變公共接口部分。
Java 集合架構(gòu)
Java 2軟件開(kāi)發(fā)包（SDK）提供了一些新類(lèi)來(lái)支持大多數(shù)常用的ADT.這些類(lèi)被稱(chēng)為Java集合類(lèi)（類(lèi)似于MFC中的集合類(lèi)），它們協(xié)同工作從而形成Java 集合架構(gòu)。這個(gè)集合架構(gòu)提供了一套將數(shù)據(jù)表示成所謂的集合抽象數(shù)據(jù)的接口和類(lèi)。
java.util.Collection接口被用來(lái)表示任意的成組的對(duì)象，也就是元素。這個(gè)接口提供基本的諸如添加，刪除，和查詢(xún)這樣的操作。Collection接口還提供了一個(gè)iterator方法。iterator方法返回java.util.Iterator接口的一個(gè)實(shí)例。而Iterator接口又提供了hasNext， next， 和 remove方法。使用Iterator接口提供的方法，你可以從頭到尾循環(huán)遍歷一個(gè)Collection對(duì)象中的實(shí)例并能夠安全的刪除iterator（游標(biāo)）所表示的元素。
java.util.AbstractCollection 是所有集合架構(gòu)類(lèi)的基礎(chǔ)。AbstractCollection 類(lèi)提供了對(duì)java.util.Collection 接口中除iterator和size方法以外的所有方法的實(shí)現(xiàn)。這兩個(gè)例外的方法由所有繼承java.util.AbstractCollection的子類(lèi)實(shí)現(xiàn)。
實(shí)現(xiàn)一個(gè)接口的類(lèi)必須提供對(duì)所有接口方法的實(shí)現(xiàn)。因?yàn)榧霞軜?gòu)中的一些接口方法是可選的，所以必須有一種方法來(lái)通知調(diào)用者某種方法沒(méi)有實(shí)現(xiàn)。當(dāng)一個(gè)可選的方法被實(shí)現(xiàn)而這個(gè)方法又并沒(méi)有被實(shí)現(xiàn)的時(shí)候，就會(huì)拋出一個(gè)UnsupportedOperationException 異常。UnsupportedOperationException 類(lèi)繼承了RuntimeException 類(lèi)。這使得調(diào)用者能夠調(diào)用所有的集合操作而不需要把每次調(diào)用都放在一個(gè)try-catch對(duì)里。
List線(xiàn)性表
List接口繼承了Collection接口并定義了一個(gè)允許相同元素存在的有序集合。List接口還附加了一些使用一個(gè)數(shù)值型索引值并基于元素在線(xiàn)性表中的位置來(lái)操作Collection中元素的方法。這些操作包括add，get，set和remove.
List接口還提供了listIterator方法。這個(gè)方法返回java.util.ListIterator 接口的一個(gè)實(shí)例，這個(gè)實(shí)例能夠讓你從頭至尾或者從尾至頭的遍歷一個(gè)線(xiàn)性表。java.util.ListIterator 繼承了java.util.Iterator 接口。因此，它支持對(duì)它代表的Collection中的元素的添加和修改。
下面的例子演示了如何從后向前遍歷一個(gè)列表的元素。要完成這個(gè)工作，必須在遍歷開(kāi)始之前把ListIterator定位于列表最后一個(gè)元素之后。
ListIterator iter = aList.listIterator(aList.size());
while (iter.hasPrevious())
System.out.println(iter.previous().toString());
}
集合架構(gòu)提供了對(duì)List接口的兩個(gè)實(shí)現(xiàn)：LinkedList（鏈表）和ArrayList（數(shù)組列表，即靜態(tài)列表）。這兩個(gè)實(shí)現(xiàn)都支持對(duì)其元素的隨機(jī)訪問(wèn)。一個(gè)ArrayList實(shí)例支持?jǐn)?shù)組風(fēng)格的操作并支持?jǐn)?shù)組大小的改變操作。一個(gè)LinkedList的實(shí)例則提供了在列表開(kāi)始和結(jié)尾添加，刪除和提供元素的顯式的支持。使用這些新方法，一個(gè)程序員可以簡(jiǎn)單的把一個(gè)LinedList當(dāng)做堆棧或者隊(duì)列使用，如下：
LinkedList aQueue = new LinkedList(aCollection);aQueue.addFirst(newElement);Object anElement = aQueue.removeLast();LinkedList aStack = new LinkedList(aCollection);aStack.addFirst(newElement);Object anElement= aStack.removeFirst();
表A中的代碼片段使用java.util.ArrayList 和 java.util.LinkedList演示了對(duì)java.util.List接口的實(shí)現(xiàn)實(shí)例的一些常用的操作。這些操作包括添加元素，隨機(jī)訪問(wèn)元素和顯式的在列表尾刪除元素。
知其然不知其所以然是大有好處的
ADT提供了一個(gè)將對(duì)象公共接口中的操作和其具體的實(shí)現(xiàn)分開(kāi)的強(qiáng)有力的工具。這使得一個(gè)ADT的實(shí)現(xiàn)可以不斷變化和演化同時(shí)保持其公共接口不變。Java集合架構(gòu)提供了大量的接口和其實(shí)現(xiàn)用來(lái)代表基本元素的集合并可以用來(lái)創(chuàng)建有用的ADT.
|
