LinkedList是Java List類型的集合類的一種實(shí)現(xiàn)，此外，LinkedList還實(shí)現(xiàn)了Deque接口。本文基于Java1.8，對(duì)于LinkedList的實(shí)現(xiàn)原理做一下詳細(xì)講解。下面就隨動(dòng)力節(jié)點(diǎn)java培訓(xùn)機(jī)構(gòu)看看java linkedlist的實(shí)現(xiàn)原理。

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

　　一、java LinkedList實(shí)現(xiàn)原理總結(jié)

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

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

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

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

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

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

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

　　1、LinkedList概述

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

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

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

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

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

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

　　注意：迭代器的快速失敗行為不能得到保證，一般來(lái)說(shuō)，存在不同步的并發(fā)修改時(shí)，不可能作出任何硬性保證。快速失敗迭代器盡最大努力拋出 ConcurrentModificationException。因此，編寫依賴于此異常的程序的方式是錯(cuò)誤的，正確做法是：迭代器的快速失敗行為應(yīng)該僅用于檢測(cè)程序錯(cuò)誤。

2、LinkedList的實(shí)現(xiàn)

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

　　這個(gè)成員變量是LinkedList的關(guān)鍵，它在鏈表中沒(méi)有實(shí)際數(shù)據(jù)意義，是鏈表的標(biāo)示(通俗一點(diǎn)就是鏈表的第一個(gè)無(wú)意義的元素)，而且被修飾為transient，標(biāo)示著他不會(huì)被序列化。header也可以當(dāng)做隊(duì)列末尾的元素，因?yàn)槭请p向列表，所以header.next末尾元素后邊的元素就成了隊(duì)首元素，header.previous就是隊(duì)尾元素了，看一下它的添加方法。

Java代碼

public void addFirst(E paramE) {  

    addBefore(paramE, this.header.next);//隊(duì)首  

}  

public void addLast(E paramE) {  

    addBefore(paramE, this.header);//隊(duì)尾  

}  

以上兩個(gè)方法都利用addBefore方法將元素添加到指定對(duì)象之前。

 addFirst向隊(duì)頭加元素，將元素paramE添加到header.next-隊(duì)首元素之前；

 addLast向隊(duì)尾加元素，將元素paramE添加到header之前；

        再看一下addBefore(E e,Entryentry)函數(shù)：

Java代碼

/*** 

 * 要添加的元素：paramE 

 * 目標(biāo)對(duì)象：paramEntry 

 */  

private EntryaddBefore(E paramE, EntryparamEntry)  

{  

    //要添加的對(duì)象  

    Entry localEntry = new Entry(paramE, paramEntry, paramEntry.previous);  

    /*** 

     * localEntry.previous = paramEntry.previous 

     * 目標(biāo)對(duì)象的前一元素的后一元素（localEntry.previous.next）設(shè)置為要添加的對(duì)象 

     */  

    localEntry.previous.next = localEntry;  

    /*** 

     * localEntry.next = paramEntry 

     * 目標(biāo)對(duì)象的前一元素（localEntry.next.previous）設(shè)置為要添加的對(duì)象 

     */  

    localEntry.next.previous = localEntry;  

    this.size += 1;  

    this.modCount += 1;  

    return localEntry;  

}  

鏈表的基本特性是插入速度快，遍歷速度慢，下面兩個(gè)方法可以反映這個(gè)特點(diǎn)：

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ù)速度快的說(shuō)法是相對(duì)的，在數(shù)據(jù)量很小的時(shí)候，ArrayList的插入速度不僅不比LinkedList慢，而且還快很多（本文不作介紹，讀者可自行測(cè)試），只有當(dāng)數(shù)據(jù)量達(dá)到一定量，這個(gè)特性才會(huì)體現(xiàn)出來(lái)，這需要開(kāi)發(fā)者明確需求場(chǎng)景。

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

Java代碼

/*** 

 * 根據(jù)序號(hào)獲取Entry對(duì)象 

 */  

private Entryentry(int paramInt) {  

    if ((paramInt < 0) || (paramInt >= this.size)) {  

        throw new IndexOutOfBoundsException("Index: " + paramInt + ", Size: " + this.size);  

    }  

    Entry localEntry = this.header;  

    int i;  

    /*** 

     * 二分法：目標(biāo)序號(hào)小于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);  

    }  

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

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

3、LinkedList.Entry

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

Java代碼

private static class Entry  

{  

    E element;  

    Entrynext;  

    Entryprevious;  

    /*** 

     * 構(gòu)造方法：目標(biāo)對(duì)象paramE將被放置在paramEntry1之前，paramEntry2之后 

     */  

    Entry(E paramE, EntryparamEntry1, EntryparamEntry2)  

    {  

        this.element = paramE;  

        this.next = paramEntry1;  

        this.previous = paramEntry2;  

    }  

}

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

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

Java代碼  

public abstract class AbstractSequentialListextends AbstractList{  

    /*** 

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

     */  

    public Iteratoriterator() {  

        return listIterator();  

    }  

    public abstract ListIteratorlistIterator(int paramInt);  

}  

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

此類的迭代器的實(shí)現(xiàn)機(jī)制可以通過(guò)ListItr的remove方法來(lái)分析，同時(shí)也可分析Java對(duì)雙端隊(duì)列的處理辦法。

Java代碼

/*** 

 * 當(dāng)前指針位置：this.next 

 * 當(dāng)前所操作的對(duì)象：this.lastReturned 

 */  

public void remove() {  

    checkForComodification();  

    LinkedList.Entry localEntry = this.lastReturned.next;  

    try {  

        LinkedList.this.remove(this.lastReturned);  

    } catch (NoSuchElementException localNoSuchElementException) {  

        throw new IllegalStateException();  

    }  

    /*** 

     * 當(dāng)鏈表的size為0，指針會(huì)指向this.header，其他方法（如set方法）將以此判斷當(dāng)前操作對(duì)象的狀態(tài) 

     */  

    if (this.next == this.lastReturned)  

        this.next = localEntry;  

    else  

        this.nextIndex -= 1;  

    /*** 

     * 調(diào)用LinkedList.this.remove(E)之后 

     * 當(dāng)前操作對(duì)象this.lastReturned指向的對(duì)象被設(shè)置為this.header（原對(duì)象為null） 

     * 指針移動(dòng)到this.lastReturned.next 

     */  

    this.lastReturned = LinkedList.this.header;  

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

    this.expectedModCount += 1;  

}  

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

相關(guān)免費(fèi)視頻教程推薦

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