Java 之 List<T> 接口的實現：LinkedList

2014/12/21 來源：cnblogs

Collection

├List

│├LinkedList

│├ArrayList

│└Vector

│└Stack

└Set

Map

├Hashtable

├HashMap

└WeakHashMap

隸屬於隊列List<T>接口下的LinkedList是Java 自實現類的。

如果對應到數據結構中，LinkedList 的樣子其實就是一個雙鍊表（其實可以理解為環形雙向鍊表），所以很多東西（LinkedList的優劣）其實我們可以推倒出來，，這個我會在後期寫一份博文專門比較ArrayList。

首先我們來看LinkedList 的數據結構

👁 Image
...

如圖有一個Header的結點 用來保存List的頭部 同時 Header的pre 指向 整個List 的最後一個Node，而最後一個Node的Next指向header。

LinkedList 有兩個構造函數：

無參數的：直接構造一個只含有header Node的空隊列

有參數的：接收一個Collection參數collection，調用第一個構造方法構造一個空的鍊表，之後通過addAll將collection中的元素全部添加到鍊表中。

一些常用API 如下

（一）增

（1）public boolean add(Object element) 直接添加到隊列末尾

（2）public boolean add(int index, Object element) 根據索引添加

---用作棧時可操作

（3）public boolean addFirst(Object element) 添加到隊列頭部 //ArrayList 無此方法

（4）public boolean addLast(Object element) 添加到隊列末尾

addLast方法和不帶索引的add方法實現的效果一樣.

list.add("D");

list.add(0,"D");

list.addFirst("X");

list.addLast("Z");

（二）刪

(1)清除數據clear

(2)LinkedList.remove(Object) 刪除指定元素

(3)LinkedList.removeAll 刪除指定list

remove返回的Obj為刪掉的元素 主要有三個方法：

（4）public Object remove(int index) 根據索引刪除

---用作隊棧時可操作

（5）public Object removeFirst 刪除到隊列頭部

（6）public Object removeLast 刪除到隊列末尾

list.remove(0);

list.removeFirst;

list.removeLast;

（三）查

（1）indexOf(Object o)判斷o鍊表中是否存在節點的element和o相等，若相等則返回該節點在鍊表中的索引位置，若不存在則放回-1。

（2）contains(Object o)方法通過判斷indexOf(Object o)方法返回的值是否是-1來判斷鍊表中是否包含對象o。

（3）Get(int index) 獲取指定索引下的數據

（4）getFirst:從鍊表的表頭開始去（棧的入口處），//ArrayList沒有這個方法

-------以下操作模仿隊棧操作------

（4） 獲取最初元素System.out.println("鍊表的第一個元素是 : " + lList.getFirst);

（5）獲取最後元素System.out.println("鍊表最後一個元素是 : " + lList.getLast);

（四）生成新的List

（1）截取生成新的List

List subl = lList.subList(1, 4);

（2）數據複製clone

調用父類的clone方法初始化對象鍊表clone，將clone構造成一個空的雙向循環鍊表，之後將header的下一個節點開始將逐個節點添加到clone中。最後返回克隆的clone對象。

（3）toArray

創建大小和LinkedList相等的數組result，遍歷鍊表，將每個節點的元素element複製到數組中，返回數組。

注意：

LinkedList是無容量限制的；

LinkedList是非線程安全的；

參考資料;

http://wenku.baidu.com/link?url=gOmQ2zaIBAoYeaoIoswqo1Ygc3Kp9xDbGil_qjw_GKnKMEE8iOprNMh2mG_euHIeoK9nYhjHCiVrfrf-LRVC2vn-SerJbfWmzIT8MPj2tVy

免責聲明：本文內容來源于cnblogs，文章觀點不代表壹讀立場，如若侵犯到您的權益，或涉不實謠言，敬請向我們提出檢舉。