概述

在分析LinkedList的源碼之前，先看一下ArrayList在數(shù)據(jù)結(jié)構(gòu)中的位置，常見的數(shù)據(jù)結(jié)構(gòu)按照邏輯結(jié)構(gòu)跟存儲結(jié)構(gòu)可以做如下劃分：

數(shù)據(jù)結(jié)構(gòu)分類

先看看源碼的注釋：

• Doubly-linked list implementation of the {@code List} and {@code Deque}
  interfaces. Implements all optional list operations, and permits all
  elements (including {@code null}).
  All of the operations perform as could be expected for a doubly-linked
  list. Operations that index into the list will traverse the list from
  the beginning or the end, whichever is closer to the specified index.
• LinkedList是一個實(shí)現(xiàn)了List接口跟Deque的雙鏈表。實(shí)現(xiàn)了所有的List接口的操作，允許存放任意元素(包括空值).能夠進(jìn)行雙鏈表的所有操作插入操作，LinkedList中的索引操作將會從頭到尾遍歷整個鏈表，知道找到具體的索引。

從注釋中可以看出，LinkedList是一個雙向非循環(huán)鏈表，并且實(shí)現(xiàn)了Deque接口，還是一個雙端隊(duì)列，所以比ArrayList要復(fù)雜一些。

正文

鏈表

在分析LinkedList之前我們先復(fù)習(xí)一下鏈表這種數(shù)據(jù)結(jié)構(gòu)

鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動態(tài)生成。每個結(jié)點(diǎn)包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結(jié)點(diǎn)地址的指針域。

鏈表按照指向可以分為單向鏈表跟雙向鏈表，也可以按照是否循環(huán)氛分為循環(huán)鏈表跟非循環(huán)鏈表。

鏈表分類

單向鏈表

單向鏈表

從head節(jié)點(diǎn)開始，next指針只想下一個節(jié)點(diǎn)的數(shù)據(jù)，tail節(jié)點(diǎn)的next指針指向null

雙向鏈表

雙向鏈表

每個節(jié)點(diǎn)有連個指針，pre跟next，除了head節(jié)點(diǎn)pre指針跟tail節(jié)點(diǎn)的next指針都指向null之外，其余的相鄰節(jié)點(diǎn)的指針不管是從頭到尾還是反過來，當(dāng)前節(jié)點(diǎn)的兩個指針包含了相鄰節(jié)點(diǎn)的指向。

單向循環(huán)鏈表

單向循環(huán)鏈表

單向循環(huán)鏈表跟單向鏈表的區(qū)別在于，tail節(jié)點(diǎn)指向head節(jié)點(diǎn)的數(shù)據(jù)

雙向循環(huán)鏈表

雙向循環(huán)鏈表

雙向循環(huán)鏈表跟單向循環(huán)鏈表可以進(jìn)行類比，只是把head節(jié)點(diǎn)的pre指針跟tail節(jié)點(diǎn)的next指針分別指向tail跟head的數(shù)據(jù)區(qū)域而已。

ArrayList源碼分析

先看一下ArrayList的繼承關(guān)系

LinkedList的繼承關(guān)系

• 虛線代表實(shí)現(xiàn)關(guān)系
• 實(shí)線代表繼承，其中藍(lán)色的代表類之間繼承關(guān)系，綠色代表接口之間的繼承關(guān)系

跟ArrayList的區(qū)別在于LinkedList實(shí)現(xiàn)了Deque這個接口，Deque則繼承自Queue這個接口，所以LinkedList能夠進(jìn)行隊(duì)列操作，其余的實(shí)現(xiàn)跟ArrayList基本一樣，不再多說，下面開始分析LinkedList的源碼。

成員變量

//序列化
private static final long serialVersionUID = 876323262645176354L;
transient int size = 0;//元素個數(shù)
transient Node<E> first;//head結(jié)點(diǎn)
transient Node<E> last;//tail節(jié)點(diǎn)

//內(nèi)部類節(jié)點(diǎn)
private static class Node<E> {
    E item;存儲的數(shù)據(jù)
    Node<E> next;//next指針，指向下一個數(shù)據(jù)
    Node<E> prev;//pre指針，指向上一個數(shù)據(jù)

    Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }

構(gòu)造函數(shù)

• 空的構(gòu)造函數(shù)(Constructs an empty list.)

    public LinkedList() {
    }

當(dāng)我們通過此構(gòu)造方法進(jìn)行初始化LinkedList的時(shí)候，實(shí)際上什么都沒做，此時(shí)只有一個Node,data為null，pre指向null，next也指向null。

• 通過Collection來構(gòu)造(Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.)

//調(diào)用addAll
  public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
//緊接著調(diào)用addAll(size, c)
      public boolean addAll(Collection<? extends E> c) {
      return addAll(size, c);
    }
    
  //這個方法比較關(guān)鍵，因?yàn)椴还苁浅跏蓟€是進(jìn)行添加，都會調(diào)用此方法，下面重點(diǎn)分析一下
    public boolean addAll(int index, Collection<? extends E> c) {
         //檢查index是否合法
        checkPositionIndex(index);
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;
        //初始化兩個Node，保留下一個節(jié)點(diǎn)，當(dāng)集合添加完成之后，需要跟此節(jié)點(diǎn)進(jìn)行連接，構(gòu)成鏈表
        Node<E> pred, succ;
          //插入的時(shí)候就是分兩種，一種是從尾部插入，一種是從中間插入
        if (index == size) {
        //在尾部插入
            succ = null;//null值作為后面連接的一個標(biāo)志
            pred = last;//將pred指向上一個節(jié)點(diǎn)也就是tail節(jié)點(diǎn)
        } else {
        //從中間插入
            succ = node(index);
            pred = succ.prev;
        }

        //遍歷集合，按照順序依次插入相應(yīng)的元素
        for (Object o : a) {
            @SuppressWarnings("unchecked") 
            E e = (E) o;
            //初始化一個節(jié)點(diǎn)并進(jìn)行賦值
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
            //頭結(jié)點(diǎn)為空，說明是空鏈表
                first = newNode;
            else
            //Node個數(shù)>0，當(dāng)前指針指向新的節(jié)點(diǎn)
                pred.next = newNode;
            //移到下一個節(jié)點(diǎn)
            pred = newNode;
        }
     //鏈表添加完畢，開始從斷開的地方進(jìn)行連接
        if (succ == null) {
        //尾部插入進(jìn)行連接，此時(shí)last需要重新賦值，即為pred節(jié)點(diǎn)
            last = pred;
        } else {
        //中間插入，直接講集合的最后一個節(jié)點(diǎn)跟之前插入點(diǎn)后的節(jié)點(diǎn)進(jìn)行連接就好
            pred.next = succ;將當(dāng)前Node的next指針指向下一個節(jié)點(diǎn)
            succ.prev = pred;//將下一個節(jié)點(diǎn)的pre指向pre
        }

        size += numNew;
        modCount++;
        return true;
    }

結(jié)合圖形來理解一下

雙向鏈表插入元素

稍微總結(jié)一下，這個addAll實(shí)際上就是先把鏈表打斷，然后從斷的左側(cè)進(jìn)行添加一些元素，添加完成之后再將鏈表進(jìn)行連接起來，恩，就是這個樣子，歸納一下就是：

• 將鏈表打斷，用兩個節(jié)點(diǎn)保留插入位置的下一個節(jié)點(diǎn)
• 在節(jié)點(diǎn)插入完成之后，再進(jìn)行連接
• 需要注意插入的位置：是在尾部還是中間插入，因?yàn)閮烧咦詈筮M(jìn)行鏈表重連的方式不一樣。

add方法

LinkedList的Add方法

通過查看實(shí)際上有很多，這里就不一一貼出來了，最終調(diào)用的都是這幾個方法：

在頭部插入(Links e as first element.)

   private void linkFirst(E e) {
         //拿到頭結(jié)點(diǎn)
        final Node<E> f = first;
        //初始化一個結(jié)點(diǎn)，也即是新的頭結(jié)點(diǎn)
        final Node<E> newNode = new Node<>(null, e, f);
        //將新節(jié)點(diǎn)賦值給頭結(jié)點(diǎn)
        first = newNode;
        //頭結(jié)點(diǎn)為空
        if (f == null)
        //則相當(dāng)于此時(shí)只有一個節(jié)點(diǎn)，尾節(jié)點(diǎn)也是頭結(jié)點(diǎn)
            last = newNode;
        else
        //將原先的頭結(jié)點(diǎn)的pre指針指向新的頭結(jié)點(diǎn)
            f.prev = newNode;
        size++;
        modCount++;
    }

在尾部插入(Links e as last element.)

   void linkLast(E e) {
         //拿到尾節(jié)點(diǎn)
        final Node<E> l = last;
          //初始化一個Node，也就是新的尾節(jié)點(diǎn)
        final Node<E> newNode = new Node<>(l, e, null);
        //將新的尾節(jié)點(diǎn)賦值給last
        last = newNode;
        //尾結(jié)點(diǎn)為空
        if (l == null)
        //此時(shí)只有一個節(jié)點(diǎn)，所以當(dāng)前節(jié)點(diǎn)即是頭結(jié)點(diǎn)也是尾節(jié)點(diǎn)
            first = newNode;
        else
        //將原先的尾節(jié)點(diǎn)指向現(xiàn)在的新的尾節(jié)點(diǎn)
            l.next = newNode;
        size++;
        modCount++;
    }

在某個元素之前插入(Inserts element e before non-null Node succ.)

void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        //拿到要插入的元素之前節(jié)點(diǎn)
        final Node<E> pred = succ.prev;
        //初始化一個節(jié)點(diǎn)
        final Node<E> newNode = new Node<>(pred, e, succ);
        //將下一個節(jié)點(diǎn)的頭指針指向插入的節(jié)點(diǎn)
        succ.prev = newNode;
        if (pred == null)
        //如果此時(shí)只有一個節(jié)點(diǎn)，那么它既是尾節(jié)點(diǎn)也是頭結(jié)點(diǎn)
            first = newNode;
        else
         //將插入的節(jié)點(diǎn)跟前一個節(jié)點(diǎn)進(jìn)行連接
            pred.next = newNode;
        size++;
        modCount++;
    }

remove操作

有如下幾個方法

Remove操作

跟add操作相對應(yīng)，也只是改變相應(yīng)的鏈表的指向而已，我們選擇一個來看看：

   public E remove(int index) {
        checkElementIndex(index);//檢查刪除的索引值
        return unlink(node(index));//刪除節(jié)點(diǎn)
    }
      
      
       E unlink(Node<E> x) {
        // assert x != null;
        //拿到需要刪除的節(jié)點(diǎn)
        final E element = x.item;
        //獲取刪除節(jié)點(diǎn)的下一個節(jié)點(diǎn)
        final Node<E> next = x.next;
         //獲取刪除節(jié)點(diǎn)的上一個節(jié)點(diǎn)
        final Node<E> prev = x.prev;

        if (prev == null) {
        //頭結(jié)點(diǎn)，刪除之后，頭結(jié)點(diǎn)后移
            first = next;
        } else {
        //將刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn)的next指向后一個節(jié)點(diǎn)
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
        //尾結(jié)點(diǎn)，刪除之后，尾節(jié)點(diǎn)前移
            last = prev;
        } else {
        //將刪除節(jié)點(diǎn)的后一個節(jié)點(diǎn)的pre指向前一個節(jié)點(diǎn)
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }
    

說到底還是在改變Node節(jié)點(diǎn)的指向而已

set操作

    public E set(int index, E element) {
        checkElementIndex(index);//檢查索引
        Node<E> x = node(index);//拿到需要修改的那個節(jié)點(diǎn)
        E oldVal = x.item;//拿到修改的節(jié)點(diǎn)的值
        x.item = element;//進(jìn)行修改
        return oldVal;
    }

查詢操作

    public E getFirst() {
        final Node<E> f = first;//拿到head節(jié)點(diǎn)
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }
    
    public E getLast() {
        final Node<E> l = last;////拿到tail節(jié)點(diǎn)
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }
    //獲取某一個索引的節(jié)點(diǎn)
    
    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
    
        Node<E> node(int index) {
        // assert isElementIndex(index);
        
        //二分查找思想進(jìn)行查找
        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;
        }
    }
    

contains操作

        public boolean contains(Object o) {
        return indexOf(o) != -1;
    }
        
        public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
         //遍歷查找
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
    
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

沒有什么好說的，就是遍歷查找而已，這里會發(fā)現(xiàn)，LinkedList的查找很低效，需要遍歷整個集合。

隊(duì)列操作

push

    public void push(E e) {
        addFirst(e);
    }

offer

public boolean offer(E e) {
        return add(e);
    }

peek

    public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }

pop

   public E pop() {
        return removeFirst();
    }

poll

  public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

getFirst

  public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

getLast

   public E getLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }

上面都是關(guān)于隊(duì)列的一些操作，用鏈表也可以實(shí)現(xiàn)，而且操作比較簡單，可以看做是隊(duì)列的一種鏈表實(shí)現(xiàn)方式。

總結(jié)

• 底層是通過雙向鏈表來實(shí)現(xiàn)的，但是并非循環(huán)鏈表。
• 不需要擴(kuò)容，因?yàn)榈讓邮蔷€性存儲
• 增刪快，但是查找比較慢
• 非線程安全