1.定義
實現(xiàn)List接口與Deque接口雙向鏈表本鸣，實現(xiàn)了列表的所有操作，并且允許包括null值的所有元素辽幌，對于LinkedList定義我產(chǎn)生了如下疑問：
1.Deque接口是什么，定義了一個怎樣的規(guī)范?
2.LinkedList是雙向鏈表，其底層實現(xiàn)是怎樣的,具體包含哪些操作?
下文將圍繞這兩個問題進行墙歪，去探尋LinkedList內(nèi)部的奧秘,以下源碼是基于JDK 1.7.0_79
2.結(jié)構(gòu)
2.1 類結(jié)構(gòu)
LinkedList的類的結(jié)構(gòu)如下圖所示
通過上圖可以看出，LinkedList繼承的類與實現(xiàn)的接口如下：
1.Collection 接口： Collection接口是所有集合類的根節(jié)點贝奇，Collection表示一種規(guī)則虹菲，所有實現(xiàn)了Collection接口的類遵循這種規(guī)則
2.List 接口： List是Collection的子接口，它是一個元素有序(按照插入的順序維護元素順序)掉瞳、可重復(fù)毕源、可以為null的集合
3.AbstractCollection 類： Collection接口的骨架實現(xiàn)類，最小化實現(xiàn)了Collection接口所需要實現(xiàn)的工作量
4.AbstractList 類： List接口的骨架實現(xiàn)類陕习，最小化實現(xiàn)了List接口所需要實現(xiàn)的工作量
5.Cloneable 接口： 實現(xiàn)了該接口的類可以顯示的調(diào)用Object.clone()方法霎褐，合法的對該類實例進行字段復(fù)制，如果沒有實現(xiàn)Cloneable接口的實例上調(diào)用Obejct.clone()方法该镣，會拋出CloneNotSupportException異常冻璃。正常情況下，實現(xiàn)了Cloneable接口的類會以公共方法重寫Object.clone()
6.Serializable 接口： 實現(xiàn)了該接口標示了類可以被序列化和反序列化，具體的 查詢序列化詳解
7.Deque 接口： Deque定義了一個線性Collection省艳，支持在兩端插入和刪除元素歌粥，Deque實際是“double ended queue(雙端隊列)”的簡稱，大多數(shù)Deque接口的實現(xiàn)都不會限制元素的數(shù)量拍埠，但是這個隊列既支持有容量限制的實現(xiàn)失驶，也支持沒有容量限制的實現(xiàn)，比如LinkedList就是有容量限制的實現(xiàn),其最大的容量為Integer.MAX_VALUE
8.AbstractSequentialList 類： 提供了List接口的骨干實現(xiàn)枣购，最大限度地減少了實現(xiàn)受“連續(xù)訪問”數(shù)據(jù)存儲(如鏈表)支持的此接口所需的工作嬉探，對于隨機訪問數(shù)據(jù)(如數(shù)組)，應(yīng)該優(yōu)先使用 AbstractList棉圈，而不是使用AbstractSequentailList類
2.2 基礎(chǔ)屬性及構(gòu)造方法
2.2.1 基礎(chǔ)屬性
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
//長度
transient int size = 0;
//指向頭結(jié)點
transient Node<E> first;
//指向尾結(jié)點
transient Node<E> last;
}
如上源碼中為LinkedList中的基本屬性涩堤，其中size為LinkedList的長度，first為指向頭結(jié)點分瘾，last指向尾結(jié)點胎围，Node為LinkedList的一個私有內(nèi)部類，其定義如下德召，即定義了item(元素)白魂，next(指向后一個元素的指針)，prev(指向前一個元素的指針)
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;
}
}
那么假如LinkedList中的元素為["A","B","C"],其內(nèi)部的結(jié)構(gòu)如下圖所示
可以看出一個節(jié)點中包含三個屬性上岗，也就是上面源碼中定義的屬性福荸，可以清晰的看出LinkedList底層是雙向鏈表的實現(xiàn)
2.2.2構(gòu)造方法
在源碼中，LinkedList主要提供了兩個構(gòu)造方法肴掷，
1.public LinkedList() ：空的構(gòu)造方法敬锐，啥事情都沒有做
2.public LinkedList(Collection<? extends E> c) : 將一個元素集合添加到LinkedList中
3.底層實現(xiàn)
在2.2.1中的LinkedList內(nèi)部結(jié)構(gòu)圖，可以清晰的看出LinkedList雙向鏈表的實現(xiàn)呆瞻，下面將通過源碼分析如何在雙向鏈表中添加和刪除節(jié)點的台夺。
3.1 添加節(jié)點
通常我們會使用add(E e)方法添加元素，通過源碼我們發(fā)現(xiàn)add(E e)內(nèi)部主要調(diào)用了以下方法
//在鏈表的最后添加元素
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
其實通過源碼可以看出添加的過程如下：
1.記錄當前末尾節(jié)點痴脾，通過構(gòu)造另外一個指向末尾節(jié)點的指針l
2.產(chǎn)生新的節(jié)點：注意的是由于是添加在鏈表的末尾颤介，next是為null的
3.last指向新的節(jié)點
4.這里有個判斷，我的理解是判斷是否為第一個元素(當l==null時明郭，表示鏈表中是沒有節(jié)點的)买窟，
那么就很好理解這個判斷了，如果是第一節(jié)點薯定，則使用first指向這個節(jié)點始绍，若不是則當前節(jié)點的next指向新增的節(jié)點
5.size增加
例如，在上面提到的LinkedList["A","B","C"]中添加元素“D”话侄，過程大致如圖所示
LinkedList中還提供如下的方法亏推，進行添加元素学赛，具體邏輯與linkLast方法大同小異，就不在這里一一介紹了吞杭。
3.2 刪除節(jié)點
LinkedList中提供了兩個方法刪除節(jié)點盏浇，如下源碼所示
//方法1.刪除指定索引上的節(jié)點
public E remove(int index) {
//檢查索引是否正確
checkElementIndex(index);
//這里分為兩步，第一通過索引定位到節(jié)點芽狗，第二刪除節(jié)點
return unlink(node(index));
}
//方法2.刪除指定值的節(jié)點
public boolean remove(Object o) {
//判斷刪除的元素是否為null
if (o == null) {
//若是null遍歷刪除
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
//若不是遍歷刪除
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
通過源碼可以看出兩個方法都是通過unlink()刪除绢掰，在方法一種有個方法要介紹下，就是node(index)該方法的作用就是根據(jù)下標找到對應(yīng)的節(jié)點童擎，要是本人去寫這個方法肯定是遍歷到index找到對應(yīng)的節(jié)點滴劲，而JDK提供的方法如下所示
1.首先確定index的位置，是靠近first還是靠近last
2.若靠近first則從頭開始查詢顾复，否則從尾部開始查詢班挖，可以看出這樣避免極端情況的發(fā)生，也更好的利用了LinkedList雙向鏈表的特征
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;
}
}
下面會詳細介紹unlink()方法的源碼,這是刪除節(jié)點最核心的方法
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//刪除的是第一個節(jié)點芯砸，first向后移動
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
//刪除的是最后一個節(jié)點萧芙，last向前移
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
1.獲取到需要刪除元素當前的值，指向它前一個節(jié)點的引用假丧，以及指向它后一個節(jié)點的引用双揪。
2.判斷刪除的是否為第一個節(jié)點，若是則first向后移動虎谢，若不是則將當前節(jié)點的前一個節(jié)點next指向當前節(jié)點的后一個節(jié)點
3.判斷刪除的是否為最后一個節(jié)點盟榴，若是則last向前移動，若不是則將當前節(jié)點的后一個節(jié)點的prev指向當前節(jié)點的前一個節(jié)點
4.將當前節(jié)點的值置為null
5.size減少并返回刪除節(jié)點的值
至此介紹了LinkedList添加婴噩、刪除元素的內(nèi)部實現(xiàn)。
4.對比
在ArrList詳解中講解了ArrayList的相關(guān)的內(nèi)容羽德，下面將對ArrayList與LinkedList進行對比几莽，主要從以下方面進行
4.1 相同點
1.接口實現(xiàn)：都實現(xiàn)了List接口，都是線性列表的實現(xiàn)
2.線程安全：都是線程不安全的
4.2 區(qū)別
1.底層實現(xiàn):ArrayList內(nèi)部是數(shù)組實現(xiàn)宅静，而LinkedList內(nèi)部實現(xiàn)是雙向鏈表結(jié)構(gòu)
2.接口實現(xiàn)：ArrayList實現(xiàn)了RandomAccess可以支持隨機元素訪問章蚣，而LinkedList實現(xiàn)了Deque可以當做隊列使用
3.性能：新增、刪除元素時ArrayList需要使用到拷貝原數(shù)組姨夹，而LinkedList只需移動指針纤垂，查找元素 ArrayList支持隨機元素訪問,而LinkedList只能一個節(jié)點的去遍歷
4.3 性能比較
下面通過代碼去比較下ArrayList與LinkedList在性能方面的差別，代碼如下
public class ListPerformance {
private static ArrayList<String> arrayList= new ArrayList<String>();
private static LinkedList<String> linkedList = new LinkedList<String>();
/**
* 插入數(shù)據(jù)
* @param list
* @param count
*/
public static void insertElements(List<String> list, int count){
Long startTime = System.currentTimeMillis();
for (int i = 0; i < count; i++) {
list.add(String.valueOf(i));
}
Long endTime = System.currentTimeMillis();
System.out.println("insert elements use time: " +(endTime-startTime) + " ms");
}
/**
* 刪除元素
* @param list
* @param count
*/
public static void removeElements(List<String> list, int count){
Long startTime = System.currentTimeMillis();
for (int i = 0; i < count; i++) {
list.remove(0);
}
Long endTime = System.currentTimeMillis();
System.out.println("remove elements use time: " +(endTime-startTime) + " ms");
}
/**
* 獲取元素
* @param list
* @param count
*/
public static void getElements(List<String> list, int count){
Long startTime = System.currentTimeMillis();
for (int i = 0; i < count; i++) {
list.get(i);
}
Long endTime = System.currentTimeMillis();
System.out.println("get elements use time: " +(endTime-startTime) + " ms");
}
/**
* 刪除元素第二種實現(xiàn)
* @param list
* @param count
*/
public static void removeElements2(List<String> list, int count){
Long startTime = System.currentTimeMillis();
for (int i = count-1; i > 0; i--) {
list.remove(i);
}
Long endTime = System.currentTimeMillis();
System.out.println("remove elements use time: " +(endTime-startTime) + " ms");
}
public static void main(String[] args){
System.out.println("arrayList test");
insertElements(arrayList,100000);
getElements(arrayList,100000);
removeElements(arrayList,100000);
System.out.println("linkedList test");
insertElements(linkedList,100000);
getElements(linkedList,100000);
removeElements(linkedList,100000);
System.out.println("arrayList test2");
insertElements(arrayList,100000);
getElements(arrayList,100000);
removeElements2(arrayList,100000);
System.out.println("linkedList test2");
insertElements(linkedList,100000);
getElements(linkedList,100000);
removeElements2(linkedList,100000);
}
結(jié)果如下圖所示磷账，可以看出
1.LinkedList下插入峭沦、刪除是性能優(yōu)于ArrayList，這是由于插入逃糟、刪除元素時ArrayList中需要額外的開銷去移動吼鱼、拷貝元素(但是使用removeElements2方法所示去遍歷刪除是速度異常的快蓬豁，這種方式的做法是從末尾開始刪除，不存在移動菇肃、拷貝元素地粪，從而速度非常快)
2.ArrayList在查詢元素的性能上要由于LinkedList
5.總結(jié)
本文主要介紹了LinkedList的內(nèi)部實現(xiàn)琐谤，主要從添加元素蟆技、刪除元素入手分析LinkedList實現(xiàn)的細節(jié)，后面也將LinkedList與ArrayList進行了對比斗忌。
