Java LinkedList指南

1。簡介

*LinkedListListDeque*接口的雙鏈列表實現, LinkedList元素允許為null,允許重複元素。

2。特點

以下是LinkedList的最重要屬性:

  • 可以從開始或結束遍歷List,以更接近指定元素位置為准
  • 它是非線程同步
  • 它的*IteratorListIterator反覆運算器是快速失敗的(這意味著在創建迭代器之後,如果修改了列表,將拋出ConcurrentModificationException*)
  • 每個元素都是一個節點,LinkedList保留對下一個和前一個元素的引用
  • LinkedList保持插入順序

儘管LinkedList不同步,但是我們可以通過調用Collections.synchronizedList方法來檢索它的同步版本,例如:

List list = Collections.synchronizedList(new LinkedList(...));


## 3.與*ArrayList的*比較

儘管它們都實現了List接口,但是它們具有不同的語義–無疑會影響使用哪個接口的決策。

3.1。結構體

一個ArrayList的是由支持基於索引數據結構陣列。它提供對元素的隨機訪問,其性能等於O(1)。

另一方面,LinkedList將其數據存儲為元素列表,每個元素都鏈接到其上一個和下一個元素。在這種情況下,對項目的搜索操作的執行時間等於O(n)。

3.2。運作方式

LinkedList中,項目的插入,添加和刪除操作更快,因為在將元素添加到集合內的任意位置時,無需調整數組大小或更新索引,僅更改周圍元素中的引用即可。


### **3.3。內存使用情況**

LinkedList消耗比ArrayList使用更多的內存,因為在每一個節點的LinkedList存儲兩個引用,一個用於它的前一個元素,一個用於它的下一個元素,而ArrayList中僅存儲它的元素和它的索引。


## 4.用法

以下是一些代碼示例,展示瞭如何使用LinkedList


### **4.1。創建**
LinkedList<Object> linkedList = new LinkedList<>();

### **4.2。添加元素**

除了標準的add() addAll() 方法外,LinkedList還實現了ListDeque接口,您可以找到*addFirst() addLast() *,分別在開頭或結尾添加元素。

4.3。移除元素

與元素添加類似,此列表實現提供removeFirst() removeLast() 。

此外,還有方便的方法*removeFirstOccurence() removeLastOccurence() *,它們返回布爾值(如果collection包含指定的元素,則為true)。


### **4.4。隊列操作**

Deque接口提供類似隊列的行為(實際上Deque擴展了Queue接口):

linkedList.poll();
linkedList.pop();

這些方法檢索第一個元素並將其從列表中刪除。

之間的區別poll()pop() 方法流行將拋出NoSuchElementException()異常如果爲空鏈表,而poll則返回null。API *pollFirst()*和pollLast()*也可用。

例如,這是push API的使用方式:

linkedList.push(Object o);

它將元素插入為集合的頭部。

LinkedList還有許多其他方法,其中大多數方法對於已經使用過Lists的用戶應該是熟悉的。Deque提供的其他方法可能是“標準”方法的便捷替代方法。

完整的文檔可以在這裡找到。


## 5.結論

ArrayList通常是默認的List實現。

但是,在某些使用情況下,使用LinkedList會更合適,例如,優先選擇LinkedList的插入/刪除時間(例如,頻繁的插入/刪除/更新)會有效的使用內存和更少的訪問時間,。

可以在GitHub上找到代碼示例。