前言：
本文主要基于JDK9,對LinkedList源碼進行簡單分析，主要內(nèi)容分為以下幾個部分：
1.LinkedList中add(),get()方法的源碼分析及LinkedList雙向鏈表的底層實現(xiàn)
2.LinkedList和ArrayLIst對比
3.RandomAccess接口和Deque的對比分析
1.LinkedList中add(),get()方法的源碼分析及LinkedList雙向鏈表的底層實現(xiàn)
首先，我們在Idea中new一個LinkedList:
List list = new LinkedList();
然后，直接list.來看看LinkedList提供了哪些方法？
一個個看下來發(fā)現(xiàn)，幾乎和ArrayList一毛一樣對，就是幾乎一樣。同樣的方法熟悉的味道那既然都有ArrayList了，為啥還搞個幾乎一樣的LinkedList?
這個問題很好，因為它觸及到了ArrayList和LinkedList的底層，他們雖然功能看上去一樣，但底層實現(xiàn)則完全不同，ArrayList的底層是Object[]數(shù)組，這個我們都知道了，LinkedList底層是鏈表，這個鏈表是怎么實現(xiàn)的？具體和數(shù)組有哪些不同，我們現(xiàn)在還是通過get()和add()方法來看一下源碼吧~看完就知道了！
看源碼前幾句會發(fā)現(xiàn)，LinkedList繼承自AbstractSequentialList類，實現(xiàn)了List、Deque、Cloneable、Serializable接口，細(xì)心的你可能會發(fā)現(xiàn)，和ArrayList有些區(qū)別，ArrayList實現(xiàn)了RandomAccess接口，但沒有實現(xiàn)Deque接口，這個留到最后再討論。
來看一下LinkedList的成員變量有size、Node<E> first; Node<E> last;這個Node節(jié)點是干什么用的？而且還有一個first，一個last？難道是鏈表的頭節(jié)點尾節(jié)點？
答案是:yes
這個Node<E> first，就是用于標(biāo)志鏈表表頭的頭結(jié)點，Node<E> last是對應(yīng)的鏈表尾部的尾節(jié)點。size是成員變量，用于標(biāo)志LinkedList中對象的個數(shù)。
現(xiàn)在，來看一下add()方法吧：
public boolean add(E e) {
linkLast(e);
return true;
}
很簡單add()方法調(diào)用了linkLast()方法，然后返回boolean類型的true。這個linkLast()方法很形象，一看方法名就知道此方法的作用是將元素e添加到鏈表尾部。點進去看看是不是？
果然沒猜錯！讓我們一行行地過一遍：
void linkLast(E e) {
final Node<E> l = last; //last節(jié)點賦給l
//新建一個新節(jié)點newNode，l、e、和null作為參數(shù)
final Node<E> newNode = new Node<>(l, e, null);
//新節(jié)點賦給last
last = newNode;
if (l == null)//若l為空，即初始last為空，則表明LinkedList為空將newNode作為first節(jié)點
first = newNode;
else//否則將newNode連接到last節(jié)點的下一位
l.next = newNode;
size++;//LinkedList中對象數(shù)量+1
modCount++;//modCount值+1
}
linkLast方法主要就是new了一個新的Node節(jié)點，并將要添加的值放入節(jié)點中，然后根據(jù)last節(jié)點是否為空來決定newNode作為first節(jié)點還是直接鏈接到last節(jié)點后。
讓我們點進去Node的構(gòu)造方法看一下，節(jié)點里有什么？
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
可以看到，這個Node節(jié)點類，是個內(nèi)部類，主要包含3個成員變量：
1.item
2.Node<E> next;
3.Node<E> prev;
原來，這個Node<E>節(jié)點就是LinkedList中最底層的鏈表的節(jié)點，item，即存放要存儲的對象；next節(jié)點是用于指向下一個節(jié)點的指針，prev是指向上一個節(jié)點的指針。為什么要用兩個指針呢？因為LinkedList是雙向鏈表需要兩個指針分別指向前后節(jié)點。
add方法好簡單啊，看的不太過癮啊~我們再看下get()方法的實現(xiàn)吧，看看通過索引index = i時get(i)是怎么實現(xiàn)的？
get()方法源碼實現(xiàn)：
可以看到get方法也很少，就3行代碼：
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
通過索引get(index)訪問元素時，首先會調(diào)用checkElementIndex方法檢測索引范圍是否異常，如果索引<0或者>=LinkedList中所包含的對象個數(shù)，則throw一個IndexOutOfBoundsException異常。如果沒有異常，則繼續(xù)執(zhí)行return node(index).item;
這注意下，node(index)是個方法，而不是node節(jié)點，讓我們看看這個有意思的方法：
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
此node方法主要用于查找鏈表中給定index的元素，如果index小于size/2，則從頭部遍歷鏈表，直到找到索引index對應(yīng)的元素，然后return；如果index>=size/2，則從尾部開始遍歷鏈表。是不是很有意思呢？哈哈
2.LinkedList和ArrayLIst對比
首先，讓我們來復(fù)習(xí)下ArrayLIst的特點：
首先，讓我們回顧一下ArrayList的結(jié)構(gòu)圖，可見ArrayList繼承自抽象類AbstractList，實現(xiàn)了Cloneable,Serializable,RandomAccess,以及List接口，這個我們已經(jīng)很熟了?，F(xiàn)在，讓我們看一下集合類庫中另一種和ArrayList很相似卻又很不一樣的類——LinkedList
LinkedList繼承自AbstractSequentialList,實現(xiàn)了Cloneable,Serializable,Deque以及List接口。
那么和ArrayList相比，出了直接繼承自AbstractSequentialList，實現(xiàn)的接口也略有差異，我們可以看到ArrayList實現(xiàn)了RandomAccess接口而LinkedList實現(xiàn)了Deque接口，那么問題來了，這兩個接口的差異會不會和LinkedList以及ArrayList的底層有關(guān)？
答案是YES
我們知道，ArrayList的底層是Object數(shù)組（Object[]），數(shù)組在內(nèi)存空間中是一塊聯(lián)系的內(nèi)存，訪問時除了遍歷外，還可以根據(jù)數(shù)組下標(biāo)index實現(xiàn)高效隨機訪問，時間復(fù)雜度為O(1)，所以ArrayList必然是要實現(xiàn)RandomAccess接口的。
作為對比，LinkedList雖然和ArrayList的方法類似，也能通過get(index)來訪問對象，但是LinkedList的get()是通過遍歷底層以node節(jié)點鏈接的鏈表而實現(xiàn)的，只是表面看上去和Object[]中的get()類似罷了，實際上效率差遠(yuǎn)了，時間復(fù)雜度為O(n)
3.RandomAccess接口和Deque的對比分析
RandomAccess
中文字面意思，表示隨機存取，讓我們進入此接口看看里面有什么方法？
除了一大串注釋外，并沒有具體的方法。好吧，那讓我們看看注釋吧：
/**
** Marker interface used by {@code List} implementations to indicate that
** they support fast (generally constant time) random access. The primary
** purpose of this interface is to allow generic algorithms to alter their
** behavior to provide good performance when applied to either random or
** sequential access lists.*
簡單翻譯下，意思是：
標(biāo)記接口，被實現(xiàn)類實現(xiàn)后表示此類支持隨機存取。這個接口的首要目的是：
允許通用算法在應(yīng)用于隨機存取或順序存取列表時改變其行為以提供良好的性能
意思是，此接口不提供方法，僅僅起標(biāo)記作用，實現(xiàn)了此接口的類即表示此類支持隨機存取，方便后面對此類進行進一步的操作和選擇更優(yōu)化的方法。上一篇我們看到了ArrayList的底層其實是數(shù)組，是個Object[]，數(shù)組在堆內(nèi)存中的排列是線性順序排列，一個裝了n個元素的ArrayList其通過0~n-1之間的任意下標(biāo)i來查找到對應(yīng)元素的時間復(fù)雜度開銷為O(1)，所以說ArrayList是支持隨機訪問的，那么毫無疑問其應(yīng)該實現(xiàn)RandomAccess這個接口。
作為對比，如果一個類底層為鏈表，那么我要訪問任意一個下標(biāo)為i的元素需要從第一個元素開始找一直遍歷前0~i-1個元素后才能找到第i個元素，于是時復(fù)雜度為O(n)，這樣如果這個類中元素數(shù)量很多，那么尋找過程就顯得很慢，那么這個訪問就不能叫做隨機訪問，而是線性訪問。實現(xiàn)了Deque接口的LinkedList就是這樣一種鏈表作為底層的數(shù)據(jù)結(jié)構(gòu)，而且是雙向鏈表，所以LinkedList沒有實現(xiàn)RandomAccess接口，而是實現(xiàn)了Deque接口。
那么問題來了：
Deque是干嘛的？
Deque接口，是表示包含雙端隊列方法的接口。Deque，全名double-ended queue）是一種具有隊列和棧的性質(zhì)的數(shù)據(jù)結(jié)構(gòu)。雙端隊列中的元素可以從兩端彈出，其限定插入和刪除操作在表的兩端進行。學(xué)過數(shù)據(jù)結(jié)構(gòu)的童鞋們應(yīng)該都知道，雙端隊列是個全能的數(shù)據(jù)結(jié)構(gòu)，頭尾兩段都可以執(zhí)行插入和刪除操作，一定條件下，還可以當(dāng)做?；蜿犃惺褂谩５荍ava中Deque用到的其實并不是很多，實現(xiàn)類有ArrayLisr、ArrayDeque、LinkedBlockingDeque。
讓我們來看一下Deque接口中有哪些方法吧：
可見繼承自Queue的Deque是集大成者，方法是相當(dāng)?shù)亩??？匆幌路椒ㄉ献髡哔N心的注釋發(fā)現(xiàn)，Deque中，除了Queue中的方法外還包含Stack棧的方法，Collection集合類的部分方法以及自己獨特的方法。一句話概括下，Deque既可以當(dāng)隊列，還可以當(dāng)做棧，還可以用于集合類。
看一下Deque中獨特的方法：
void addFirst(E e); //頭部添加元素,失敗報異常
void addLast(E e); //...
boolean offerFirst(E e); //頭部添加元素,失敗返回false
boolean offerLast(E e); //...
removeFirst(); //刪除頭部元素,空則報異常
removeLast(); //...
pollFirst(); //刪除頭部元素,空則返回null
pollLast(); //...
getFirst(); //取頭部元素,不刪除,空則報異常
getLast(); //...
peekFirst(); //取頭部元素,不擅長,空則返回null
peekLast();
至此，我們隊Deque就有個比較清晰的了解了，至此LinkedList就告一段落了。
下篇文章：Java集合框架—HashMap—源碼深入分析1 介紹的是HashMap的底層原理和源碼研讀。喜歡的親，請點個??吧~
