LinkedList是Java List類型的集合類的一種實現(xiàn)，此外，LinkedList還實現(xiàn)了Deque接口。本文基于Java1.8，對于LinkedList的實現(xiàn)原理做一下詳細講解。下面就隨動力節(jié)點java培訓機構看看java linkedlist的實現(xiàn)原理。

　　(Java1.8源碼：http://docs.oracle.com/javase/8/docs/api/)

　　一、java LinkedList實現(xiàn)原理總結

　　Java LinkedList的實現(xiàn)原理總結如下：

　　1、數(shù)據(jù)存儲是基于雙向鏈表實現(xiàn)的。

　    2、插入數(shù)據(jù)很快。先是在雙向鏈表中找到要插入節(jié)點的位置index，找到之后，再插入一個新節(jié)點。 雙向鏈表查找index位置的節(jié)點時，有一個加速動作：若index < 雙向鏈表長度的1/2，則從前向后查找; 否則，從后向前查找。

　　3、刪除數(shù)據(jù)很快。先是在雙向鏈表中找到要插入節(jié)點的位置index，找到之后，進行如下操作：node.previous.next = node.next;node.next.previous = node.previous;node = null 。查找節(jié)點過程和插入一樣。

　　4、獲取數(shù)據(jù)很慢，需要從Head節(jié)點進行查找。

　　5、遍歷數(shù)據(jù)很慢，每次獲取數(shù)據(jù)都需要從頭開始。

　　二、ArrayList的實現(xiàn)原理詳解

　　1、LinkedList概述

　　List 接口的鏈接列表實現(xiàn)。實現(xiàn)所有可選的列表操作，并且允許所有元素(包括 null)。除了實現(xiàn) List 接口外，LinkedList 類還為在列表的開頭及結尾 get、remove 和 insert 元素提供了統(tǒng)一的命名方法。這些操作允許將鏈接列表用作堆棧、隊列或雙端隊列。

　　此類實現(xiàn) Deque 接口，為 add、poll 提供先進先出隊列操作，以及其他堆棧和雙端隊列操作。

　　所有操作都是按照雙重鏈接列表的需要執(zhí)行的。在列表中編索引的操作將從開頭或結尾遍歷列表(從靠近指定索引的一端)。

　　注意：此實現(xiàn)不是同步的。如果多個線程同時訪問一個鏈接列表，而其中至少一個線程從結構上修改了該列表，則它必須 保持外部同步。(結構修改指添加或刪除一個或多個元素的任何操作;僅設置元素的值不是結構修改。)這一般通過對自然封裝該列表的對象進行同步操作來完成。如果不存在這樣的對象，則應該使用 Collections.synchronizedList 方法來“包裝”該列表。最好在創(chuàng)建時完成這一操作，以防止對列表進行意外的不同步訪問，如下所示：

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

　　此類的 iterator 和 listIterator 方法返回的迭代器是快速失敗 的：在迭代器創(chuàng)建之后，如果從結構上對列表進行修改，除非通過迭代器自身的 remove 或 add 方法，其他任何時間任何方式的修改，迭代器都將拋出 ConcurrentModificationException。因此，面對并發(fā)的修改，迭代器很快就會完全失敗，而不冒將來不確定的時間任意發(fā)生不確定行為的風險。

　　注意：迭代器的快速失敗行為不能得到保證，一般來說，存在不同步的并發(fā)修改時，不可能作出任何硬性保證?？焖偈〉鞅M最大努力拋出 ConcurrentModificationException。因此，編寫依賴于此異常的程序的方式是錯誤的，正確做法是：迭代器的快速失敗行為應該僅用于檢測程序錯誤。

2、LinkedList的實現(xiàn)

Java代碼：private transient Entryheader = new Entry(null, null, null);   

　　這個成員變量是LinkedList的關鍵，它在鏈表中沒有實際數(shù)據(jù)意義，是鏈表的標示(通俗一點就是鏈表的第一個無意義的元素)，而且被修飾為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,Entryentry)函數(shù)：

Java代碼

/*** 

 * 要添加的元素：paramE 

 * 目標對象：paramEntry 

 */  

private EntryaddBefore(E paramE, EntryparamEntry)  

{  

    //要添加的對象  

    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;  

    /*** 

     * 遍歷規(guī)則：從頭到尾，序列呈升序狀態(tài) 

     */  

    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;  

    /*** 

     * 遍歷規(guī)則：從尾到頭，序列呈降序狀態(tài) 

     */  

    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;  

}  

值得注意的是，鏈表插入數(shù)據(jù)速度快的說法是相對的，在數(shù)據(jù)量很小的時候，ArrayList的插入速度不僅不比LinkedList慢，而且還快很多（本文不作介紹，讀者可自行測試），只有當數(shù)據(jù)量達到一定量，這個特性才會體現(xiàn)出來，這需要開發(fā)者明確需求場景。

LinkedList的方法entry(int index)類似ArrayList的get(int index)：

Java代碼

/*** 

 * 根據(jù)序號獲取Entry對象 

 */  

private Entryentry(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 IteratordescendingIterator()   {  

        return new DescendingIterator(null);  

    }  

關于降序迭代的具體實現(xiàn)可以看看源碼，很簡單

LinkedList是針對鏈表操作的一個比較全的實現(xiàn)，對于頻繁的數(shù)據(jù)插入有較高效率，研究其具體實現(xiàn)可更有利于準確的使用它。該類的toArray、clone以及其他一些方法很值得參考。

3、LinkedList.Entry

LinkedList的內(nèi)部類Entry是實現(xiàn)Deque接口的基本操作單元，其結構如下：

Java代碼

private static class Entry  

{  

    E element;  

    Entrynext;  

    Entryprevious;  

    /*** 

     * 構造方法：目標對象paramE將被放置在paramEntry1之前，paramEntry2之后 

     */  

    Entry(E paramE, EntryparamEntry1, EntryparamEntry2)  

    {  

        this.element = paramE;  

        this.next = paramEntry1;  

        this.previous = paramEntry2;  

    }  

}

4、內(nèi)部迭代器：ListItr

雖然上層父類AbstractList已經(jīng)實現(xiàn)了迭代器，但LinkedList的直接父類AbstractSequentialList給子類重新定義個一個需要實現(xiàn)的迭代器的抽象方法，代碼如下：

Java代碼  

public abstract class AbstractSequentialListextends AbstractList{  

    /*** 

     * 返回子類實現(xiàn)的迭代器 

     */  

    public Iteratoriterator() {  

        return listIterator();  

    }  

    public abstract ListIteratorlistIterator(int paramInt);  

}  

此處實現(xiàn)的迭代器內(nèi)部機制跟AbstractList基本一致。

此類的迭代器的實現(xiàn)機制可以通過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方法）將以此判斷當前操作對象的狀態(tài) 

     */  

    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;  

    //修改次數(shù)加1  

    this.expectedModCount += 1;  

}  

以上就是動力節(jié)點java培訓機構小編介紹的“Java LinkedList的實現(xiàn)原理”的內(nèi)容，希望能夠幫助到大家，更多java最新資訊請繼續(xù)關注動力節(jié)點java培訓機構官網(wǎng)，每天會有精彩內(nèi)容分享與你。

相關免費視頻教程推薦

java LinkedList視頻教程下載：http://www.soulsinkind.com/xiazai/2483.html