注：本系列文章中用到的jdk版本均為java8

LinkedList類圖如下：

LinkedList底層是由雙向鏈表實現(xiàn)的。鏈表好比火車，每節(jié)車廂包含了車廂和連接下一節(jié)車廂的連接點。而雙向鏈表的每個節(jié)點不僅有指向下一個節(jié)點的指針，還有指向上一個節(jié)點的指針。

在LinkedList源碼中有一個Node靜態(tài)類，源碼如下：

 
 
 
 
  
  
  
  
private static class Node { 
  
  
  
  
    E item; 
  
  
  
  
    Node next; 
  
  
  
  
    Node prev; 
  
  
  
  
 
  
  
  
  
    Node(Node prev, E element, Node next) { 
  
  
  
  
        this.item = element; 
  
  
  
  
        this.next = next; 
  
  
  
  
        this.prev = prev; 
  
  
  
  
    } 
  
  
  
  
} 
 
 
 

一個Node節(jié)點包含三個部分，分別是

• item：數(shù)據(jù)
• next：下一個節(jié)點的指針
• prev：上一個節(jié)點的指針

LinkedList的主要變量如下：

 
 
 
 
  
  
  
  
// 集合中的元素數(shù)量 
  
  
  
  
transient int size = 0; 
  
  
  
  
 
  
  
  
  
/** 
  
  
  
  
  * 首節(jié)點的指針. 
  
  
  
  
  * Invariant: (first == null && last == null) || 
  
  
  
  
  *            (first.prev == null && first.item != null) 
  
  
  
  
  */ 
  
  
  
  
transient Node first; 
  
  
  
  
 
  
  
  
  
/** 
  
  
  
  
  * 尾結點的指針. 
  
  
  
  
  * Invariant: (first == null && last == null) || 
  
  
  
  
  *            (last.next == null && last.item != null) 
  
  
  
  
  */ 
  
  
  
  
transient Node last; 
 
 
 

一、添加元素

LinkedList支持在任意節(jié)點位置添加元素，不僅提供了集合常用的add()方法，還提供了addFirst()和addLast()，add()方法默認調用addLast()方法，也就是默認是往鏈表尾部插入元素的。

add()方法源碼：

 
 
 
 
  
  
  
  
public boolean add(E e) { 
  
  
  
  
    linkLast(e); 
  
  
  
  
    return true; 
  
  
  
  
} 
 
 
 

1.1 尾部插入元素

linkLast()源碼如下：

 
 
 
 
  
  
  
  
void linkLast(E e) { 
  
  
  
  
    final Node l = last; 
  
  
  
  
    final Node newNode = new Node<>(l, e, null); 
  
  
  
  
    last = newNode; 
  
  
  
  
    if (l == null) 
  
  
  
  
        first = newNode; 
  
  
  
  
    else 
  
  
  
  
        l.next = newNode; 
  
  
  
  
    size++; 
  
  
  
  
    modCount++; 
  
  
  
  
} 
 
 
 

我們來畫張圖演示一下如何給鏈表尾部插入元素：

假如鏈表中沒有元素

對應源碼中的if語句，如果沒有元素則新增的這個節(jié)點為鏈表中唯一的一個元素，既是首節(jié)點，又是尾結點，前一個元素的指針和后一個元素的指針都是null。這里注意head節(jié)點不是第一個節(jié)點，head節(jié)點只是標識了這個鏈表的地址。

假如鏈表中有元素

對應源碼中else語句。先將新增的元素當成Last節(jié)點，然后將原來的Last節(jié)點的next指向新節(jié)點。

 
 
 
 
  
  
  
  
else 
  
  
  
  
    l.next = newNode; 
 
 
 

一圖勝前言，畫個圖是不是什么都明白了。

1.2 頭部插入元素

linkFirst()源碼如下：

 
 
 
 
  
  
  
  
private void linkFirst(E e) { 
  
  
  
  
    final Node f = first; 
  
  
  
  
    final Node newNode = new Node<>(null, e, f); 
  
  
  
  
    first = newNode; 
  
  
  
  
    if (f == null) 
  
  
  
  
        last = newNode; 
  
  
  
  
    else 
  
  
  
  
        f.prev = newNode; 
  
  
  
  
    size++; 
  
  
  
  
    modCount++; 
  
  
  
  
} 
 
 
 

還是根據(jù)上面的圖來解讀一下源碼，先將第一個節(jié)點賦值給中間變量f，將新節(jié)點newNode賦值給first節(jié)點。如果鏈表沒有元素，則Last節(jié)點和First節(jié)點都是新插入的節(jié)點newNode，否則，將原來的First節(jié)點的頭指針指向新節(jié)點。

二、刪除元素

LinkedList提供的刪除方法有根據(jù)索引和元素刪除，除此之外還提供刪除第一個元素和最后一個元素的方法，這里我們只分析一下根據(jù)索引刪除的方法。

 
 
 
 
  
  
  
  
public E remove(int index) { 
  
  
  
  
    checkElementIndex(index); 
  
  
  
  
    return unlink(node(index)); 
  
  
  
  
} 
 
 
 

checkElementIndex(index)方法就是用來判斷傳輸?shù)乃饕凳欠窈戏?，不合法則拋出數(shù)組越界異常。重點來看一下unlink(node(index))方法是如何刪除元素的。

node(index)方法源碼：

node(index)方法就是根據(jù)索引獲取該索引位置的節(jié)點

 
 
 
 
  
  
  
  
Node node(int index) { 
  
  
  
  
    // assert isElementIndex(index); 
  
  
  
  
    // 如果指定下標 < 一半元素數(shù)量，則從首結點開始遍歷 
  
  
  
  
    // 否則，從尾結點開始遍歷 
  
  
  
  
    if (index < (size >> 1)) { 
  
  
  
  
        Node x = first; 
  
  
  
  
        for (int i = 0; i < index; i++) 
  
  
  
  
            x = x.next; 
  
  
  
  
        return x; 
  
  
  
  
    } else { 
  
  
  
  
        Node x = last; 
  
  
  
  
        for (int i = size - 1; i > index; i--) 
  
  
  
  
            x = x.prev; 
  
  
  
  
        return x; 
  
  
  
  
    } 
  
  
  
  
} 
 
 
 

unlink(Node x)源碼如下：

 
 
 
 
  
  
  
  
E unlink(Node x) { 
  
  
  
  
    // assert x != null; 
  
  
  
  
    final E element = x.item; 
  
  
  
  
    final Node next = x.next; 
  
  
  
  
    final Node 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; 
  
  
  
  
} 
 
 
 

畫張圖分析一下刪除是如何進行的：

1. 假設刪除的是第一個元素：則它的prev==NULL，我們需要將他的后一個元素(圖中的second)作為第一個元素
2. 假設刪除的是最后一個元素，則它的next==null，我們需要將他的前一個元素(圖中的second)作為最后一個元素
3. 如果是中間的任意元素，則需要將它的前一個元素的next指針指向它的后一個元素，同時將它的后一個元素的prev指針指向它的前一個元素。

三、總結

LinkedList底層是由雙向鏈表實現(xiàn)的，由于是鏈表實現(xiàn)的，不僅要存放數(shù)據(jù)，還要存放指針，所以內存開銷要比ArrayList大，刪除元素不需要移動其他元素，只需要改變指針的指向，因此刪除效率更高，同時它沒有實現(xiàn)RandomAccess接口，因此使用迭代器遍歷要比for循環(huán)更加高效。LinkedList也支持插入重復值和空值，同樣也是線程不安全的。

本文轉載自微信公眾號「 Java旅途」，可以通過以下二維碼關注。轉載本文請聯(lián)系 Java旅途公眾號。

文章題目：從面試角度分析LinkedList源碼
網(wǎng)站鏈接：http://uogjgqi.cn/article/cccgcge.html