LinkedList源碼分析：JDK源碼分析系列

如果本文中有不正確的地方請指出

由於沒有留言可以在公眾號添加我的好友共同討論。

1.介紹

LinkedList 是線程不安全的，允許元素為null的雙向鏈表。

2.繼承結構

我們來看一下LinkedList的繼承結構圖：

代碼實現:

public class LinkedList
 extends AbstractSequentialList
 implements List, Deque, Cloneable, java.io.Serializable

• Cloneable實現克隆
• Serializable序列化
• List 定義了一些集合類的方法
• Deque雙向隊列接口(就是兩端都可以進行增加刪除操作)

注意一點LinkedList並沒有實現RandomAccess所以隨機訪問是非常慢的。

3.屬性

元素個數

transient int size = 0;

指向第一個節點的指針(註釋直接就寫著)

 /**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 * (first.prev == null && first.item != null) 

 */
 transient Node first;

指向最後一個節點的指針

 /**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 * (last.next == null && last.item != null)
 */
 transient Node last;

transient關鍵字的作用是保持變量不被序列化具體的百度。

不過我們注意到LinkedList是有Node類，這裡的Node是一個內部類：

• item存儲的元素
• next指向後置節點
• prev指向前置節點
• 內部類同時包含了一個構造函數

其實LinkedList 集合就是由許多個 Node 對象y一個連著一個組成手構成，可以看下方的圖

可以看上面的四個元素，分別就是四個Node對象，可以看到node1所指向的prev上一個節點是空也就是沒有上節點,node4所指向的next節點為空也就是沒有下一個節點。

4.構造方法

LinkedList共有兩個構造方法，一個是創建一個空的構造函數，一個是將已有的Collection添加到LinkedList中。

因為LinkedList不同於ArrayList所以初始化不需要指定大小取分配內存空間。

5.添加元素

LinkedList有幾種添加方法我們先從add()開始。

5.1 add方法

checkPositionIndex(index);

可以看到在調用Add方法首先校驗一下索引是否合法，如果不合法就會拋出異常。

if (index == size)
 linkLast(element);
 else
 linkBefore(element, node(index));

然後如果索引值等於size的值則直接調用linkLast插入到尾部節點。

否則就linkBefore方法。linkLast方法：

void linkLast(E e) {
 //將l設為尾節點
 final Node l = last;
 //構造一個新節點，節點上一個節點引用指向尾節點l
 final Node newNode = new Node<>(l, e, null);
 //將尾節點設為創建的新節點
 last = newNode;
 //如果尾節點為空，表示原先鏈表為空
 if (l == null)
 //將頭節點設為新創建的節點（尾節點也是新創建的節點）
 first = newNode;
 else
 //將原來尾節點下一個節點的引用指向新節點
 l.next = newNode;
 size++;//節點數加1
 modCount++; 

 }

注意一下這裡出現了modCount方法，和ArrayList中一樣，iterator和listIterator方法返回的迭代器和列表迭代器實現使用。linkBefore:

void linkBefore(E e, Node succ) {
 //將pred設為插入節點的上一個節點
 final Node pred = succ.prev;
 //將新節點的上引用設為pred,下引用設為succ
 final Node newNode = new Node<>(pred, e, succ);
 //succ的上一個節點的引用設為新節點
 succ.prev = newNode;
 //如果插入節點的上一個節點引用為空
 if (pred == null)
 //新節點就是頭節點
 first = newNode;
 else
 //插入節點的下一個節點引用設為新節點
 pred.next = newNode;
 size++;
 //同上
 modCount++;
 }

5.2 addAll()

在LinkedList中有兩個addAll方法一個是 addAll(Collection c)一個是addAll(int index, Collection c),其實

addAll(Collection c)=addAll(int index, Collection c)

可以看下面的截圖:

源碼如下：

現在開始分析源碼：首先我們可以看到先調用了checkPositionIndex(index);方法來檢查索引是否合法。然後將傳進來的Collection轉成Object數組

 Object[] a = c.toArray();

如果集合為空就直接返回false

if (numNew == 0)
 return false;

如果插入的位置等於鏈表的長度就把新增加的元素放在尾部。

Node pred, succ;
 if (index == size) {
 succ = null;
 pred = last;
 } else {
 succ = node(index);
 pred = succ.prev;
 }

最後在循環要插入的元素。這裡我們可以看到上面也有modCount。

5.3 addFirst()

addFirst是將元素插入到LinkedList的頭部。如果現在的機構是下圖的：

addFirst執行的操作就是：

紅色是使用addFirst插入後的位置。一下是源碼

調用了linkFirst方法。

上面的操作時：

• 首先執行final Node f = first;將頭節點賦值給 f
• final Node newNode = new Node<>(null, e, f);將指定元素構造成一個新節點，此節點的指向下一個節點的引用為頭節點

 //將新節點設為頭節點，那麼原先的頭節點 f 變為第二個節點 

 first = newNode;
 //如果第二個節點為空，也就是原先鏈表是空
 if (f == null)
 //將這個新節點也設為尾節點（前面已經設為頭節點了）
 last = newNode;
 else
 f.prev = newNode;//將原先的頭節點的上一個節點指向新節點
 size++;//節點數加1
 modCount++;//和ArrayList中一樣記錄修改次數

5.4 addLast方法

addLast是將元素插入到尾部如圖(黃色元素)：

黃色node是新增加。注意add也是把元素添加到尾部。我們來看一下源碼：

這裡看到addLast和add是調用的同一方法，這裡就不在講解。可以看上方的代碼。

由於文章比較長分為兩次更新。下一篇文章繼續分析

上次分析了LinkedList的結構和添加方法這次開始分析下面的。

注意源碼版本為JDK1.8

直接進入正題。

1.刪除

1.2remove()

在LinkedList中remove()和removeFirst()是相同的

在LinkedList中的刪除其實就是通過修改上一個節點和指向下一個節點的引用完成的,可以看下面的圖片：

我們可以看到把node6的prev指向清空然後把node3的next設置成空就完成了刪除的操作。看一下JDK的源碼實現：

調用removeFirst,在調用removeFirst中先獲取頭部節點，如果頭節點為空就拋異常。

調用unlinkFirst

private E unlinkFirst(Node f) {
 final E element = f.item;
 //next 為頭結點的下一個節點
 final Node next = f.next;
 f.item = null;
 // 將節點的元素以及引用都設為 null，便於垃圾回收
 f.next = null;  

 //修改頭結點為第二個節點
 first = next; 
 //如果第二個節點為空（當前鏈表只存在第一個元素）
 if (next == null)
 //那麼尾節點也置為 null
 last = null;
 else
 //如果第二個節點不為空，那麼將第二個節點的上一個引用置為 null
 next.prev = null;
 size--;
 modCount++;
 return element;
 } 

1.3 removeLast()

我們看一下removeLast，從列表中刪除最後一個元素

首先看到先獲取了last最後一個元素，如果為空然後就拋異常然後調用了unlinkLast

看到unlinkLast方法中有一個 help gc ,它的主要作用就是幫助GC來做垃圾回收。

private E unlinkLast(Node l) {
 // assert l == last && l != null;
 final E element = l.item;
 final Node prev = l.prev;
 l.item = null;
 //幫助GC垃圾回收 

 l.prev = null;
 //尾節點為倒數第二個節點
 last = prev;
 //如果倒數第二個節點為null
 if (prev == null)
 //那麼將節點也置為 null
 first = null;
 else
 prev.next = null;
 //如果倒數第二個節點不為空，那麼將倒數第二個節點的下一個引用置為 null
 size--;
 modCount++;
 return element;
 }

同樣執行了modCount++

1.3 remove(int index)

根據索引來刪除元素

 //刪除此列表中指定位置的元素
 public E remove(int index) {
 //判斷索引 index >= 0 && index <= size中時拋出IndexOutOfBoundsException異常
 checkElementIndex(index);
 return unlink(node(index));
 }
 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) {//如果刪除節點位置的上一個節點引用為null（表示刪除第一個元素） 

 first = next;//將頭結點置為第一個元素的下一個節點
 } else {//如果刪除節點位置的上一個節點引用不為null
 prev.next = next;//將刪除節點的上一個節點的下一個節點引用指向刪除節點的下一個節點（去掉刪除節點）
 x.prev = null;//刪除節點的上一個節點引用置為null
 }
 
 if (next == null) {//如果刪除節點的下一個節點引用為null（表示刪除最後一個節點）
 last = prev;//將尾節點置為刪除節點的上一個節點
 } else {//不是刪除尾節點
 next.prev = prev;//將刪除節點的下一個節點的上一個節點的引用指向刪除節點的上一個節點
 x.next = null;//將刪除節點的下一個節點引用置為null
 }
 //刪除節點內容置為null，便於垃圾回收
 x.item = null;
 size--;
 modCount++;
 return element;
 }

3.set(int index, E element)

簡單粗暴直接貼代碼

public E set(int index, E element) {
 //檢查索引是否合法否則IndexOutOfBoundsException異常
 checkElementIndex(index);
 //獲取指定索引的元素
 Node x = node(index);
 E oldVal = x.item;
 //將指定索引的元素替換成新的元素
 x.item = element;
 /返回指定索引位置原來的元素
 return oldVal;/
 }

4.查找元素

很簡單

4.1 getFirst()

返回第一個元素

 public E getFirst() {
 獲取頭
 final Node f = first;
 判斷是否為空
 if (f == null)
 throw new NoSuchElementException();
 元素返回
 return f.item;
 }

4.2 getLast()

返回最後一個元素

public E getLast() {
 final Node l = last;
 if (l == null)
 throw new NoSuchElementException();
 return l.item;
 }

4.3 get

返回指定索引元素

public E get(int index) {
 checkElementIndex(index);
 return node(index).item;
 }

暫時就這麼多

原創不易,如果你喜歡本文或者對你有幫助就請轉發

本文由博客一文多發平臺 https://openwrite.cn?from=article_bottom 發佈！