一、介紹

LinkedList 是一個(gè)雙向鏈表結(jié)構(gòu)（JDK1.6 之前為循環(huán)鏈表，JDK1.7 取消了循環(huán)），在任意位置插入刪除都很方便，但是不支持隨機(jī)取值，每次都只能從一端開始遍歷，直到找到查詢的對(duì)象，然后返回；不過，它不像 ArrayList 那樣需要進(jìn)行內(nèi)存拷貝，因此相對(duì)來說效率較高，但是因?yàn)榇嬖陬~外的前驅(qū)和后繼節(jié)點(diǎn)指針，因此占用的內(nèi)存比 ArrayList 多一些。

LinkedList 采用鏈表存儲(chǔ)，所以對(duì)于add(E e)方法的插入，刪除元素時(shí)間復(fù)雜度不受元素位置的影響，近似 O(1)，如果是要在指定位置i插入和刪除元素的話（(add(int index, Eelement)） 時(shí)間復(fù)雜度近似為o(n))因?yàn)樾枰纫苿?dòng)到指定位置再插入

二、源碼分析

1、LinkedList實(shí)現(xiàn)的接口

如下圖：

觀察上圖：

AbstractSequentialList抽象類：繼承自 AbstractList，是 LinkedList 的父類，是 List 接口 的簡化版實(shí)現(xiàn)，具有雙端隊(duì)列的功能

• List接口：列表，add、set、等一些對(duì)列表進(jìn)行操作的方法
• Deque接口：實(shí)現(xiàn)了雙端隊(duì)列接口Deque，因此具有雙端隊(duì)列的功能
• Serializable接口：主要用于序列化，即：能夠?qū)?duì)象寫入磁盤。與之對(duì)應(yīng)的還有反序列化操作，就是將對(duì)象從磁盤中讀取出來。因此如果要進(jìn)行序列化和反序列化，ArrayList的實(shí)例對(duì)象就必須實(shí)現(xiàn)這個(gè)接口，否則在實(shí)例化的時(shí)候程序會(huì)報(bào)錯(cuò)（java.io.NotSerializableException）。
• Cloneable接口：實(shí)現(xiàn)Cloneable接口的類能夠調(diào)用clone方法，如果沒有實(shí)現(xiàn)Cloneable接口就調(diào)用方法，就會(huì)拋出異常（java.lang.CloneNotSupportedException）。

2、LinkedList中的變量

• transient int size = 0：雙向鏈表節(jié)點(diǎn)數(shù)量size。默認(rèn)初始化值為0，包訪問權(quán)限。
• transient Node<E> first：雙向鏈表的頭節(jié)點(diǎn)。包訪問權(quán)限。
• transient Node<E> last：雙向鏈表的尾節(jié)點(diǎn)。包訪問權(quán)限。

3、LinkedList的構(gòu)造方法

（1）無參構(gòu)造方法

    public LinkedList() {
    }

總結(jié)：無參構(gòu)造方法，此時(shí)雙向鏈表的節(jié)點(diǎn)數(shù)量size為0，雙向鏈表的頭尾節(jié)點(diǎn)為null。

（2）帶集合參數(shù)的構(gòu)造方法

    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

總結(jié)：先將集合轉(zhuǎn)換為數(shù)組，然后將數(shù)組中的元素按照索引順序一個(gè)個(gè)從雙向鏈表的尾部插入到空的雙向鏈表中。

4、LinkedList中的重要方法

（1）靜態(tài)內(nèi)部類Node

    private static class Node<E> {
        //元素
        E item;
        //后驅(qū)指針
        Node<E> next;
        //前驅(qū)指針
        Node<E> prev;
        //構(gòu)造方法
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

（2）add()方法

    public boolean add(E e) {
        //將元素添加到鏈表的尾部
        linkLast(e);
        return true;
    }

    void linkLast(E e) {
        final Node<E> l = last;
        //創(chuàng)建新節(jié)點(diǎn)
        final Node<E> newNode = new Node<>(l, e, null);
        //把之前的尾指針節(jié)點(diǎn)指向新節(jié)點(diǎn)
        last = newNode;
        //如果尾節(jié)點(diǎn)為空，則代表是新鏈表，直接賦值給頭指針；如果不為空，則把尾指針指向新節(jié)點(diǎn)
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        //長度++
        size++;
        //代表對(duì)集合的操作次數(shù)
        modCount++;
    }

通過上述分析，可以看到：add()方法調(diào)用了linkLast()方法，將新節(jié)點(diǎn)插入到鏈表的尾部。在linkLast()方法里對(duì)尾指針last進(jìn)行了判斷，如果尾節(jié)點(diǎn)為空，說明是第一次插入元素，則直接將新節(jié)點(diǎn)賦值給頭指針；如果尾節(jié)點(diǎn)不為空，則將節(jié)點(diǎn)的尾指針指向新節(jié)點(diǎn)即可，然后再將size和modCount自增1。modCount不是LinkedList里的變量，而是來自于AbstractList。

接下來看一下如何在指定位置添加元素：

    public void add(int index, E element) {
        //檢查索引位置
        checkPositionIndex(index);
        //如果和當(dāng)前長度size相等，則直接添加元素到末尾，否則就將元素插入到指定的位置
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));        //node用來獲取給定index處的元素節(jié)點(diǎn)
    }
    //索引校驗(yàn)
    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }
    //linkLast()前面已經(jīng)介紹，這里只展示linkBefore()
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

由上述分析可以看到：在指定位置添加元素的時(shí)候，首先調(diào)用checkPositionIndex()方法判斷下標(biāo)是否越界，然后判斷index是否等于 size，如果相等則添加到末尾，否則將該元素插入的 index 的位置。linkBefore()方法負(fù)責(zé)把元素 e 插入到 succ 之前。

node(index)方法是獲取 index 位置的節(jié)點(diǎn)，它將index與當(dāng)前鏈表的一半進(jìn)行比較，如果比一半小則從頭遍歷，如果比一半大則向后遍歷。

    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;
        }
    }

在前面介紹LinkedList的有參構(gòu)造時(shí)，我們可以看到其調(diào)用了addAll()方法，那么接下來看看這個(gè)方法又是如何實(shí)現(xiàn)的？

    //調(diào)用addAll(index, c)
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
    public boolean addAll(int index, Collection<? extends E> c) {
        //檢查index是否越界
        checkPositionIndex(index);
        //將集合轉(zhuǎn)為數(shù)組
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;
        Node<E> pred, succ;
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }
        //遍歷數(shù)組，將數(shù)組中的元素創(chuàng)建為節(jié)點(diǎn)，并按照順序連接起來
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }
        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }
        //修改當(dāng)前節(jié)點(diǎn)個(gè)數(shù)size的值
        //操作次數(shù)modCount+1
        size += numNew;
        modCount++;
        return true;
    }

（3）remove()方法

如果是刪除指定位置的元素，則先檢查下標(biāo)是否越界，然后再調(diào)用unlink()方法釋放節(jié)點(diǎn)，移除掉指定的元素。

    //移除指定位置的元素
    public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }
    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é)點(diǎn)，則頭節(jié)點(diǎn)后移
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;    //否則就釋放節(jié)點(diǎn)的遷移借宿
            x.prev = null;
        }
        //如果溢出的是尾節(jié)點(diǎn)，則尾節(jié)點(diǎn)前移
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;        //否則就釋放節(jié)點(diǎn)的后一個(gè)元素
            x.next = null;
        }
        //節(jié)點(diǎn)數(shù)據(jù)置為空
        x.item = null;
        size--;
        modCount++;
        return element;
    }

remove(Object o)從該列表中刪除第一個(gè)出現(xiàn)的指定元素（如果存在）。如果此列表不包含該元素，則它將保持不變。

    public boolean remove(Object o) {
        if (o == 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;
    }

除了上述的移除元素方法，還有一些其他的方法，如：removeFirst()、removeLast()、poll()等，這里不再贅述。

（4）set()方法

set()方法通過修改下標(biāo)獲取到下標(biāo)節(jié)點(diǎn)，獲取出舊值返回，把新值賦值元素

    public E set(int index, E element) {
        //檢查索引是否越界
        checkElementIndex(index);
        //獲取到要修改的元素的下標(biāo)
        Node<E> x = node(index);
        //獲取舊值
        E oldVal = x.item;
        //修改
        x.item = element;
        return oldVal;
    }

（5）get()方法

get()方法根據(jù)下標(biāo)獲取元素遍歷找到當(dāng)前元素并返回，遍歷利用的是判斷當(dāng)前獲取元素位于鏈表的前半段還是后半段，前半段則從頭遍歷到當(dāng)前位置返回，后半段則從尾遍歷到當(dāng)前位置返回

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

除此之外，還有g(shù)etFirst()、element()、peek()、peekFirst() 這四個(gè)獲取頭結(jié)點(diǎn)方法，區(qū)別在于對(duì)鏈表為空時(shí)的處理，是拋出異常還是返回null，其中g(shù)etFirst() 和element() 方法將會(huì)在鏈表為空時(shí)，拋出異常；因?yàn)閮?nèi)部都保存了頭節(jié)點(diǎn)所以直接獲取頭節(jié)點(diǎn)就可以。getLast() 方法在鏈表為空時(shí)，會(huì)拋出NoSuchElementException，而peekLast() 則不會(huì)，只是會(huì)返回 null；內(nèi)部保存了尾節(jié)點(diǎn)直接返回即可。

三、總結(jié)

1、LinkedList總結(jié)

• linkedList本質(zhì)上是一個(gè)雙向鏈表，通過一個(gè)Node內(nèi)部類實(shí)現(xiàn)的這種鏈表結(jié)構(gòu)。
• LinkedList能存儲(chǔ)null值。
• LinkedList在刪除和增加等操作上性能好，而ArrayList在查詢的性能上好。
• 從源碼中看，它不存在容量不足的情況。
• LinkedList不光能夠向前迭代，還能像后迭代，并且在迭代的過程中，可以修改值、添加值、還能移除值。
• LinkedList不光能當(dāng)鏈表，還能當(dāng)隊(duì)列使用，這個(gè)就是因?yàn)閷?shí)現(xiàn)了Deque接口。

2、雙向鏈表與雙向循環(huán)鏈表

雙向鏈表就是一個(gè)元素有3個(gè)屬性，一個(gè)向前的指針，一個(gè)向后的指針，一個(gè)當(dāng)前節(jié)點(diǎn)值；雙向就是本節(jié)點(diǎn)既有向后的指向，也有向前的

雙向循環(huán)鏈表的差別在于循環(huán)，雙向鏈表首位不相連，指針都指向空，雙向循環(huán)鏈表是首位相連形成環(huán)狀

3、JDK1.7為什么把雙向循環(huán)鏈表改為雙向鏈表

• 雙向循環(huán)鏈表是通過new一個(gè)headerEntry管理首尾相連得，可以少創(chuàng)建對(duì)象
• 寫操作主要分為2種，一種頭尾插入，一種中間插入；雙向鏈表的有點(diǎn)在于頭尾插入的時(shí)候只需要維護(hù)一個(gè)指針，中間插入2個(gè)沒什么區(qū)別，但實(shí)際使用中頭尾插入是最頻繁的

4、ArrayList 與LinkedList比較

• ArrayList是基于數(shù)組實(shí)現(xiàn)的，LinkedList是基于雙鏈表實(shí)現(xiàn)的。另外LinkedList類不僅是List接口的實(shí)現(xiàn)類，可以根據(jù)索引來隨機(jī)訪問集合中的元素，除此之外，LinkedList還實(shí)現(xiàn)了Deque接口，Deque接口是Queue接口的子接口，它代表一個(gè)雙向隊(duì)列，因此LinkedList可以作為雙向隊(duì)列 ，棧（可以參見Deque提供的接口方法）和List集合使用，功能強(qiáng)大。
• ArrayList是基于索引(index)的數(shù)據(jù)結(jié)構(gòu)，它使用索引在數(shù)組中搜索和讀取數(shù)據(jù)是很快的，可以直接返回?cái)?shù)組中index位置的元素，因此在隨機(jī)訪問集合元素上有較好的性能。Array獲取數(shù)據(jù)的時(shí)間復(fù)雜度是O(1),但是要插入、刪除數(shù)據(jù)卻是開銷很大的，因?yàn)檫@需要移動(dòng)數(shù)組中插入位置之后的的所有元素。LinkedList的隨機(jī)訪問集合元素時(shí)性能較差，因?yàn)樾枰陔p向列表中找到要index的位置，再返回；但在插入，刪除操作是更快的。因?yàn)長inkedList不像ArrayList一樣，不需要改變數(shù)組的大小，也不需要在數(shù)組裝滿的時(shí)候要將所有的數(shù)據(jù)重新裝入一個(gè)新的數(shù)組，這是ArrayList最壞的一種情況，時(shí)間復(fù)雜度是O(n)，而LinkedList中插入或刪除的時(shí)間復(fù)雜度僅為O(1)。ArrayList在插入數(shù)據(jù)時(shí)還需要更新索引（除了插入數(shù)組的尾部）。
• LinkedList需要更多的內(nèi)存，因?yàn)锳rrayList的每個(gè)索引的位置是實(shí)際的數(shù)據(jù)，而LinkedList中的每個(gè)節(jié)點(diǎn)中存儲(chǔ)的是實(shí)際的數(shù)據(jù)和前后節(jié)點(diǎn)的位置。也就是說，ArrayList在查找方面速度快。LinkedList在增刪速度快。
• ArrayList是實(shí)現(xiàn)了基于動(dòng)態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)，LinkedList基于鏈表的數(shù)據(jù)結(jié)構(gòu)。 對(duì)于隨機(jī)訪問get和set，ArrayList覺得優(yōu)于LinkedList，因?yàn)長inkedList要移動(dòng)指針。對(duì)于新增和刪除操作add和remove，LinedList比較占優(yōu)勢，因?yàn)锳rrayList要移動(dòng)數(shù)據(jù)
• 如果應(yīng)用程序?qū)?shù)據(jù)有較多的隨機(jī)訪問，ArrayList對(duì)象要優(yōu)于LinkedList對(duì)象；如果應(yīng)用程序有更多的插入或者刪除操作，較少的隨機(jī)訪問，LinkedList對(duì)象要優(yōu)于ArrayList對(duì)象；不過ArrayList的插入，刪除操作也不一定比LinkedList慢，如果在List靠近末尾的地方插入，那么ArrayList只需要移動(dòng)較少的數(shù)據(jù)，而LinkedList則需要一直查找到列表尾部，反而耗費(fèi)較多時(shí)間，這時(shí)ArrayList就比LinkedList要快。

到此這篇關(guān)于Java中的LinkedList集合詳解的文章就介紹到這了,更多相關(guān)LinkedList集合詳解內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論