LinkedList類【JDK源碼分析】

LinkedList類類【JDK源碼分析】

• ​​前言​​
• ​​推薦​​
• ​​說明​​
• ​​LinkedList類​​

• ​​基本資訊​​

• ​​字段摘要​​
• ​​構造方法摘要​​

• ​​字段​​
• ​​構造方法詳細資訊​​
• ​​内部類​​

• ​​add​​
• ​​remove​​

• ​​總結​​
• ​​最後​​

前言

2022/11/2

路漫漫其修遠兮,吾将上下而求索

本文是根據jdk學習所做筆記

僅供學習交流使用，轉載注明出處

推薦

JDK API 1.6 中文版

說明

以下内容是結合很多資料進行編寫的

源碼為jdk1.8的

斜體樣式 為自己的思考

下劃線為自己所畫的重點

LinkedList類

基本資訊

java.util

類 LinkedList< E>

java.lang.Object

繼承者 java.util.AbstractCollection< E>

繼承者 java.util.AbstractList< E>

繼承者 java.util.AbstractSequentialList< E>

繼承者 java.util.LinkedList

類型參數：

E - 在此 collection 中保持的元素的類型

所有已實作的接口：

Serializable, Cloneable, Iterable< E>, Collection< E>, Deque< E>, List< E>, Queue< E>

public class LinkedList

extends AbstractSequentialList

implements List, Deque, Cloneable, Serializable

List 接口的連結清單實作。實作所有可選的清單操作，并且允許所有元素（包括 null）。除了實作 List 接口外，LinkedList 類還為在清單的開頭及結尾 get、remove 和 insert 元素提供了統一的命名方法。這些操作允許将連結清單用作堆棧、隊列或雙端隊列。

此類實作 Deque 接口，為 add、poll 提供先進先出隊列操作，以及其他堆棧和雙端隊列操作。

所有操作都是按照雙重連結清單的需要執行的。在清單中編索引的操作将從開頭或結尾周遊清單（從靠近指定索引的一端）。

注意，此實作不是同步的。如果多個線程同時通路一個連結清單，而其中至少一個線程從結構上修改了該清單，則它必須 保持外部同步。（結構修改指添加或删除一個或多個元素的任何操作；僅設定元素的值不是結構修改。）這一般通過對自然封裝該清單的對象進行同步操作來完成。如果不存在這樣的對象，則應該使用 Collections.synchronizedList 方法來“包裝”該清單。最好在建立時完成這一操作，以防止對清單進行意外的不同步通路，如下所示：

List list = Collections.synchronizedList(new LinkedList(...));      

此類的 iterator 和 listIterator 方法傳回的疊代器是快速失敗 的：在疊代器建立之後，如果從結構上對清單進行修改，除非通過疊代器自身的 remove 或 add 方法，其他任何時間任何方式的修改，疊代器都将抛出 ConcurrentModificationException。是以，面對并發的修改，疊代器很快就會完全失敗，而不冒将來不确定的時間任意發生不确定行為的風險。

注意，疊代器的快速失敗行為不能得到保證，一般來說，存在不同步的并發修改時，不可能作出任何硬性保證。快速失敗疊代器盡最大努力抛出 ConcurrentModificationException。是以，編寫依賴于此異常的程式的方式是錯誤的，正确做法是：疊代器的快速失敗行為應該僅用于檢測程式錯誤。

此類是 Java Collections Framework 的成員。

從以下版本開始：

1.2

另請參見：

List, ArrayList, Vector, 序列化表格

字段摘要

從類 java.util.AbstractList 繼承的字段

modCount

構造方法摘要

LinkedList()

構造一個空清單。

LinkedList(Collection<? extends E> c)

構造一個包含指定 collection 中的元素的清單，這些元素按其 collection 的疊代器傳回的順序排列。

￥## 方法摘要

boolean add(E e)

将指定元素添加到此清單的結尾。

void add(int index, E element)

在此清單中指定的位置插入指定的元素。

boolean addAll(Collection<? extends E> c)

添加指定 collection 中的所有元素到此清單的結尾，順序是指定 collection 的疊代器傳回這些元素的順序。

boolean addAll(int index, Collection<? extends E> c)

将指定 collection 中的所有元素從指定位置開始插入此清單。

void addFirst(E e)

将指定元素插入此清單的開頭。

void addLast(E e)

将指定元素添加到此清單的結尾。

void clear()

從此清單中移除所有元素。

Object clone()

傳回此 LinkedList 的淺表副本。

boolean contains(Object o)

如果此清單包含指定元素，則傳回 true。

Iterator descendingIterator()

傳回以逆向順序在此雙端隊列的元素上進行疊代的疊代器。

E element()

擷取但不移除此清單的頭（第一個元素）。

E get(int index)

傳回此清單中指定位置處的元素。

E getFirst()

傳回此清單的第一個元素。

E getLast()

傳回此清單的最後一個元素。

int indexOf(Object o)

傳回此清單中首次出現的指定元素的索引，如果此清單中不包含該元素，則傳回 -1。

int lastIndexOf(Object o)

傳回此清單中最後出現的指定元素的索引，如果此清單中不包含該元素，則傳回 -1。

ListIterator listIterator(int index)

傳回此清單中的元素的清單疊代器（按适當順序），從清單中指定位置開始。

boolean offer(E e)

将指定元素添加到此清單的末尾（最後一個元素）。

boolean offerFirst(E e)

在此清單的開頭插入指定的元素。

boolean offerLast(E e)

在此清單末尾插入指定的元素。

E peek()

擷取但不移除此清單的頭（第一個元素）。

E peekFirst()

擷取但不移除此清單的第一個元素；如果此清單為空，則傳回 null。

E peekLast()

擷取但不移除此清單的最後一個元素；如果此清單為空，則傳回 null。

E poll()

擷取并移除此清單的頭（第一個元素）

E pollFirst()

擷取并移除此清單的第一個元素；如果此清單為空，則傳回 null。

E pollLast()

擷取并移除此清單的最後一個元素；如果此清單為空，則傳回 null。

E pop()

從此清單所表示的堆棧處彈出一個元素。

void push(E e)

将元素推入此清單所表示的堆棧。

E remove()

擷取并移除此清單的頭（第一個元素）。

E remove(int index)

移除此清單中指定位置處的元素。

boolean remove(Object o)

從此清單中移除首次出現的指定元素（如果存在）。

E removeFirst()

移除并傳回此清單的第一個元素。

boolean removeFirstOccurrence(Object o)

從此清單中移除第一次出現的指定元素（從頭部到尾部周遊清單時）。

E removeLast()

移除并傳回此清單的最後一個元素。

boolean removeLastOccurrence(Object o)

從此清單中移除最後一次出現的指定元素（從頭部到尾部周遊清單時）。

E set(int index, E element)

将此清單中指定位置的元素替換為指定的元素。

int size()

傳回此清單的元素數。

Object[] toArray()

傳回以适當順序（從第一個元素到最後一個元素）包含此清單中所有元素的數組。

T[]

toArray(T[] a)

傳回以适當順序（從第一個元素到最後一個元素）包含此清單中所有元素的數組；傳回數組的運作時類型為指定數組的類型。

從類 java.util.AbstractSequentialList 繼承的方法

iterator

從類 java.util.AbstractList 繼承的方法

equals, hashCode, listIterator, removeRange, subList

從類 java.util.AbstractCollection 繼承的方法

containsAll, isEmpty, removeAll, retainAll, toString

從類 java.lang.Object 繼承的方法

finalize, getClass, notify, notifyAll, wait, wait, wait

從接口 java.util.List 繼承的方法

containsAll, equals, hashCode, isEmpty, iterator, listIterator, removeAll, retainAll, subList

從接口 java.util.Deque 繼承的方法

iterator

字段

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

public LinkedList()

構造一個空清單。

LinkedList

public LinkedList(Collection<? extends E> c)

構造一個包含指定 collection 中的元素的清單，這些元素按其 collection 的疊代器傳回的順序排列。

參數：

c - 要将其元素放入此清單的 collection

抛出：

NullPointerException - 如果指定的 collection 為 null

内部類

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

/**
     * Returns a list-iterator of the elements in this list (in proper
     * sequence), starting at the specified position in the list.
     * Obeys the general contract of {@code List.listIterator(int)}.<p>
     *
     * The list-iterator is <i>fail-fast</i>: if the list is structurally
     * modified at any time after the Iterator is created, in any way except
     * through the list-iterator's own {@code remove} or {@code add}
     * methods, the list-iterator will throw a
     * {@code ConcurrentModificationException}.  Thus, in the face of
     * concurrent modification, the iterator fails quickly and cleanly, rather
     * than risking arbitrary, non-deterministic behavior at an undetermined
     * time in the future.
     *
     * @param index index of the first element to be returned from the
     *              list-iterator (by a call to {@code next})
     * @return a ListIterator of the elements in this list (in proper
     *         sequence), starting at the specified position in the list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     * @see List#listIterator(int)
     */
    public ListIterator<E> listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);//也是快速失敗 
    }      

final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }      

add

public boolean add(E e)

将指定元素添加到此清單的結尾。

此方法等效于 addLast(E)。

指定者：

接口 Collection 中的 add

指定者：

接口 Deque 中的 add

指定者：

接口 List 中的 add

指定者：

接口 Queue 中的 add

覆寫：

類 AbstractList 中的 add

參數：

e - 要添加到此清單的元素

傳回：

true（根據 Collection.add(E) 的規定）

/**
     * Appends the specified element to the end of this list.
     *
     * <p>This method is equivalent to {@link #addLast}.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }      

/**
     * Links e as last element.
     */
    void linkLast(E e) {
        final Node<E> l = last;//l，最後結點  lp,l,null (prev, element, next)
        final Node<E> newNode = new Node<>(l, e, null);//新結點 把值e的newNode的prev指向l 
        last = newNode;//最後指針指向新加入的最後結點
        if (l == null)
            first = newNode;//為空是同一個 l=last=null
        else
            l.next = newNode;//l的next指向newNode
        size++;//數量加
        modCount++;//結構變化次數加
    }      

remove

public boolean remove(Object o)從此清單中移除首次出現的指定元素（如果存在）。如果清單不包含該元素，則不作更改。更确切地講，移除具有滿足 (o==null ? get(i)==null : o.equals(get(i))) 的最低索引 i 的元素（如果存在這樣的元素）。如果此清單已包含指定元素（或者此清單由于調用而發生更改），則傳回 true。

指定者：

接口 Collection 中的 remove

指定者：

接口 Deque 中的 remove

指定者：

接口 List 中的 remove

覆寫：

類 AbstractCollection 中的 remove

參數：

o - 要從此清單删除的元素，如果存在

傳回：

如果此清單包含指定元素，則傳回 true

/**
     * Removes the first occurrence of the specified element from this list,
     * if it is present.  If this list does not contain the element, it is
     * unchanged.  More formally, removes the element with the lowest index
     * {@code i} such that
     * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
     * (if such an element exists).  Returns {@code true} if this list
     * contained the specified element (or equivalently, if this list
     * changed as a result of the call).
     *
     * @param o element to be removed from this list, if present
     * @return {@code true} if this list contained the specified element
     */
    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;
    }      

/**
     * Unlinks non-null node x.
     */
    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;
    }      

總結

• public LinkedList()

• 構造一個空清單。

• add
• remove
• listIterator

• 快速失敗

最後