1 表的定義
形如A0,A1,A2,...,An-1的一般的表，這個表的大小是N，當N=0時稱為空表。Ai後繼Ai-1,Ai-1前驅Ai,表中第一個元素是A0，最後一個元素是AN-1。
與這些定義相關的是在表上的操作的集合，printList打印表，makeEmpty清空表，find返回某一項首次出現的位置，insert插入某個元素，remove移除某個元素，findKth返回某個位置上的元素
2 表的實現方式
2.1 表的數組實現
對錶的所有操作均可以通過使用數組來實現。雖然數組是由固定容量創建的，但在需要的時候可以用雙倍的容量來創建一個不同的數組。
1 int [] arr = new int[10];
2
3 ...
4
5 int [] newArr = new int[arr.length*2];
6 for(int i =0;i<arr.length>7 newArr[i]=arr[i];
8 }
9 arr = newArr;
/<arr.length>
數組實現表的形式，可以使得print List以線性時間被執行，而findKth操作則花費常數時間。不過，插入和刪除的花費卻潛藏著昂貴的開銷，特別是對於表的前端進行，數組不是一個很好的選擇，這時候可以考慮使用另一種數據結構：鏈表
2.2 表的鏈表實現
為了避免插入和刪除的線性開銷，需要保證表可以不連續存儲，否則表的每個部分都有可能影響到整體。圖1給出了鏈表的一般想法：
圖1. 一個鏈表
鏈表由一系列的節點組成，這些節點不必在內存中相連，每一個節點均含有表元素和到包含該元素後繼元的節點鏈。為了執行printLis或find(x)，只要從表的第一個節點開始，然後用一些後繼的next鏈遍歷該表即可。
remove方法可以通過修改一個next引用來實現。圖2給出了在原表刪除第三個元素的結果。
圖2. 從鏈表中刪除
insert方法需要使用new操作符從系統去的一個新的節點，此後執行兩次引用的調整。其一般想法如圖3所示，其中虛線表示原來的next引用。
圖3.向鏈表插入
如圖3所示，如果知道變動要發生的地方，那麼向鏈表插入或從鏈表中刪除一項的操作不需要移動很多的項，只設計常數個節點鏈的改變。讓每一個節點持有一個指向其前驅節點的鏈，如圖4所示，構成雙鏈表。
圖4.雙鏈表
3. ArrayList類和LinkedList類
ArrayList類和LinkedList類都實現了List接口，List接口繼承了Collection接口，他們間的繼承關係如圖5所示。
圖5.表的繼承關係
所以無論Arraylist類還是LinkedList類，都包含有接口Collection和List所定義的方法。
collection主要方法:
- boolean add(Object o)添加對象到集合；
- boolean remove(Object o)刪除指定的對象；
- int size()返回當前集合中元素的數量；
- boolean contains(Object o)查找集合中是否有指定的對象；
- boolean isEmpty()判斷集合是否為空；
- Iterator iterator()返回一個迭代器；
- boolean containsAll(Collection c)查找集合中是否有c中的元素；
- boolean addAll(Collection c)將集合c中所有元素添加給該集合；
- void clear()刪除集合中所有元素；
- void removeAll(Collection c)從集合中刪除c集合中也有的元素；
- void retainAll(Collection c)從集合中刪除集合c中不包含的元素。
list主要方法：
- void add(int index,Object element)在指定位置上添加一個對象；
- boolean addAll(int index,Collection c)將集合c的元素添加到指定的位置；
- Object get(int index)返回List中指定位置的元素；
- int indexOf(Object o)返回第一個出現元素o的位置；
- Object remove(int index)刪除指定位置的元素；
- Object set(int index,Object element)用元素element取代位置index上的元素,返回被取代的元素；
- void sort()排序方法。
3.1ArrayList類
ArrayList包含了兩個重要的對象：
- elementData 是"Object[]類型的數組"，它保存了添加到ArrayList中的元素。實際上，elementData是個動態數組，我們能通過構造函數 ArrayList(int initialCapacity)來執行它的初始容量為initialCapacity；如果通過不含參數的構造函數ArrayList()來創建ArrayList，則elementData的容量默認是10。elementData數組的大小會根據ArrayList容量的增長而動態的增長，具體的增長方式，請參考源碼分析中的ensureCapacity()函數。
- size 則是動態數組的實際大小。
ArrayList三種遍歷方法
1//第一種，通過迭代器遍歷。即通過Iterator去遍歷。
2
3Integer value = null;
4Iterator iter = list.iterator();
5while (iter.hasNext()) {
6 value = (Integer)iter.next();
7}
8
9//第二種，隨機訪問，通過索引值去遍歷。
10由於ArrayList實現了RandomAccess接口，它支持通過索引值去隨機訪問元素。
11
12Integer value = null;
13int size = list.size();
14for (int i=0; i<size>15 value = (Integer)list.get(i);
16}
17
18//第三種，for循環遍歷。如下：
19
20Integer value = null;
21for (Integer integ:list) {
22 value = integ;
23}
/<size>
ArrayList使用案例
1package ArrayListPackage;
2import java.util.ArrayList;
3import java.util.Iterator;
4public class ArrayListTest {
5
6 public static void main(String[] args) {
7 // TODO Auto-generated method stub
8
9 //創建一個數組鏈表對象list
10 ArrayList<string> list = new ArrayList<string>();
11
12 //增加元素到list對象中
13 list.add("翟天臨");
14 list.add("陳邑");
15 list.add("張輝");
16 list.add("劉熙陽");
17 list.add("白行朗");
18
19 //顯示數組鏈表中的內容
20 System.out.println("ArrayList 包含如下元素"+list);
21
22 //替換元素
23 list.set(4, "俞建紅");
24 System.out.println("替換後的ArrayList 包含如下元素"+list);
25
26 //檢查元素的位置
27 int position = list.indexOf("陳邑");
28 System.out.println("陳邑在ArrayList中的位置是:"+position);
29
30 //獲取鏈表的大小
31 int size = list.size();
32 System.out.println("ArrayList鏈表的大小為："+size);
33
34 //遍歷ArrayList中所有的元素
35 Iterator<string> it = list.iterator();
36 System.out.println("使用iterator遍歷ArrayList中所有元素");
37 for(;it.hasNext();){
38 System.out.println("ArrayList 元素包括 "+it.next());
39 }
40 }
41
42}
/<string>/<string>/<string>
輸出結果為：
圖6. 輸出結果
3.2 LinkedList類
LinkedList的本質是雙向鏈表，包含兩個重要的對象：
- header是雙向鏈表的表頭，它是雙向鏈表節點所對應的類Entry的實例。Entry中包含成員變量： previous, next, element。其中，previous是該節點的上一個節點，next是該節點的下一個節點，element是該節點所包含的值。
- size是雙向鏈表中節點的個數。
Linked的遍歷方式
1//通過迭代器遍歷。即通過Iterator去遍歷。
2for(Iterator iter = list.iterator(); iter.hasNext();)
3 iter.next();
4
5//通過快速隨機訪問遍歷LinkedList
6int size = list.size();
7for (int i=0; i<size> 8 list.get(i);
9}
10
11//通過另外一種for循環來遍歷LinkedList
12for (Integer integ:list)
13 ;
14
15//通過pollFirst()來遍歷LinkedList
16while(list.pollFirst() != null)
17 ;
18
19//通過pollLast()來遍歷LinkedList
20while(list.pollLast() != null)
21 ;
22
23//通過removeFirst()來遍歷LinkedList
24try {
25 while(list.removeFirst() != null)
26 ;
27} catch (NoSuchElementException e) {
28}
29
30//通過removeLast()來遍歷LinkedList
31try {
32 while(list.removeLast() != null)
33 ;
34} catch (NoSuchElementException e) {
35}
/<size>
LinkedList使用案例
1package LinkedListPackage;
2
3import java.util.Iterator;
4import java.util.LinkedList;
5
6public class LinkedListTest {
7
8 public static void main(String[] args) {
9 // TODO Auto-generated method stub
10
11 //創建一個數組鏈表對象list
12 LinkedList<string> list = new LinkedList<string>();
13
14 //增加元素到list對象中
15 list.add("翟天臨");
16 list.add("陳邑");
17 list.add("張輝");
18 list.add("劉熙陽");
19 list.add("白行朗");
20
21 //顯示數組鏈表中的內容
22 System.out.println("LinkedList包含如下元素"+list);
23
24 //替換元素
25 list.set(4, "俞建紅");
26 System.out.println("替換後的LinkedList包含如下元素"+list);
27
28 //檢查元素的位置
29 int position = list.indexOf("陳邑");
30 System.out.println("陳邑在LinkedList中的位置是:"+position);
31
32 //獲取鏈表的大小
33 int size = list.size();
34 System.out.println("LinkedList鏈表的大小為："+size);
35
36 //遍歷ArrayList中所有的元素
37 Iterator<string> it = list.iterator();
38 System.out.println("使用iterator遍歷LinkedList中所有元素");
39 for(;it.hasNext();){
40 System.out.println("LinkedList元素包括 "+it.next());
41 }
42 }
43}
/<string>/<string>/<string>
輸出結果與圖6一致。
4. ArrayList和LinkedList的區別
ArrayList和LinkedList的區別大致可以總結為：
- ArrayList是實現了基於動態數組的數據結構，LinkedList基於鏈表的數據結構。
- 對於隨機訪問get和set，ArrayList覺得優於LinkedList，因為LinkedList要移動指針。
- 對於新增和刪除操作add和remove，LinedList比較佔優勢，因為ArrayList要移動數據。
閱讀更多 大木叉叉 的文章
