【源碼解析】面試必問的LinkedList,看這篇文章就夠了

NO IMAGE

積千里跬步,匯萬里江河;每天進步一點點,終有一天將成大佬。

本文基於JDK1.8

前言

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

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

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

鏈表的第一個Nodeprevnull,最後個Nodenextnull

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

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

【源碼解析】面試必問的LinkedList,看這篇文章就夠了

本文內容

【源碼解析】面試必問的LinkedList,看這篇文章就夠了

內部變量

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

【源碼解析】面試必問的LinkedList,看這篇文章就夠了

構造方法

無參構造方法

代碼實現

List<String> list=new LinkedList<>();

源碼分析

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

【源碼解析】面試必問的LinkedList,看這篇文章就夠了

有參構造方法

代碼實現

List<String> oldList=new LinkedList<>();
List<String> newList=new LinkedList<>(oldList);

源碼分析

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

【源碼解析】面試必問的LinkedList,看這篇文章就夠了

get方法

get(int index)

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

代碼實現

List<String> list=new LinkedList<>();
list.add("hui");
list.add("灰");
list.add("灰2");
list.add("灰3");
list.get(2);

源碼分析

【源碼解析】面試必問的LinkedList,看這篇文章就夠了
  • checkElementIndex(int index)檢查越界
【源碼解析】面試必問的LinkedList,看這篇文章就夠了
【源碼解析】面試必問的LinkedList,看這篇文章就夠了
  • node(int index)查找Node
【源碼解析】面試必問的LinkedList,看這篇文章就夠了

add方法

add(E e)

代碼實現

List<String> list=new LinkedList<>();
list.add("hui");

源碼分析

【源碼解析】面試必問的LinkedList,看這篇文章就夠了
  • linkLast(E e)連接最後一個元素
【源碼解析】面試必問的LinkedList,看這篇文章就夠了
  • Node<E>內部類

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

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

流程圖

  • 第一次添加時的流程示意圖
【源碼解析】面試必問的LinkedList,看這篇文章就夠了
第一次添加時的流程示意圖
  • 不是第一次添加
【源碼解析】面試必問的LinkedList,看這篇文章就夠了
不是第一次添加

add(int index, E element)

代碼實現

List<String> list=new LinkedList<>();
list.add("hui");
list.add("灰");
list.add(1,"hk");

源碼分析

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

【源碼解析】面試必問的LinkedList,看這篇文章就夠了
  • checkPositionIndex(int index)檢查是否越界

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

【源碼解析】面試必問的LinkedList,看這篇文章就夠了
【源碼解析】面試必問的LinkedList,看這篇文章就夠了
  • linkBefore(E e, Node<E> succ)插入元素操作
【源碼解析】面試必問的LinkedList,看這篇文章就夠了

流程圖

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

  • 添加的位置為第一個
【源碼解析】面試必問的LinkedList,看這篇文章就夠了
添加的位置為第一個
  • 添加的位置為中間
【源碼解析】面試必問的LinkedList,看這篇文章就夠了
添加的位置為中間

set方法

set(int index, E element)

代碼實現

List<String> list=new LinkedList<>();
list.add("hui");
list.set(0,"灰");

源碼解析

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

【源碼解析】面試必問的LinkedList,看這篇文章就夠了

remove方法

remove(int index)

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

代碼實現

List<String> list=new LinkedList<>();
list.add("hui");
list.add("灰");
list.remove(1);

源碼解析

【源碼解析】面試必問的LinkedList,看這篇文章就夠了
  • unlink(Node<E> x)解除Node的連接,然後返回被解除鏈接的item
【源碼解析】面試必問的LinkedList,看這篇文章就夠了

流程圖

  • 刪除的是鏈表裡的第一個元素
【源碼解析】面試必問的LinkedList,看這篇文章就夠了
刪除的是鏈表裡的第一個元素
  • 刪除的是鏈表裡的中間元素
【源碼解析】面試必問的LinkedList,看這篇文章就夠了
  • 刪除的是鏈表裡的最後一個元素
【源碼解析】面試必問的LinkedList,看這篇文章就夠了

remove(Object o)

這個刪除就比較了,它內部沒有用二分查找算法,而是從頭開始一一對比,時間複雜度為O(n),這個刪除也是只刪除最早添加的數據

代碼實現

List<String> list=new LinkedList<>();
list.add("hui");
list.remove("hui");

源碼解析

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

【源碼解析】面試必問的LinkedList,看這篇文章就夠了

clear方法

clear()

代碼實現

List<String> list=new LinkedList<>();
list.add("hui");
list.clear();

源碼解析

【源碼解析】面試必問的LinkedList,看這篇文章就夠了

總結

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

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

相關文章

Kotlin協程:Coroutine/Channel/Flow以及實際應用

css容易使人蒙圈的幾個經典問題

自從學會了Array.reduce(),再也離不開它

瓜子二手車在Dubbo版本升級、多機房方案方面的思考和實踐