大家好，我是程式員xiao熊，本篇内容将為大家Java集合中LinkedList的源碼解析，本篇是源碼解讀系列的第二篇，關于LinkedList的其他内容可閱讀《輕松解讀源碼系列之Java集合LinkedList（上）》，《輕松解讀源碼系列之Java集合LinkedList（中）》；後續還會有其他的源碼解讀分享，如果大家有想要了解的内容，可以寫在評論中，或者私信告訴我；廢話不多說，開始進入正題吧，由于篇幅問題，本篇内容如下：

LinkedList疊代器
設定指定索引的值
擷取指定對象的索引
子連結清單
将連結清單轉為Object數組
将連結清單轉為指定類型的數組
總結

1、疊代器

LinkedList的疊代器與ArrayList類似，也有兩種：單向移動的Iterator和雙向移動的ListIterator，分别通過iterator()和listIterator()/listIterator(index)方法擷取。其中iterator()方法是父類AbstractSequentialList的方法，最終調用的是listiterator()方法，不過傳回的類型是Iterator，隻能正向周遊元素；listerator()是父類AbstractList（不是直接父類）的方法，但是其最終還是調用了listIterator(idnex)方法，本質上還是LinkedList中的Listerator；

ListIterator具體的實作類是LinkedList的内部類ListItr；與ArrayList的ListIterator類似，該ListIterator能夠正向周遊，也能反向周遊；具體代碼如下：

1.1、底層資料結構

ListItr的底層結構代碼如下，在底層的資料結構中有一個屬性：lastReturned；這是記錄上一次通路的元素節點，目的是為Iterator的set和remove方法服務的；因為set和remove方法隻能操作上一次通路過的元素，不能操作其他的元素；

// 上一次通路的節點
private Node<E> lastReturned; 
// 需要即将通路的節點（方向是向後周遊）
private Node<E> next; 
 // 即将通路的節點的索引
private int nextIndex;
// 修改連結清單結構的次數，可了解為外部類LinkedList的modCount的一個快照
private int expectedModCount = modCount;

1.2、構造函數

ListItr(int index) {
        // assert isPositionIndex(index);
// 如果索引等于元素數量，則通路的元素為null，因為下标從0開始，若index==size，則通路不到任何元素；否則即将通路的元素等于該索引位置的元素
        next = (index == size) ? null : node(index);
        nextIndex = index;
  }

1.3、正向周遊元素

在平常使用中，通過hasNext()和next()的配合使用來正常周遊連結清單中的元素，hasNext()用于判斷即将通路的索引是否有元素，next()用于通路元素，我們将對其中通路元素的方法next()進行講解，其業務邏輯過程如下：

1. 并發修改校驗，避免其他線程同時修改連結清單(添加或者删除元素)

2. 通路元素時再次校驗目前即将通路的索引是否有元素，沒有則抛出異常，避免在并發校驗之後又有線程操作連結清單

3. 将即将通路的節點作為上一次通路的節點(相對下一次通路)

4. 下一次即将需要通路的節點後移

5. 下一次即将通路的節點的索引後移

6. 傳回目前元素的值

// 判斷是否有可以通路的元素節點
public boolean hasNext() {
        //即将通路的索引是否小于元素數量，小于則表示存在元素，可以通路；否則表示沒有元素，不能通路
return nextIndex < size;
}
==================================
  // 正式通路元素節點
public E next() {
       // 1. 并發修改校驗，避免其他線程同時修改連結清單(添加或者删除元素)
        checkForComodification();
      // 2. 通路元素時再次校驗目前即将通路的索引是否有元素，沒有則抛出異常，避免在并發校驗之後又有線程操作連結清單
        if (!hasNext())
            throw new NoSuchElementException();

        // 3. 将即将通路的節點作為上一次通路的節點(相對下一次通路)
        lastReturned = next;
        // 4.- 下一次即将需要通路的節點後移
        next = next.next;
				// 5. 下一次即将通路的節點的索引後移
        nextIndex++;
				// 6. 傳回目前元素的值
        return lastReturned.item;
    }

1.4、反向周遊元素

在平常使用中，通過hasPervious()和previous()的配合使用來反向周遊連結清單中的元素，hasPrevious()用于判斷即将通路的索引位置是否有前驅元素節點，previous()用于通路即将通路的元素的前驅元素節點，反向周遊的是前驅節點，這是與next()通路指定索引位置的節點不一樣的地方；我們将對其中通路元素的方法previous()進行講解，其業務邏輯過程如下：

1. 并發修改校驗，避免其他線程同時修改連結清單(添加或者删除元素)

2. 如果目前節點(正向通路的節點)沒有前驅節點，則抛出異常，避免在并發校驗之後，又有其他線程修改了連結清單（添加、删除元素）

3. 如果即将通路（針對正向周遊的方向）的元素為null，則取尾結點作為即将通路的元素，也作為上一次通路的元素（針對下一輪的通路）；否則取前驅節點作為即将通路的節點

4. 下一次需要通路的元素索引是以減1

5. 傳回本次通路的元素值

// 判斷是否有可以通路的元素節點
public boolean hasPrevious() {
    return nextIndex > 0;
}
==========================
 // 通路前一個元素節點
public E previous() {
    //1. 并發修改校驗，避免其他線程同時修改連結清單(添加或者删除元素)
    checkForComodification();
    // 2.如果目前節點沒有前驅節點，則抛出異常，避免在并發校驗之後，又有其他線程修改了連結清單（添加、删除元素）
    if (!hasPrevious())
        throw new NoSuchElementException();
    // 3. 如果即将通路（針對向後周遊的方向）的元素為null，則取尾結點作為即将通路的元素，也作為上一次通路的元素（針對下一輪的通路）；否則取前驅節點作為即将通路的節點
    lastReturned = next = (next == null) ? last : next.prev;
    // 4. 下一次需要通路的元素索引是以減1
    nextIndex--;
    // 5. 傳回本次通路的元素值
    return lastReturned.item;
}

1.5、删除元素

iterator的删除方法操作的剛剛通路過的元素，需要依賴于lastReturned屬性，其具體業務邏輯過程如下：

1. 并發修改校驗，避免其他線程修改連結清單

2. 如果還沒有通路元素，則不能執行删除操作，則抛出異常

3. 擷取上一次通路的元素的後繼節點（主要是為了反向周遊時服務）

4. 删除上一次通路的元素：unlink(lastReturned)，具體參考之前unlink方法的講解

5. 如果是next==lastReterned，表示是反向周遊，則更新正向周遊的即将通路的節點是删除節點的後繼節點

6. 如果是正向周遊的情況，則下一次即将通路的節點的索引減1即可

7. 上一次通路的元素設定為null（針對下一次的通路）

8. 修改連結清單結構的次數加1，與外部類保持一緻(unlink(lastReturned)方法會更新“修改連結清單結構的次數”的值)

public void remove() {
    // 1. 并發修改校驗，避免其他線程修改連結清單
    checkForComodification();
    // 2. 如果還沒有通路元素，則不能執行删除操作，則抛出異常
    if (lastReturned == null)
            throw new IllegalStateException();
    // 3. 上一次通路的元素的後繼節點作為上一次通路的元素
     Node<E> lastNext = lastReturned.next;
    // 4.  删除上一次通路的元素
     unlink(lastReturned);
    // 5. 如果是next==lastReterned，表示是反向周遊，則更新向後周遊的下一個通路節點是删除節點的後繼節點
    if (next == lastReturned)
            next = lastNext;
    else
    // 6. 如果是向後周遊的情況，則下一次即将通路的節點的索引減1即可
     nextIndex--;
    // 7. 上一次通路的元素設定為null（針對下一次的通路）
    lastReturned = null;
    // 8. 修改連結清單結構的次數加1，與外部類保持一緻(unlink(lastReturned)方法會更新“修改連結清單結構的次數”的值)
    expectedModCount++;
}

1.6、添加元素

添加元素其具體業務邏輯過程如下：

1. 并發校驗，避免與其他線程同時修改導緻問題，若多線程操作，則會阻斷

2. 上一次通路的元素重置為null（針對下一次的通路）

3. 如果即将通路的元素為null，則追加至連結清單尾部（具體參考linkLast的講解）

4. 否則，将元素追加至即将通路的前面，作為前驅節點（具體參考在指定位置添加元素的講解）

5. 因為在即将通路的元素之前加了一個節點，則即将通路的索引加1

6. 由于前面追加元素的方法（步驟3、4）會更新“修改連結清單結構的次數”，Iterator中的也需要同步更新，保持一緻，否則會出現并發修改異常

public void add(E e) {
        // 1. 并發校驗，避免與其他線程同時修改導緻問題，若多線程操作，則會阻斷
       checkForComodification();
       // 2. 上一次通路的元素重置為null（針對下一次的通路）
        lastReturned = null;
       // 3. 如果即将通路的元素為null，則追加至連結清單尾部
        if (next == null)
            linkLast(e);
        else
       // 4. 否則，将元素追加至即将通路的前面，作為前驅節點
            linkBefore(e, next);
       // 5. 因為在即将通路的元素之前加了一個節點，則即将通路的索引加1
        nextIndex++;
       // 6. 由于前面追加元素的方法會更新“修改連結清單結構的次數”，
       // Iterator中的也需要同步更新，保持一緻，否則會出現并發修改異常
        expectedModCount++;
    }

1.7、更新元素的值

更新上一次通路的元素的值相對比較簡單，其業務邏輯過程如下：

1. 如果還沒有通路過任何元素，則抛出狀态非法的異常

2. 并發修改校驗，避免節點被删除

3. 設定節點的值

public void set(E e) {
        // 如果沒有通路過的元素，則不能更新值
        if (lastReturned == null)
            throw new IllegalStateException();
        // 并發校驗, 避免節點被删除
        checkForComodification();
        // 設定通路的節點的值
       lastReturned.item = e;
}

1.8、疊代器全部代碼

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);
// 如果索引等于元素數量，則通路的元素為null，因為下标從0開始，若index==size，則通路不到任何元素；否則即将通路的元素等于該索引位置的元素
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

    public  oolean hasNext() {
        //即将通路的索引是否小于元素數量，小于則表示存在元素，可以通路；否則表示沒有元素，不能通路
return nextIndex < size;
    }

    public E next() {
// 并發修改校驗，避免其他線程同時修改連結清單(添加或者删除元素)
        checkForComodification();
// 通路元素時再次校驗目前即将通路的索引是否有元素，沒有則抛出異常，避免在并發校驗之後又有線程操作連結清單
        if (!hasNext())
            throw new NoSuchElementException();

        // 将即将通路的節點作為上一次通路的節點(相對下一次通路)
lastReturned = next;
// 下一次即将需要通路的節點後移
        next = next.next;
// 下一次即将通路的節點的索引後移
        nextIndex++;
// 傳回目前元素的值
        return lastReturned.item;
    }

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


    public E previous() {
// 并發修改校驗
        checkForComodification();
// 如果目前節點沒有前驅節點，則抛出異常，避免在并發校驗之後，又有其他線程修改了連結清單（添加、删除元素）
        if (!hasPrevious())
            throw new NoSuchElementException();
// 如果即将通路（針對向後周遊的方向）的元素為null，則取尾結點作為即将通路的元素，也作為上一次通路的元素（針對下一輪的通路）；否則取前驅節點作為即将通路的節點
        lastReturned = next = (next == null) ? last : next.prev;
// 下一次需要通路的元素索引是以減1
        nextIndex--;
// 傳回本次通路的元素值
        return lastReturned.item;
    }

    public int nextIndex() {
        return nextIndex;
    }

    public int previousIndex() {
        return nextIndex – 1;
    }

    public void remove() {
        // 并發修改校驗
checkForComodification();
// 如果還沒有通路元素，則抛出異常
        if (lastReturned == null)
            throw new IllegalStateException();
// 上一次通路的元素的後繼節點作為上一次通路的元素
        Node<E> lastNext = lastReturned.next;
// 删除上一次通路的元素
        unlink(lastReturned);
// 如果是next==lastReterned，表示是向前周遊，則更新向後周遊的下一個通路節點是删除節點的後繼節點
        if (next == lastReturned)
            next = lastNext;
        else
// 如果是向後周遊的情況，則下一次即将通路的節點的索引減1即可
            nextIndex--;
// 上一次通路的元素設定為null（針對下一次的通路）
        lastReturned = null;
// 修改連結清單結構的次數加1，與外部類保持一緻(unlink(lastReturned)方法會更新“修改連結清單結構的次數”的值)
        expectedModCount++;
    }

    public void set(E e) {
// 如果沒有通路過的元素，則不能更新值
        if (lastReturned == null)
            throw new IllegalStateException();
        // 并發校驗, 避免節點被删除
checkForComodification();
        // 設定通路的節點的值
lastReturned.item = e;
    }

    public void add(E e) {
        // 并發校驗，避免與其他線程同時修改導緻問題，若多線程操作，則會阻斷
checkForComodification();
// 上一次通路的元素重置為null（針對下一次的通路）
        lastReturned = null;
如果即将通路的元素為null，則追加至連結清單尾部
        if (next == null)
            linkLast(e);
        else
// 否則，将元素追加至即将通路的前面，作為前驅節點
            linkBefore(e, next);
// 因為在即将通路的元素之前加了一個節點，則即将通路的索引加1
        nextIndex++;
// 由于前面追加元素的方法會更新“修改連結清單結構的次數”，Iterator中的也需要同步更新，保持一至，否則會出現并發修改異常
        expectedModCount++;
    }

    public void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (modCount == expectedModCount && nextIndex < size) {
            action.accept(next.item);
            lastReturned = next;
            next = next.next;
            nextIndex++;
        }
        checkForComodification();
    }

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

2、設定指定索引的值

public E set(int index, E element) {
// 校驗索引是否合法，不合法則抛出異常
    checkElementIndex(index);
// 根據索引擷取指定節點的值，具體參考之前的方法解析
    Node<E> x = node(index);
// 擷取節點的資料項
    E oldVal = x.item;
// 更新節點的資料項為指定的值
    x.item = element;
// 傳回原來的資料項
    return oldVal;
}

3、擷取指定對象的索引

擷取指定對象的索引相對簡單，其業務邏輯過程如下：

1. 初始化索引位置為0

2. 若指定對象為空，則從頭結點元素開始周遊，使用==判斷節點元素是否于null相等，相等則傳回對應的索引，否則繼續進行下一輪周遊

3. 若對象不為空，則從頭節點元素開始周遊，使用equals判斷節點元素是否等于指定的值，相等則傳回對應的索引，否則繼續進行下一輪周遊

4. 如果不存在這樣的節點，則傳回-1

public int indexOf(Object o) {
    // 1. 初始化索引位置為0
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
          // 2. 若指定對象為空，則從頭結點元素開始周遊，
          // 使用==判斷節點元素是否于null相等，相等則傳回對應的索引，否則繼續進行下一輪周遊
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
             // 3.若對象不為空，則從頭節點元素開始周遊，
             // 使用equals判斷節點元素是否等于指定的值，相等則傳回對應的索引，否則繼續進行下一輪周遊
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
  // 如果不存在這樣的節點，則傳回-1
    return -1;
}

4、将連結清單轉為Object數組

LinkedList轉為數組的方式比較簡單，沒有借助任何工具類；業務邏輯過程如下：

1. 初始化一個Object數組，大小是LinkedList的元素數量

2. 從頭開始周遊LinkedList，依次将節點元素的資料項放入數組中

public Object[] toArray() {
  // 初始化一個Object數組，大小是LinkedList的元素數量
    Object[] result = new Object[size];
    int i = 0;
    for (Node<E> x = first; x != null; x = x.next)
       // 從頭開始周遊LinkedList，依次将節點元素的資料項放入數組中
        result[i++] = x.item;
    return result;
}

5、将連結清單轉為指定類型的數組

相比于将連結清單轉為Object數組，将連結清單轉為指定類型的數組會多一些處理，具體業務邏輯過程如下：

1. 如果入參的數組a的長度比連結清單的元素數量小，則需要建立一個數組；否則使用入參數組；

2. 從頭開始周遊LinkedList，依次将節點元素的資料項放入數組中

3. 轉換之後，如果入參數組a的長度比連結清單的元素數量大，則數組中新的結束位置設定為null

public <T> T[] toArray(T[] a) {
  // 1、如果入參的數組a的長度比連結清單的元素數量小, 則需要建立一個數組；否則使用入參數組；
    if (a.length < size)
        a = (T[])java.lang.reflect.Array.newInstance(
                            a.getClass().getComponentType(), size);
    int i = 0;
    Object[] result = a;
  // 2. 從頭開始周遊LinkedList，依次将節點元素的資料項放入數組中
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;
  // 轉換之後，如果入參數組a的長度比連結清單的元素數量大，則數組中新的結束位置設定為null
    if (a.length > size)
        a[size] = null;

    return a;
}

需要注意的是：此方式傳回的數組與清單也不會互相影響，如果數組a的長度能夠存儲清單中的元素，則将元素存入數組中，然後傳回數組a；如果數組a容量不足以存儲清單中的元素，則傳回一個新的數組；但是這裡有一個問題，如果數組a的長度遠大清單的長度，則數組a中，清單長度之外的元素還會存在于數組a中。

例如：
清單元素：[1, 2]
原數組元素：[a,b,c,d,e,f,g,h]
新數組元素：[1,2,null,d,e,f,g,h]

6、擷取子清單（subList）

subList方法傳回的是AbstractList的内部類SubList的對象，擁有與LinkedList相同的功能；資料源還是LinkedList中的元素；SubList中的方法都需要進行并發修改校驗，同時修改操作都是依托于LinkedList類的對象，直接操作LinkedList對象的元素節點（添加元素、删除元素、通路元素等）；由于LinkedList沒有實作RandomAccess接口，是以隻能是傳回SubList類的對象

public List<E> subList(int fromIndex, int toIndex) {
    return (this instanceof RandomAccess ?
            new RandomAccessSubList<>(this, fromIndex, toIndex) :
            new SubList<>(this, fromIndex, toIndex));
}

7、總結：

需要通過索引去查找節點時，使用的是二分查找法（索引位置和list的長度作二分對比）
在進行節點操作時，需要考慮前後節點是否為null的情況，并且需要對first和last節點進行指派
對LinkedList進行周遊時，推薦使用iterator或者加強版的for循環，不能使用下标方式的for循環，因為LinkedList根據索引位置擷取元素是需要從頭部或者尾部周遊元素的，相對會很消耗時間

輕松解讀源碼系列之Java集合LinkedList（下）

1、疊代器

1.1、底層資料結構

1.2、構造函數

1.3、正向周遊元素

1.4、反向周遊元素

1.5、删除元素

1.6、添加元素

1.7、更新元素的值

1.8、疊代器全部代碼

2、設定指定索引的值

3、擷取指定對象的索引

4、将連結清單轉為Object數組

5、将連結清單轉為指定類型的數組

6、擷取子清單（subList）

7、總結：

繼續閱讀

Ambry：LinkedIn開源的可擴充分布式對象存儲系統

JUC - BlockingQueue

從源碼全面解析LinkedBlockingQueue的來龍去脈

一個新的AI聊天機器人PI誕生了，對話十分流暢自然，支援語音輸出，UI設計很優雅，将機器人的思考展現在了輸出動畫裡。支援

ArrayList和LinkedList怎麼選，想過嗎？

從 LinkedIn 到 TikTok：新移民如何利用社交媒體在加拿大取得成功

Linkedin要離開中國了做外貿的同行有想法嗎？好像前年開始，國内版本隻作為職場内容，但是越獄還是可以使用，不知道八月

怎麼給領英群組(LinkedIn Group)内的客戶批量發消息添加好友？

Win11預覽版LinkedIn應用上架微軟商城

從Linkedin案例學習怎樣培養人脈，從“弱關系”到“強關系”

外貿&職場-工具&黑科技10000+#外貿#Google#高效辦公#新客戶開發#Linkedin

1900名全球高管、86頁幹貨：LinkedIn釋出B2B營銷基準報告

綠色生态可持續：LinkedIn領英活力動态的混合園區總部設計

Java LinkedList 雙向連結清單實作原理

WhatsAPP找客戶給大家推薦一個超好用的工具，Linkedln，Facebook，GoogleInstagram等9

LeetCode-Linked List Cycle II