LinkedList

前言

本文作為我學習 Java 集合 LinkedList 的一個記錄與總結，如有疏漏或不足之處歡迎指出共同進步！

一、LinkedList 簡介

1.1 LinkedList 概述

LinkedList 是可以動态增長或縮減的索引序列，其底層是基于雙向連結清單實作的
LinkedList 類内部維護了一個雙向連結清單，是以可以完成高效的的插入和删除，但由于順序存取的原因其查詢效率不如 ArrayList ，後者可以通過 index 直接取得相應的值。
LinkedList 與 ArrayList 一樣是線程不安全的，并發場景可使用 CopyOnWriteArrayList
LinkedList 實作了 Deque 接口，是以其可以作為棧，隊列，雙端隊列來使用
繼承結構：

JAVA 集合之 LinkedListLinkedList

1.2 LinkedList 底層資料結構

LinkedList 的底層資料結構為雙向連結清單，其能存放任何元素 (包括 null)，如下圖所示雙向連結清單每個節點由

JAVA 集合之 LinkedListLinkedList

三個成員組成：

ele ：連結清單節點存儲的元素

prev ：目前節點的前一個節點

next：目前節點的下一個節點

此外還有 first 和 last 隻想連結清單的頭節點和尾節點，頭節點的 prev 指向 null，尾節點的 next 指向 null。

二、LinedList 源碼分析

2.1 繼承類與接口實作

JAVA 集合之 LinkedListLinkedList

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, Serializable

繼承類
- LinkedList extends AbstractSequentialList
- AbstractSequentialList extends AbstractList

從整個繼承結構中可以看到 LinkedList 相比于 ArrayList 其上面多了一層 AbstractSequentialList，而這個抽象類繼承自 AbstractList。從源碼中的注釋可以發現這個抽象類的作用：

JAVA 集合之 LinkedListLinkedList

這兩段話總結下來就是倆點：

這個抽象類實作了一些順序存取的 List 的通用方法以減少繼承類的代碼量
這個抽象類的實作與 AbstractList 相反，比如 add()，get() 等方法，因為其為順序存取結構，而 AbstractList 則是随機存取，如果想要實作順序存取應該繼承此抽象類，而随機存取應該繼承 AbstractList
實作接口
- List 接口：LinkedList 實作這個接口的原因應該與 ArrayList 一樣屬于一個小錯誤
- Deque 接口：擁有雙端隊列的各種特性，即 LinkedList 可以看作雙端隊列的一種實作
- Cloneable 接口：實作了這個接口就可以使用 clone() 方法
- Serializable 接口：實作了這個接口表明該類是可序列化的
- 注意與 ArrayList 不同 LinkedList 沒有實作 RandomAccess 這是因為 LinkedList 是順序存儲的結構，是以周遊 LinkedList 應該使用 iterator

2.2 成員屬性

// 版本号
private static final long serialVersionUID = 876323262645176354L;
// LinkedList 的 Size
transient int size = 0;
// 雙向連結清單的頭節點
transient Node<E> first;
// 雙向連結清單的尾節點
transient Node<E> last;

其中

Node<E>

為内部類，其結構就如 1.2 節中展示的資料結構。

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

2.3 構造方法

JAVA 集合之 LinkedListLinkedList

LinkedList()
```
public LinkedList() {
}
           
```
LinkedList 的空構造，初始化一個空的 LinkedList
LinkedList(Collection<? extends E> c)
```
public LinkedList(Collection<? extends E> c) {
    	// 調用空構造
        this();
    	// 将集合 c 中的元素全部初始化到 LinkedList 中
        addAll(c);
    }
           
```
在這個構造函數中調用了 addAll() 方法其具體内容在下文核心方法一節會具體闡述，其作用是将傳入的集合 c中的元素初始化為 LinkedList 的元素

2.4 核心方法

LinkedList 的核心方法有 add()、get()、set()、remove()、indexOf()

2.4.1 add() 方法

JAVA 集合之 LinkedListLinkedList

LinkedList 中共有 6 個 add 方法，其中最後倆個

addFirst()

和

addLast()

需要在初始化時指定類型為 LinkedList 或 Deque 才能使用，其為雙端隊列的方法，本文着重講述 List 相關内容，是以不詳細闡述這倆個方法。

add(E e)

public boolean add(E e) {
    	// 調用 linkLast 方法将元素連接配接在連結清單尾部
        linkLast(e);
        return true;
    }

add(E e)

方法在 LinkedList 最後添加一個元素其内部調用了 linkLast() 方法：

void linkLast(E e) {
    	// 将尾部指針 last 賦給臨時變量 l
        final Node<E> l = last;
    	// 建立一個新的 node 其 pre 指向 l，元素值為 e，next 指向 null
        final Node<E> newNode = new Node<>(l, e, null);
    	// 尾指針指向新節點
        last = newNode;
        if (l == null)
            // 若連結清單原來為空那麼将頭指針也指向此節點
            first = newNode;
        else
            // 如果不為空則将原來的尾部節點指向新節點
            l.next = newNode;
        size++;
    	// modCount 表示 LinkedList 中添加或删除的次數
        modCount++;
    }

從 linkLast 可以看到在調用

add()

方法後會建立一個新節點并連接配接到原來連結清單的最尾部，此過程隻需要建立一個新的 node 對象并修改若幹指針，相比于 ArrayList 的數組複制 LinkedList 在添加元素方面更加高效。

add(int index, E e)

public void add(int index, E element) {
    	// 判斷 index >= 0 && index <= size
        checkPositionIndex(index);
		// 如果 index == size 直接在連結清單尾部添加元素
        if (index == size)
            linkLast(element);
        else
            // 調用 linkBefore() 方法在指定 index 處插入元素
            linkBefore(element, node(index));
    }

add(int index, E e) 方法中核心的語句就是

linkBefore(element, node(index))

其中調用了

node()

方法來擷取 index 位置上的節點，然後調用

linkBefore()

來在此節點之前插入元素，接下來看一下源碼：

Node<E> node(int index) {
        // assert isElementIndex(index);
		// 判斷輸入的 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;
        }
    }

node()

的代碼很簡單先判斷 index 距離那一端更近，然後周遊找到 index 所對應的那個 node 節點，從這就可以看到底層為雙向連結清單的一個好處，可以一定程度上的減少周遊花銷的時間。

void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
    	// 取得 index 所指節點的前一個節點
        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++;
    }

linkBefore()

此方法就是執行了連結清單插入的一些基本操作，取得 index 節點的前一個節點，将前一個節點的 next 指向新節點，将新節點的 next 指向 index 節點。

addAll(Collection c)

public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

方法中調用了另一個

addAll(int index, Collection c)

方法，參照上面兩個

add()

方法的關系可以猜到此方法的作用就是在 LinkedList 按順序依次添加集合 c 中的所有元素，是以我們重點看下其調用的

addAll()

方法。

addAll(int index, Collection 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;
    	// 如果 index == size 直接在末尾添加
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            // 在中間插入，先取得 index 對應的 node 節點，即其前一個節點
            succ = node(index);
            pred = succ.prev;
        }
		// 周遊集合 c 中的元素并插入到連結清單中
        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;
        }

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

整體代碼比較簡單，其作用就是在 index 處插入集合 c 中的全部元素，基本都為連結清單的基本操作。

add()

方法總結：

從四個 add() 方法可以看到，LinkedList 由于底層使用雙向連結清單實作在在添加新元素時隻需要建立新節點并修改若幹指針即可，是以其修改效率很高。
因為 LinkedList 隻能順序存取，是以在需要周遊整個連結清單的場合會先判斷距離 first 和 last 那一端更近，以此來減少周遊的時間。

2.4.2 get() 方法

JAVA 集合之 LinkedListLinkedList

與

add()

方法相同，

get()

方法中

getFirst()

和

getLast()

都是實作的 Deque 接口的方法本文中不再詳細叙述。

get(int index)
```
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
           
```
這個方法很簡單其中調用的方法之前也詳細的講過，通過 node() 方法取得 index 對應的節點後傳回其元素值。

2.4.3 set() 方法

set(int index, E e)

public E set(int index, E element) {
    checkElementIndex(index);
    // 通過 node() 方法來的到 index 所對應的那個節點
    Node<E> x = node(index);
    E oldVal = x.item;
    // 設定節點中新的元素值
    x.item = element;
    return oldVal;
}

set()

方法核心依然是

node()

方法，其通過

node()

方法得到 index 所對應的節點，然後新的元素值指派給節點的 item 屬性。

2.4.4 remove() 方法

remove(Object o)

public boolean remove(Object o) {
    // 判斷傳入元素是否為 null
    if (o == null) {
        // 周遊連結清單尋找相等的元素
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                // remove() 方法的核心 unlink() 其作用為将一個指定的節點從連結清單中删除
                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;
}

方法的核心就在于

unlink()

方法，老樣子檢視一下其源碼看看到底做了什麼。

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 {
        // 将目前節點的前一個節點的 next 指向目前節點的後一個節點
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        // 将目前節點的後一個節點的 prev 指向目前節點的前一個節點
        next.prev = prev;
        x.next = null;
    }

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

unlink()

方法的核心就是獲得目前節點的前後節點然後通過修改前後節點的連結來将目前節點排除對外連結表，之後将目前節點的元素值置為 null 讓 gc 機制更快的回收節點，如果整個過程不明白可以在紙上畫一畫圖來幫助了解。

set(int index)
```
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}
           
```
前文分析了 node() 和 unlink() 方法，那麼這個通過 index 來删除指定的元素的方法就不難了解了。

2.4.5 indexOf() 方法

indexOf(Object o)

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

與

remove(Object o)

異曲同工，隻不過其是找到節點并将其删除，

indexOf()

是找到節點傳回其 index 的值，需要注意的是兩者都隻能處理找到的第一個滿足條件的節點。

三、LinkedList 疊代器

3.1 内部類 ListItr

JAVA 集合之 LinkedListLinkedList

上圖為内部類 ListItr 的詳細資訊，可以看到這個内部類實作了 ListIterator 接口，從這個接口的注釋中可以探查目的是為了那種能夠從兩邊變量的 List 類型而提供方法，此外還提供了在疊代過程中用于修改 List 結構的

add()

和

remove()

方法。

JAVA 集合之 LinkedListLinkedList

從其提供的方法可以看到 LinkedList 不僅可以向後疊代，也可以向前疊代方法如下：

public class ArrayTest {
    public static void main(String[] args) {
        LinkedList<Person> list = new LinkedList<Person>();
        list.add(new Person(35, "張三", "男"));
        list.add(new Person(30, "李四", "男"));
        list.add(new Person(29, "王五", "男"));
        list.add(new Person(29, "劉六", "男"));
        // 擷取一個類型為 ListIterator 的疊代器，并将初始遊标位置設定在 index = size() 處
        ListIterator<Person> iterator = list.listIterator(list.size());
        // 向前疊代 LinkedList
        while(iterator.hasPrevious()){
            System.out.println(iterator.previous());
        }

    }
}
class Person {
    int age;
    String name;
    String sex;

    public Person() {
    }

    public Person(int age, String name, String sex) {
        this.age = age;
        this.name = name;
        this.sex = sex;
    }

}

結果:

JAVA 集合之 LinkedListLinkedList

此外還能看到，疊代器内部提供了

remove()

和

add()

方法是以在疊代過程中可以對 LinkedList 進行結構性的改變，但不能調用 LinkedList 自己的方法，否則會導緻 ConcurrentModificationException 異常，詳細原因可以檢視我有關 ArrayList 的部落格。

3.2 内部類 DescendingIterator

LinkedList 還提供了另一個内部類 DescendingIterator，其作用就是在向前疊代 LinkedList 的過程中讓使用者可以依然使用

next()

而不用使用

previous()

。

private class DescendingIterator implements Iterator<E> {
    private final ListItr itr = new ListItr(size());
    // 将 hasPrevious 改為 hasNext
    public boolean hasNext() {
        return itr.hasPrevious();
    }
    // 将 previou 改為 next
    public E next() {
        return itr.previous();
    }
    public void remove() {
        itr.remove();
    }
}

接下來用一個小例子來驗證一下：

public static void main(String[] args) {
    LinkedList<Person> list = new LinkedList<Person>();
    list.add(new Person(35, "張三", "男"));
    list.add(new Person(30, "李四", "男"));
    list.add(new Person(29, "王五", "男"));
    list.add(new Person(29, "劉六", "男"));
    Iterator<Person> iterator = list.descendingIterator();
    while(iterator.hasNext()){
        System.out.println(iterator.next());
    }

}

結果：

JAVA 集合之 LinkedListLinkedList

可以看到雖然是用

next()

但是結果是反向周遊的。

四、總結

LinkedList 的本質是一個雙向連結清單，通過内部類 Node 來實作這種結構
LinkedList 能存儲任何值，包括 null
LinkedList 不僅實作了 List 接口還實作了 Deque 接口，是以具有雙端隊列的所有特征，是雙端隊列的一種實作，可以用作棧，隊列，雙端隊列來使用
LinkedList 不像 ArrayList 那樣有一個最大容量，其理論上可以無限擴充
LinkedList 與 ArrayList 相比在改變 List 結構的操作上性能更高，與之相對的是在查詢上性能較差。

JAVA 集合之 LinkedListLinkedList

LinkedList

前言

一、LinkedList 簡介

1.1 LinkedList 概述

1.2 LinkedList 底層資料結構

二、LinedList 源碼分析

2.1 繼承類與接口實作

2.2 成員屬性

2.3 構造方法

2.4 核心方法

2.4.1 add() 方法

2.4.2 get() 方法

2.4.3 set() 方法

2.4.4 remove() 方法

2.4.5 indexOf() 方法

三、LinkedList 疊代器

3.1 内部類 ListItr

3.2 内部類 DescendingIterator

四、總結

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method