本文介紹

1医增、LinkedList相關(guān)面試題。
2老虫、LinkedList基本信息调窍。
3、LinkedList屬性和方法张遭。
4邓萨、LinkedList最佳實(shí)踐。
5菊卷、LinkedList的總結(jié)缔恳。

概述

LinkedList 是一種變長的集合類洁闰。底層數(shù)據(jù)結(jié)構(gòu)是雙向鏈表歉甚，是非連續(xù)的內(nèi)存空間。
LinkedList 允許空值和重復(fù)元素扑眉，因?yàn)閍dd方法不做空值和重復(fù)元素校驗(yàn)纸泄。
LinkedList 是非線程安全類赖钞，并發(fā)環(huán)境下，多個線程同時操作 LinkedList聘裁，會引發(fā)不可預(yù)知的錯誤雪营。

LinkedList類關(guān)系圖

LinkedList 繼承AbstractSequentialList，實(shí)現(xiàn)了List, Deque, Cloneable, java.io.Serializable接口衡便。
LinkedList 實(shí)現(xiàn)List接口献起，即提供相關(guān)的添加、刪除镣陕、修改谴餐、遍歷功能。
LinkedList 實(shí)現(xiàn)Cloneable接口呆抑，即覆蓋了函數(shù)clone()岂嗓，能被克隆。
LinkedList 實(shí)現(xiàn)Serializable接口鹊碍，這意味著LinkedList 支持序列化摄闸。

下面讓我們翻開LinkedList 的源代碼，看看一些常用的方法屬性妹萨，以及一些需要注意的地方。

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

LinkedList最最最核心的就是節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)炫欺。組成鏈表的節(jié)點(diǎn)由 prev：指向上一個節(jié)點(diǎn)的引用乎完、next：指向下一個節(jié)點(diǎn)的引用、item：存儲的元素組成品洛。

// 靜態(tài)內(nèi)部類形式的Node
private static class Node<E> {
    E item; // 元素
    Node<E> next; // 指向下個節(jié)點(diǎn)的引用
    Node<E> prev; // 指向上個節(jié)點(diǎn)的引用

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

下圖是由Node節(jié)點(diǎn)組成雙向鏈表树姨，LindedList底層的數(shù)據(jù)存儲基本上就是醬紫了。

屬性

LinkedList 屬性主要有當(dāng)前鏈表長度size桥状，first 指向第一個節(jié)點(diǎn) 這里我稱為首節(jié)點(diǎn)帽揪，last 指向最后一個節(jié)點(diǎn)簡稱尾節(jié)點(diǎn) 。除此之外還有一個經(jīng)常用到的屬性就是從 AbstractList 繼承過來的 modCount 屬性辅斟，代表 LinkedList 集合的修改次數(shù)转晰。

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;

加入first屬性和last屬性后的雙向鏈表

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

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

如果不傳入?yún)?shù)，則使用默認(rèn)無參構(gòu)建方法創(chuàng)建LinkedList對象士飒，如下：

public LinkedList() {
}

帶collection類型的構(gòu)造函數(shù)

// 創(chuàng)建LinkedList
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

// 添加 collection 中所有元素
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

// 在index位置添加 collection 所有元素
public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index); // 范圍插入范圍查邢，[0 , size]位置為正常

    Object[] a = c.toArray(); // 將集合轉(zhuǎn)成Object數(shù)組
    int numNew = a.length;
    if (numNew == 0) // 如果新增元素數(shù)量為0，直接返回false
        return false;

    Node<E> pred, succ; // pred與succ是兩個臨時變量酵幕，為將c中的元素構(gòu)建成Node再將其連接到鏈表上的臨時變量扰藕，（具體理解該的方法：先要理解鏈表是什么,也就是先搞清楚不懂的概念。再Debug進(jìn)來具體的代碼）
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }

    // 此處for循環(huán)主要把a(bǔ)中的元素鏈接到已有的元素上
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null); // 創(chuàng)建一個新節(jié)點(diǎn)芳撒，新節(jié)點(diǎn)的prev 指向 pred邓深，item 為e未桥，next 為null
        if (pred == null)
            first = newNode; // 設(shè)置首節(jié)點(diǎn)
        else
            pred.next = newNode;   // pred.next 指向新的節(jié)點(diǎn)
        pred = newNode; // pred 指向新的節(jié)點(diǎn)
    }

    if (succ == null) {
        last = pred; // 設(shè)置尾節(jié)點(diǎn)
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew; // 添加元素后數(shù)據(jù)大小
    modCount++; 
    return true;
}

/**
 * 將集合轉(zhuǎn)成Object數(shù)組
 *  1、創(chuàng)建一個size長度的數(shù)組 
 *  2芥备、循環(huán)將鏈表節(jié)點(diǎn)的元素賦值給新數(shù)組中并返回冬耿。
 */
public Object[] toArray() {
    Object[] result = new Object[size];
    int i = 0;
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;
    return result;
}

add方法

add(E e) 方法

添加單個元素方法

public boolean add(E e) {
    linkLast(e); // 在尾部添加元素 
    return true;
}

/**
 * 添加元素到鏈表最后
 * 1、生成新節(jié)點(diǎn)
 * 2门躯、插入到鏈表尾部
 * 3淆党、更新 last/first 節(jié)點(diǎn)。
 */
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);  // 創(chuàng)建pre指向l讶凉，item賦值為e染乌，next賦值為null
    last = newNode; // 設(shè)置last引用
    if (l == null)
        first = newNode; // 空鏈表情況設(shè)置first
    else
        l.next = newNode; // 設(shè)置尾節(jié)點(diǎn)指向新節(jié)點(diǎn)
    size++;
    modCount++;
}

add(int index, E element) 方法

添加元素到指定位置方法

public void add(int index, E element) {
    checkPositionIndex(index); // 檢查插入點(diǎn)的范圍 [0,size]
    if (index == size)
        linkLast(element); // 添加到鏈表最后
    else
        linkBefore(element, node(index));
}

/**
 * Returns the (non-null) Node at the specified element index.
 * 返回指定元素索引處的(非空)節(jié)點(diǎn)。下標(biāo)從0開始
 */
Node<E> node(int index) {
    if (index < (size >> 1)) { // index是否小于size的一半懂讯，小于則從首節(jié)點(diǎn)往后移
        Node<E> x = first;
        for (int i = 0; i < index; i++) // 從首節(jié)點(diǎn)開始荷憋，循環(huán)往后移動，直到 i=index
            x = x.next;
        return x; // 返回下標(biāo)為index處的節(jié)點(diǎn)（下標(biāo)從0開始）
    } else { // 反之大于從尾節(jié)點(diǎn)往前移
        Node<E> x = last;
        for (int i = size - 1; i > index; i--) // 從尾節(jié)點(diǎn)開始褐望，循環(huán)往前移動勒庄，直到 i=index
            x = x.prev; 
        return x;  // 返回下標(biāo)為index處的節(jié)點(diǎn)（下標(biāo)從0開始）
    }
}

/**
 * 將 e元素連接到 succ節(jié)點(diǎn)之前
 */
void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;  // pred指向succ的上一個節(jié)點(diǎn)
    final Node<E> newNode = new Node<>(pred, e, succ); // 創(chuàng)建新的節(jié)點(diǎn)，新節(jié)點(diǎn)的prev指向pred瘫里，新節(jié)點(diǎn)的item為e实蔽，新節(jié)點(diǎn)的nextr指向succ.
    succ.prev = newNode; // succ節(jié)點(diǎn)的prev指向新節(jié)點(diǎn)
    if (pred == null) // 如果pred是null，說明succ.prev是第一個節(jié)點(diǎn)谨读，則新的節(jié)點(diǎn)設(shè)置為首節(jié)點(diǎn)
        first = newNode; 
    else  // 修改pred指向的下一個節(jié)點(diǎn)為新節(jié)點(diǎn)
        pred.next = newNode;
    size++;
    modCount++;
}

get方法

get(int index)

獲取指定位置節(jié)點(diǎn)元素方法

public E get(int index) {
    checkElementIndex(index); // 檢查索引元素范圍局装，[0 , size）位置為正常。注意：不包括size
    return node(index).item; // 返回節(jié)點(diǎn)中具體的值
}

/** 檢查元素的索引位置 */
private void checkElementIndex(int index) {
    if (!isElementIndex(index))  // 是否是元素的索引劳殖，如果不是則拋出異常
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/** 是否是元素的索引铐尚，[0,size)  包括0不包括size*/
private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

getFirst()

獲取第一個節(jié)點(diǎn)元素方法

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

remove方法

remove(int index)

移除指定位置元素方法

public E remove(int index) {
    checkElementIndex(index);  // 檢查元素索引位置，如不是則拋出異常
    return unlink(node(index)); // 找到index位置節(jié)點(diǎn)哆姻，并移除
}

/** 移除節(jié)點(diǎn) */
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) { // x是否為首節(jié)點(diǎn)宣增，如果是則修改首節(jié)點(diǎn)指向
        first = next;
    } else { // 不是首節(jié)點(diǎn)
        prev.next = next;  // 修改x前一個節(jié)點(diǎn)的next指向x后一個節(jié)點(diǎn)
        x.prev = null; // 修改x節(jié)點(diǎn)的prev指向null
    }

    if (next == null) { // x是否為尾節(jié)點(diǎn)，如果是則修改尾節(jié)點(diǎn)指向
        last = prev;
    } else { // 不是尾節(jié)點(diǎn)
        next.prev = prev; // 修改x后一個節(jié)點(diǎn)的prev指向x前一個節(jié)點(diǎn)矛缨。
        x.next = null; // 修改x節(jié)點(diǎn)的next指向null
    }

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

remove(Object o)

根據(jù)對象移除元素方法

public boolean remove(Object o) {
    if (o == null) { // o是否為空爹脾，為空。循環(huán)遍歷鏈表箕昭，找到一個就移除誉简，并返回，假如有兩個null只會移除第一個盟广。
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x); 
                return true;
            }
        }
    } else { // 不為空闷串，循環(huán)遍歷鏈表，找到一個就移除筋量，并返回烹吵，假如有兩個o對象只會移除第一個碉熄。
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

removeFirst()

移除第一個節(jié)點(diǎn)方法

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

/** 將第一個元素移除，將移除元素置空肋拔，first指向下一個節(jié)點(diǎn)锈津，size減1，修改次數(shù)加1凉蜂，返回舊值 */
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
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

removeLast()

移除最后一個節(jié)點(diǎn)方法

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

/** 將最后一個元素移除琼梆，last指向上一個節(jié)點(diǎn)，將移除元素置空窿吩，size減1茎杂，修改次數(shù)加1，返回舊值 */
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;
}

set方法

set(int index, E element)

設(shè)置指定位置元素方法

public E set(int index, E element) {
    checkElementIndex(index);  // 檢查元素索引位置纫雁，如不是則拋出異常
    Node<E> x = node(index); // 獲取index位置的節(jié)點(diǎn)
    E oldVal = x.item; // 保存舊值
    x.item = element; // 設(shè)置item為新值
    return oldVal; // 返回舊值
}

clear方法

clear()

清除鏈表方法

/** 將所有鏈表元素置空煌往，然后將鏈表長度修改成0，修改次數(shù)加1 */
public void clear() {
    // Clearing all of the links between nodes is "unnecessary", but:
    // - helps a generational GC if the discarded nodes inhabit
    //   more than one generation
    // - is sure to free memory even if there is a reachable Iterator
    for (Node<E> x = first; x != null; ) { // 從首節(jié)點(diǎn)開始轧邪，循環(huán)遍歷鏈表刽脖，將節(jié)點(diǎn)只有item、next忌愚、prev設(shè)置為null
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null; // 首尾節(jié)點(diǎn)設(shè)置為null
    size = 0; // 設(shè)置大小為0
    modCount++; 
}

push和pop方法

最后說下兩個棧操作的方法曲管，這也是鏈表的另一種用法，把LinkedList當(dāng)做棧來使用硕糊。push其實(shí)就是調(diào)用addFirst(e)方法院水，pop調(diào)用的就是removeFirst()方法。

/** 出棧 */
public E pop() {
    return removeFirst();
}

/** 入棧 */
public void push(E e) {
    addFirst(e);
}

總結(jié)

LinkedList基于雙向鏈表實(shí)現(xiàn)癌幕，無容量的限制。
LinkedList下標(biāo)從0開始昧穿，最大下標(biāo)為size-1勺远。
LinkedList當(dāng)作棧使用，可以調(diào)用push和pop方法时鸵。
LinkedList移除對象時胶逢，如果有多個相同對象只會移除第一個。
LinkedList根據(jù)下標(biāo)和對象獲取元素的值時都會循環(huán)遍歷鏈表饰潜，時間復(fù)雜度為都為O(n)初坠，而ArrayList根據(jù)下標(biāo)獲取時直接可取到值，時間復(fù)雜度為O(1)彭雾，而根據(jù)對象查詢是需要遍歷數(shù)據(jù)碟刺，時間復(fù)雜度為O(n)。

最佳實(shí)踐

1薯酝、適合用于增加刪除多半沽，查詢修改少的業(yè)務(wù)中爽柒，與ArrayList對比剛好互補(bǔ)。但是目前對于這個容器的使用還是極少者填，以至于找不到一個好點(diǎn)的例子（后續(xù)補(bǔ)上）浩村。

引文

面試必備：LinkedList源碼解析（JDK8）
https://blog.csdn.net/zxt0601/article/details/77341098
LinkedList源碼分析（基于JDK8）
https://blog.csdn.net/fighterandknight/article/details/61476335