文章目錄

前言
初識LinkedList
源碼解析
- 添加元素
- 删除元素
- 更改元素
- 查詢元素
- 内部類
LinkedList 和 ArrayList 的對比

前言

上篇文裡講解了ArrayList ，它是基于List 接口來實作的，今天講解Java集合類中另一個跟List相關的集合類，叫做LinkedList 。

初識LinkedList

LinkedList 是基于雙向連結清單實作的，也就是說，連結清單中任何一個存儲單元都可以通過向前或者向後的指針擷取到前面或者後面的存儲單元。在 LinkedList 的源碼中，其存儲單元用一個Node 類表示：

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

可以看到，Node 中包含了三個成員，分别是存儲資料的

item

，指向前一個存儲單元的節點

prev

和指向後一個存儲單元的節點

next

，用圖檔來表示就是這樣：

Java集合類：LinkedList前言初識LinkedList源碼解析LinkedList 和 ArrayList 的對比

源碼解析

依照慣例，深入源碼前先看下類中的成員變量

transient int size = 0;				//連結清單長度

/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;			//指向頭一個節點

/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;				//指向最後一個節點

知道變量後就是對具體方法的解析了。之前就說過，對一個集合類我們都是最關注的就是它的增删改查元素操作，了解了這些操作的源碼也就基本了解容器的核心思想了。

先看添加元素的方法源碼。

添加元素

LinkedList 中包含了不少插入元素的方法，就使用來說，我們一般調用下面這三個方法：

transient int size = 0;			//連結清單長度

//普通插入方法，直接添加元素到尾部
public boolean add(E e) {
    linkLast(e);
    return true;
}
//在指定位置添加元素
public void add(int index, E element) {
	//判斷index是否在範圍内
    checkPositionIndex(index);
	//如果指定位置是尾部，就直接添加到尾部
    if (index == size)
    linkLast(element);
    //否則插入到指定位置
    else
    linkBefore(element, node(index));
}
//添加一整個集合
public boolean addAll(Collection<? extends E> c) {
   return addAll(size, c);
}

三個方法的代碼比較簡單，其核心邏輯是調用其他的方法來實作，我們可以看到源碼中調用了幾個方法：

linkLast(e)

、

linkBefore(e)

、

addAll(e)

，下面他們的源碼：

//插入到頭部
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++;
}
//在指定節點前插入一個元素，注意這裡是假設插入的元素不為null
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    // 擷取指定節點 succ 前面指向的節點
    final Node<E> pred = succ.prev;
    //建立一個節點，向前指針指向pred，向後指向 succ 節點，資料為 e
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    //如果 succ 前面的節點為空，直接把新節點作為連結清單的頭結點
    if (pred == null)
    first = newNode;
    else
    pred.next = newNode;
    size++;
    modCount++;
 }
 //添加一個集合對象
 public boolean addAll(Collection<? extends E> c) {
     return addAll(size, c);
 }
 //在指定位置添加一個集合
 public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);
		// 把集合對象轉成數組
        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;
        }
		//周遊要添加内容的數組
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            //建立新節點，前指針指向 pred
            Node<E> newNode = new Node<>(pred, e, null);
            //如果 pred 為空，說明建立的這個是頭節點
            if (pred == null)
                first = newNode;
            else
            	//建立節點為pred 後指針指向的節點
                pred.next = newNode;
            //pred 後移一位
            pred = newNode;
        }
		//如果 succ 為空，說明要插入的位置就是尾部，現在 pred 已經到最後了
        if (succ == null) {
            last = pred;
        } else {
        //否則 pred 指向後面的元素
            pred.next = succ;
            succ.prev = pred;
        }

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

幾個方法的邏輯并不複雜，基本都是通過改變要插入位置的節點的指針指向來插入元素，這樣一來插入元素的複雜度就為O(1)，性能是比較好的。

删除元素

LinkedList 中删除元素的方法也是比較多的，我們隻介紹常用的幾個

//删除頭部節點
public E remove() {
    return removeFirst();
}
//删除第一個元素
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
    throw new NoSuchElementException();
    return unlinkFirst(f);
}
//删除最後的元素
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
    throw new NoSuchElementException();
    return unlinkLast(l);
}
//删除指定位置節點
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}
//删除包含指定元素的節點
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;
    }

源碼中可以看出，删除方法中調用了幾個方法，例如

unlinkFirst

，

unlink

，

unlinkLast

，跟添加元素的方法相似，這幾個方法也是通過修改對應節點的前後節點指向來操作元素位置，并把對應位置的節點置為null。

//删除頭節點，并傳回該節點的資料
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC，置為null,友善GC回收
    //把頭節點後面的節點變成第一個節點
    first = next;
    //如果next為空，說明删除的節點是連結清單唯一的節點
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}
//删除尾部節點并傳回資料
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    if (prev == null)
    	first = null;
    else
    	prev.next = null;
    size--;
    modCount++;
    return element;
}
//删除指定的節點，傳回資料    
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;
	//前面沒有節點，說明隻有連結清單隻有一個節點
    if (prev == null) {
    	first = next;
    } else {
    	//前面有節點，直接讓前節點指向後節點
    	prev.next = next;
    	x.prev = null;
    }

    if (next == null) {
    	last = prev;
    } else {
    	next.prev = prev;
    	x.next = null;
    }

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

更改元素

更改元素的方法比較簡單，開放的方法隻有一個，那就是

set

public E set(int index, E element) {
    checkElementIndex(index);
    //擷取對應位置節點
    Node<E> x = node(index);
    //更改資料
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}
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;
    }
 }

查詢元素

因為實作了 List 接口，LinkedList 的查詢方法也是比較豐富的，最直接的就是使用 get()

//擷取對應索引的元素，調用的node的周遊操作
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

還有重寫了List 接口中的

indexOf

，

lastIndexOf

等，

//傳回指定元素第一次出現的位置
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;
}
//查詢最後一次出現的位置
public int lastIndexOf(Object o) {
        int index = size;
        if (o == null) {
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (x.item == null)
                    return index;
            }
        } else {
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (o.equals(x.item))
                    return index;
            }
        }
        return -1;
    }

值得說明的是，LinkedList 的查詢方法都是通過周遊連結清單的方式進行的，如果連結清單的資料過長，那麼查找某個元素所需的時間将會耗費很多，從這點上看，LinkedList 查詢的效率是比較差的。

内部類

關鍵的增删改查方法就說到這兒了，從原理上其實并不複雜，本質上都是針對節點的前後節點指向操作。除了這些方法外，LinkedList 中還提供了幾個内部類，其中就包括了可以逆向輸出元素的疊代器

DescendingIterator

，這是Jdk1.6之後加進來的

public Iterator<E> descendingIterator() {
    return new DescendingIterator();
}
/**
 * Adapter to provide descending iterators via ListItr.previous
 */
 //逆向周遊元素，其實就是從最後一個一直往前周遊
private class DescendingIterator implements Iterator<E> {
    private final ListItr itr = new ListItr(size());
    public boolean hasNext() {
        return itr.hasPrevious();
    }
    public E next() {
        return itr.previous();
    }
    public void remove() {
        itr.remove();
    }
}

以及一個類似Iterator 接口的類

ListItr

，可以幫我們對List進行周遊，增删改查等，其實就跟 LinkedList 的内部操作元素方法差不多，這裡展示部分的源碼

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    private int expectedModCount = modCount;

    ListItr(int index) {
        // assert isPositionIndex(index);
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

    public boolean hasNext() {
        return nextIndex < size;
    }

    public E next() {
        checkForComodification();
        if (!hasNext())
            throw new NoSuchElementException();

        lastReturned = next;
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }

    public boolean hasPrevious() {
        return nextIndex > 0;
    }

    ..........
}

還有Jdk1.8之後加的一個特殊類

LLSpliterator

，大概用途是将元素分割成多份，開啟多個線程去做周遊，以提高效率。我大概看了一下，具體的内部實作還是挺有東西的，因為用的不多，我對于這個内部類也不是特别了解，就不多班門弄斧了，順便也貼下部分代碼吧，

@Override
public Spliterator<E> spliterator() {
    return new LLSpliterator<E>(this, -1, 0);
}

/** A customized variant of Spliterators.IteratorSpliterator */
static final class LLSpliterator<E> implements Spliterator<E> {
    static final int BATCH_UNIT = 1 << 10;  // batch array size increment
    static final int MAX_BATCH = 1 << 25;  // max batch array size;
    final LinkedList<E> list; // null OK unless traversed
    Node<E> current;      // current node; null until initialized
    int est;              // size estimate; -1 until first needed
    int expectedModCount; // initialized when est set
    int batch;            // batch size for splits

    LLSpliterator(LinkedList<E> list, int est, int expectedModCount) {
        this.list = list;
        this.est = est;
        this.expectedModCount = expectedModCount;
    }

    final int getEst() {
        int s; // force initialization
        final LinkedList<E> lst;
        if ((s = est) < 0) {
            if ((lst = list) == null)
                s = est = 0;
            else {
                expectedModCount = lst.modCount;
                current = lst.first;
                s = est = lst.size;
            }
        }
        return s;
    }
    ........
 }

LinkedList 和 ArrayList 的對比

源碼方面的學習就到這裡了，最後說一個老生常談的問題，那就是關于LinkedList 和 ArrayList 兩者之間的比較，這也是比較常見的面試題，大概也就這麼幾點：

結構

LinkedList 是雙向連結清單結構，ArrayList 是基于數組

添加、删除效率

LinkedList 中添加/删除元素隻會影響周圍的兩個節點，開銷較低；
ArrayList 添加、删除時該元素後面的所有元素都要移動，是以添加/删除資料效率不高；

占用記憶體

LinkedList 的節點不僅要維護資料，還有維護前後兩個節點，一般情況下，耗用記憶體高于ArrayList

查詢速度

ArrayList 基于數組，查詢的時候直接根據索引找到元素，時間複雜度為O(1)；
LinkedList查詢時隻能做順序周遊，要麼從頭結點開始周遊，要麼從尾節點開始周遊，比起按索引搜尋元素慢多了，是以查詢效率不高；

線程安全

兩者的方法都沒有做同步，是非線程安全的，如有需要，可用 Collections.synchronizedList 來包住容器執行個體。

Java集合類：LinkedList前言初識LinkedList源碼解析LinkedList 和 ArrayList 的對比

文章目錄

前言

初識LinkedList

源碼解析

添加元素

删除元素

更改元素

查詢元素

内部類

LinkedList 和 ArrayList 的對比

繼續閱讀

interface可以多繼承嗎

Java集合類面試題總結Java集合類面試題

ArrayList初見

集合初始化大小彙總

LinkedHashSet詳解LinkedHashSet詳解

ArrayList源碼剖析1. 屬性2. 構造器3. get 方法4. add 方法5. set 方法6. remove方法7. grow 方法8. size 方法9. indexOf 方法10. Vector 類

Java集合彙總(全)

JDK源碼【集合架構】Java集合架構概述

【源碼】LinkedHashMap源碼剖析

疊代器的并發修改異常

java集合類源碼解析(1)---類關系簡介

Java集合類架構學習 4.2 —— HashMap(JDK1.7)

Java集合類架構學習 4.3 —— HashMap(JDK1.8)

Java集合類架構學習 4.1 —— HashMap(JDK1.6)

java--HashSet詳解