• 推薦閱讀：
• <strong>
  
• <strong>
  
• <strong>
  

前言

LinkedList由於實現了Deque這個接口，所以可以當棧和隊列使用。不過一般要用棧或隊列的時候推薦使用ArrayDeque,所以這裡就不講LinkedList的棧和隊列功能了。還是和上篇ArrayList一樣，講些常用的方法。

LinkedList內部是由雙鏈表組成的，裡面存放著一個個Node，每個Node又包含三個元素(prev,item,next):

• prev:指向前一個Node
• item:存放存入的數據
• next:指向下一個Node

鏈表的第一個Node的prev為null，最後個Node的next為null

我簡單的畫了一張圖，可以看下

這個prev和next並不是指向null，因為內存中沒有為null分配空間，這邊是表示是prev和next為null；

本文內容

01 內部變量

相比於Arraylist，LinkedList內部變量就少得多，就只有三個，size存這當前元素的個數，first指向鏈表的第一個，last指向列表的最後一個

02 構造方法

2.1 無參構造方法

（1）代碼實現

<code>List<string>list=newLinkedList<>();/<string>/<code> 

（2）源碼分析

無參構造只是初始化了數據，並未做任何操作(初始化 size=0 first=null last=null)

2.2 有參構造方法

（1）代碼實現

<code>List<string>oldList=newLinkedList<>();List<string>newList=newLinkedList<>(oldList);/<string>/<string>/<code>

（2）源碼分析

由於篇幅有限，addAll()方法這邊就不講了，後面另寫文章再講，裡面的操作就相當於把集合裡的元素複製到新集合裡面。

03 get方法

3.1 get(int index)

這裡先講get()方法，然後再講add()方法，原因是插入方法裡用到的調用的方法個get()方法裡是一樣的

（1）代碼實現

<code>List<string>list=newLinkedList<>();list.add("hui");list.add("灰");list.add("灰2");list.add("灰3");list.get(2);/<string>/<code>

（2）源碼分析

• checkElementIndex(int index)檢查越界

• node(int index)查找Node

04 add方法

4.1 add(E e)

（1）代碼實現

<code>List<string>list=newLinkedList<>();list.add("hui");/<string>/<code>

（2）源碼分析

• linkLast(E e)連接最後一個元素

• Node內部類

就像開頭說的，每個Node裡有三個，prev:指向前一個Node，item:存放存入的數據，next:指向下一個Node

<code>privatestaticclassNode{Eitem;Nodenext;Nodeprev;Node(Nodeprev,Eelement,Nodenext){this.item=element;this.next=next;this.prev=prev;}}/<code>

（3）流程圖

• 第一次添加時的流程示意圖

第一次添加時的流程示意圖

• 不是第一次添加

不是第一次添加

4.2 add(int index, E element)

（1）代碼實現

<code>List<string>list=newLinkedList<>();list.add("hui");list.add("灰");list.add(1,"hk");/<string>/<code>

（2）源碼分析

這邊插入元素時，先判斷插入的位置是不是尾部，如果不尾部的話，先調用和get()那個一樣的方法，來查找要插入位置的當前元素，然後進行插入操作

• checkPositionIndex(int index)檢查是否越界

這個檢查越界的方法個get()檢查越界的方法有點不同，它是可以等於size的，因為linkedList的索引設計也是從0開始的，

• linkBefore(E e, Node succ)插入元素操作

（3）流程圖

上面說的可能有點繞，看看流程圖就明白了，哈哈

• 添加的位置為第一個

添加的位置為第一個

• 添加的位置為中間

添加的位置為中間

05 set方法

5.1 set(int index, E element)

（1）代碼實現

<code>List<string>list=newLinkedList<>();list.add("hui");list.set(0,"灰");/<string>/<code>

（2）源碼解析

這裡大多調用的是和get()裡一樣的方法

06 remove方法

6.1 remove(int index)

按索引刪除，先找到被刪除的Node，然後解除相關鏈接，設置Node裡三大元素為null，刪除後返回被刪除Node裡的item

（1）代碼實現

<code>List<string>list=newLinkedList<>();list.add("hui");list.add("灰");list.remove(1);/<string>/<code>

（2）源碼解析

• unlink(Node x)解除Node的連接，然後返回被解除鏈接的item

（3）流程圖

• 刪除的是鏈表裡的第一個元素

刪除的是鏈表裡的第一個元素

• 刪除的是鏈表裡的中間元素

• 刪除的是鏈表裡的最後一個元素

6.2 remove(Object o)

這個刪除就比較慢了，它內部沒有用二分查找算法，而是從頭開始一一對比，時間複雜度為O(n)，這個刪除也是

（1）代碼實現

<code>List<string>list=newLinkedList<>();list.add("hui");list.remove("hui");/<string>/<code>

（2）源碼解析

unlink()方法就是上面講的那個

07 clear方法

7.1 clear()

（1）代碼實現

<code>List<string>list=newLinkedList<>();list.add("hui");list.clear();/<string>/<code>

（2）源碼解析

總結

LinkedList裡刪除，添加操作一般就兩個步驟，變換前後Node指向的地址，刪除操作把對應Node裡的三個變量都設置為null，方便GC回收。

如果要刪除元素時，最好選擇傳入索引刪除，他比直接傳入要刪除的對象的方法要快很多

作者：灰灰H_K
原文鏈接：https://juejin.im/post/5e12861b6fb9a0481d28b510

閱讀更多 追逐仰望星空 的文章

關鍵字: 面試題 設計 Java虛擬機