LinkedList是Java List類型的集合類的一種實現，此外，LinkedList還實現了Deque接口。本文基于Java1.8，對于LinkedList的實現原理做一下詳細講解。
（Java1.8源碼：http://docs.oracle.com/javase/8/docs/api/）
一、LinkedList實現原理總結
LinkedList的實現原理總結如下：
①數據存儲是基于雙向鏈表實現的。
②插入數據很快。先是在雙向鏈表中找到要插入節點的位置index，找到之后，再插入一個新節點。 雙向鏈表查找index位置的節點時，有一個加速動作：若index < 雙向鏈表長度的1/2，則從前向后查找; 否則，從后向前查找。
③刪除數據很快。先是在雙向鏈表中找到要插入節點的位置index，找到之后，進行如下操作：node.previous.next = node.next;node.next.previous = node.previous;node = null 。查找節點過程和插入一樣。
④獲取數據很慢，需要從Head節點進行查找。
⑤遍歷數據很慢，每次獲取數據都需要從頭開始。
二、ArrayList的實現原理詳解
（轉自：http://tan4836128.iteye.com/blog/1717809）
1. LinkedList概述：
List?接口的鏈接列表實現。實現所有可選的列表操作，并且允許所有元素（包括?null）。除了實現?List?接口外，LinkedList?類還為在列表的開頭及結尾?get、remove?和?insert?元素提供了統一的命名方法。這些操作允許將鏈接列表用作堆棧、隊列或雙端隊列。
此類實現?Deque?接口，為?add、poll?提供先進先出隊列操作，以及其他堆棧和雙端隊列操作。
所有操作都是按照雙重鏈接列表的需要執行的。在列表中編索引的操作將從開頭或結尾遍歷列表（從靠近指定索引的一端）。
注意，此實現不是同步的。如果多個線程同時訪問一個鏈接列表，而其中至少一個線程從結構上修改了該列表，則它必須?保持外部同步。（結構修改指添加或刪除一個或多個元素的任何操作；僅設置元素的值不是結構修改。）這一般通過對自然封裝該列表的對象進行同步操作來完成。如果不存在這樣的對象，則應該使用?Collections.synchronizedList?方法來“包裝”該列表。最好在創建時完成這一操作，以防止對列表進行意外的不同步訪問，如下所示：
??????????????????? List list = Collections.synchronizedList(new LinkedList(...));
此類的?iterator?和?listIterator?方法返回的迭代器是快速失敗?的：在迭代器創建之后，如果從結構上對列表進行修改，除非通過迭代器自身的?remove?或?add?方法，其他任何時間任何方式的修改，迭代器都將拋出?ConcurrentModificationException。因此，面對并發的修改，迭代器很快就會完全失敗，而不冒將來不確定的時間任意發生不確定行為的風險。
注意，迭代器的快速失敗行為不能得到保證，一般來說，存在不同步的并發修改時，不可能作出任何硬性保證。快速失敗迭代器盡最大努力拋出?ConcurrentModificationException。因此，編寫依賴于此異常的程序的方式是錯誤的，正確做法是：迭代器的快速失敗行為應該僅用于檢測程序錯誤。
?
2. LinkedList的實現：
Java代碼??
private?transient?Entry<E>?header?=?new?Entry<E>(null,?null,?null);???
?
?這個成員變量是LinkedList的關鍵，它在鏈表中沒有實際數據意義，是鏈表的標示（通俗一點就是鏈表的第一個無意義的元素），而且被修飾為transient，標示著他不會被序列化。header也可以當做隊列末尾的元素，因為是雙向列表，所以header.next末尾元素后邊的元素就成了隊首元素，header.previous就是隊尾元素了，看一下它的添加方法
?
Java代碼??
public?void?addFirst(E?paramE)?{??????addBefore(paramE,?this.header.next);//隊首??}??public?void?addLast(E?paramE)?{??????addBefore(paramE,?this.header);//隊尾??}??
?以上兩個方法都利用addBefore方法將元素添加到指定對象之前，
?
?addFirst向隊頭加元素，將元素paramE添加到header.next-隊首元素之前；
?addLast向隊尾加元素，將元素paramE添加到header之前；
?
? ? ? ? ?再看一下addBefore(E e,Entry<E> entry)函數
?
Java代碼??
/***??*?要添加的元素：paramE??*?目標對象：paramEntry??*/??private?Entry<E>?addBefore(E?paramE,?Entry<E>?paramEntry)??{??????//要添加的對象??????Entry?localEntry?=?new?Entry(paramE,?paramEntry,?paramEntry.previous);??????/***??????*?localEntry.previous?=?paramEntry.previous??????*?目標對象的前一元素的后一元素（localEntry.previous.next）設置為要添加的對象??????*/??????localEntry.previous.next?=?localEntry;??????/***??????*?localEntry.next?=?paramEntry??????*?目標對象的前一元素（localEntry.next.previous）設置為要添加的對象??????*/??????localEntry.next.previous?=?localEntry;??????this.size?+=?1;??????this.modCount?+=?1;??????return?localEntry;??}??
?
鏈表的基本特性是插入速度快，遍歷速度慢，下面兩個方法可以反映這個特點
?
Java代碼??
public?int?indexOf(Object?paramObject)?{??????int?i?=?0;??????Entry?localEntry;??????/***??????*?遍歷規則：從頭到尾，序列呈升序狀態??????*/??????if?(paramObject?==?null)??????????for?(localEntry?=?this.header.next;?localEntry?!=?this.header;?localEntry?=?localEntry.next)?{??????????????if?(localEntry.element?==?null)??????????????????return?i;??????????????i++;??????????}??????else?{??????????for?(localEntry?=?this.header.next;?localEntry?!=?this.header;?localEntry?=?localEntry.next)?{??????????????if?(paramObject.equals(localEntry.element))??????????????????return?i;??????????????i++;??????????}??????}??????return?-1;??}??public?int?lastIndexOf(Object?paramObject)?{??????int?i?=?this.size;??????Entry?localEntry;??????/***??????*?遍歷規則：從尾到頭，序列呈降序狀態??????*/??????if?(paramObject?==?null)?{??????????for?(localEntry?=?this.header.previous;?localEntry?!=?this.header;?localEntry?=?localEntry.previous)?{??????????????i--;??????????????if?(localEntry.element?==?null)??????????????????return?i;??????????????}??????}else?{??????????for?(localEntry?=?this.header.previous;?localEntry?!=?this.header;?localEntry?=?localEntry.previous)?{??????????????i--;??????????????if?(paramObject.equals(localEntry.element))??????????????????return?i;??????????}??????}??????return?-1;??}??
?值得注意的是，鏈表插入數據速度快的說法是相對的，在數據量很小的時候，ArrayList的插入速度不僅不比LinkedList慢，而且還快很多（本文不作介紹，讀者可自行測試），只有當數據量達到一定量，這個特性才會體現出來，這需要開發者明確需求場景
LinkedList的方法entry(int index)類似ArrayList的get(int index)
?
Java代碼??
/***??*?根據序號獲取Entry對象??*/??private?Entry<E>?entry(int?paramInt)?{??????if?((paramInt?<?0)?||?(paramInt?>=?this.size))?{??????????throw?new?IndexOutOfBoundsException("Index:?"?+?paramInt?+?",?Size:?"?+?this.size);??????}??????Entry?localEntry?=?this.header;??????int?i;??????/***??????*?二分法：目標序號小于Size的1/2，則從頭到尾??????*?????????????如果大于Size的1/2，則從尾到頭??????*/??????if?(paramInt?<?this.size?>>?1)?{??????????for?(i?=?0;?i?<=?paramInt;?i++)??????????????localEntry?=?localEntry.next;??????}?else?{??????????for?(i?=?this.size;?i?>?paramInt;?i--)??????????????localEntry?=?localEntry.previous;??????}??????return?localEntry;??}??
LinkedList還提供了降序迭代器，如下
?
Java代碼??
public?Iterator<E>?descendingIterator()???{??????????return?new?DescendingIterator(null);??????}??
?
關于降序迭代的具體實現可以看看源碼，很簡單
LinkedList是針對鏈表操作的一個比較全的實現，對于頻繁的數據插入有較高效率，研究其具體實現可更有利于準確的使用它。該類的toArray、clone以及其他一些方法很值得參考。
?
3. LinkedList.Entry
LinkedList的內部類Entry是實現Deque接口的基本操作單元，其結構如下：
?
Java代碼??
private?static?class?Entry<E>??{??????E?element;??????Entry<E>?next;??????Entry<E>?previous;??????/***??????*?構造方法：目標對象paramE將被放置在paramEntry1之前，paramEntry2之后??????*/??????Entry(E?paramE,?Entry<E>?paramEntry1,?Entry<E>?paramEntry2)??????{??????????this.element?=?paramE;??????????this.next?=?paramEntry1;??????????this.previous?=?paramEntry2;??????}??} ?
4. 內部迭代器：ListItr
雖然上層父類AbstractList<E>已經實現了迭代器，但LinkedList的直接父類AbstractSequentialList<E>給子類重新定義個一個需要實現的迭代器的抽象方法，代碼如下：
?
Java代碼??
public?abstract?class?AbstractSequentialList<E>?extends?AbstractList<E>?{??????/***??????*?返回子類實現的迭代器??????*/??????public?Iterator<E>?iterator()?{??????????return?listIterator();??????}??????public?abstract?ListIterator<E>?listIterator(int?paramInt);??}??
?
此處實現的迭代器內部機制跟AbstractList基本一致，可以看看源碼
此類的迭代器的實現機制可以通過ListItr的remove方法來分析，同時也可分析Java對雙端隊列的處理辦法
?
Java代碼??
/***??*?當前指針位置：this.next??*?當前所操作的對象：this.lastReturned??*/??public?void?remove()?{??????checkForComodification();??????LinkedList.Entry?localEntry?=?this.lastReturned.next;??????try?{??????????LinkedList.this.remove(this.lastReturned);??????}?catch?(NoSuchElementException?localNoSuchElementException)?{??????????throw?new?IllegalStateException();??????}??????/***??????*?當鏈表的size為0，指針會指向this.header，其他方法（如set方法）將以此判斷當前操作對象的狀態??????*/??????if?(this.next?==?this.lastReturned)??????????this.next?=?localEntry;??????else??????????this.nextIndex?-=?1;??????/***??????*?調用LinkedList.this.remove(E)之后??????*?當前操作對象this.lastReturned指向的對象被設置為this.header（原對象為null）??????*?指針移動到this.lastReturned.next??????*/??????this.lastReturned?=?LinkedList.this.header;??????//修改次數加1??????this.expectedModCount?+=?1;??} ?
總結
以上是生活随笔為你收集整理的Java LinkedList的实现原理详解的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
