線性表的邏輯定義
線性表（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對裡。
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();
表A中的代碼片段使用java.util.ArrayList 和 java.util.LinkedList演示了對Java.util.List接口的實現實例的一些常用的操作。這些操作包括添加元素，隨機訪問元素和顯式的在列表尾刪除元素。
知其然不知其所以然是大有好處的
ADT提供了一個將對象公共接口中的操作和其具體的實現分開的強有力的工具。這使得一個ADT的實現可以不斷變化和演化同時保持其公共接口不變。Java集合架構提供了大量的接口和其實現用來代表基本元素的集合並可以用來創建有用的ADT。
