Java集合之LinkedList源碼解析
簡介
本章我們來聊聊LinkedList的使用及源碼，LinkedList和ArrayList數(shù)據(jù)結(jié)構(gòu)是完全不一樣的，
ArrayList 底層是數(shù)組的結(jié)構(gòu)，而 LinkedList 的底層則是鏈表的結(jié)構(gòu)， 它可以進行高效的插入和移除的操作，它基于的是一個雙向鏈表的結(jié)構(gòu)。
LinkedList的整體結(jié)構(gòu)圖
從圖中也能看出，LinkedList 有好多的Node，并且還有first和last這兩個變量保存頭部和尾部節(jié)點的信息；還有就是它不是一個循環(huán)的雙向鏈表，因為它前后都是null，這個也是我們需要注意的地方。
繼承體系
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{...}通過繼承體系，我們可以看到 LinkedList 不僅實現(xiàn)了List接口，還實現(xiàn)了Queue和Deque接口，所以它既能作為 List 使用，也能作為雙端隊列使用，當(dāng)然也可以作為棧使用。
源碼分析
主要屬性
// 元素個數(shù) transient int size = 0; // 鏈表首節(jié)點 transient Node<E> first; // 鏈表尾節(jié)點 transient Node<E> last;
Node節(jié)點
private static class Node<E> {
//值
E item;
//后繼 指向下一個的引用
Node<E> next;
//前驅(qū) 指向前一個的引用
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}構(gòu)造方法
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
//將集合C中的所有的元素都插入到鏈表中
addAll(c);
}添加元素
作為一個雙端隊列，添加元素主要有兩種，一種是在隊列尾部添加元素，一種是在隊列首部添加元素，這兩種形式在LinkedList中主要是通過下面兩個方法來實現(xiàn)的。
// 從隊列首添加元素
private void linkFirst(E e) {
// 首節(jié)點
final Node<E> f = first;
// 創(chuàng)建新節(jié)點，新節(jié)點的next是首節(jié)點
final Node<E> newNode = new Node<>(null, e, f);
// 讓新節(jié)點作為新的首節(jié)點
first = newNode;
// 判斷是不是第一個添加的元素
// 如果是就把last也置為新節(jié)點
// 否則把原首節(jié)點的prev指針置為新節(jié)點
if (f == null)
last = newNode;
else
f.prev = newNode;
// 元素個數(shù)加1
size++;
// 修改次數(shù)加1，說明這是一個支持fail-fast的集合
modCount++;
}
// 從隊列尾添加元素
void linkLast(E e) {
// 隊列尾節(jié)點
final Node<E> l = last;
// 創(chuàng)建新節(jié)點，新節(jié)點的prev是尾節(jié)點
final Node<E> newNode = new Node<>(l, e, null);
// 讓新節(jié)點成為新的尾節(jié)點
last = newNode;
// 判斷是不是第一個添加的元素
// 如果是就把first也置為新節(jié)點
// 否則把原尾節(jié)點的next指針置為新節(jié)點
if (l == null)
first = newNode;
else
l.next = newNode;
// 元素個數(shù)加1
size++;
// 修改次數(shù)加1
modCount++;
}
public void addFirst(E e) {
linkFirst(e);
}
public void addLast(E e) {
linkLast(e);
}
// 作為無界隊列，添加元素總是會成功的
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
public boolean offerLast(E e) {
addLast(e);
return true;
}上面是作為雙端隊列來看，它的添加元素分為首尾添加元素，作為List，是要支持在中間添加元素的，主要是通過下面這個方法實現(xiàn)的。
// 在節(jié)點succ之前添加元素
void linkBefore(E e, Node<E> succ) {
// succ是待添加節(jié)點的后繼節(jié)點
// 找到待添加節(jié)點的前置節(jié)點
final Node<E> pred = succ.prev;
// 在其前置節(jié)點和后繼節(jié)點之間創(chuàng)建一個新節(jié)點
final Node<E> newNode = new Node<>(pred, e, succ);
// 修改后繼節(jié)點的前置指針指向新節(jié)點
succ.prev = newNode;
// 判斷前置節(jié)點是否為空
// 如果為空，說明是第一個添加的元素，修改first指針
// 否則修改前置節(jié)點的next為新節(jié)點
if (pred == null)
first = newNode;
else
pred.next = newNode;
// 修改元素個數(shù)
size++;
// 修改次數(shù)加1
modCount++;
}
// 尋找index位置的節(jié)點
Node<E> node(int index) {
// 因為是雙鏈表
// 所以根據(jù)index是在前半段還是后半段決定從前遍歷還是從后遍歷
// 這樣index在后半段的時候可以少遍歷一半的元素
if (index < (size >> 1)) {
// 如果是在前半段
// 就從前遍歷
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 如果是在后半段
// 就從后遍歷
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
// 在指定index位置處添加元素
public void add(int index, E element) {
// 判斷是否越界
checkPositionIndex(index);
// 如果index是在隊列尾節(jié)點之后的一個位置
// 把新節(jié)點直接添加到尾節(jié)點之后
// 否則調(diào)用linkBefore()方法在中間添加節(jié)點
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}在中間添加元素的方法也很簡單，典型的雙鏈表在中間添加元素的方法。
添加元素的三種方式大致如下圖所示：
在隊列首尾添加元素很高效，時間復(fù)雜度為O(1)。
在中間添加元素比較低效，首先要先找到插入位置的節(jié)點，再修改前后節(jié)點的指針，時間復(fù)雜度為O(n)。
刪除元素
作為雙端隊列，刪除元素也有兩種方式，一種是隊列首刪除元素，一種是隊列尾刪除元素。
作為List，又要支持中間刪除元素，所以刪除元素一個有三個方法，分別如下。
// 刪除首節(jié)點
private E unlinkFirst(Node<E> f) {
// 首節(jié)點的元素值
final E element = f.item;
// 首節(jié)點的next指針
final Node<E> next = f.next;
// 添加首節(jié)點的內(nèi)容，協(xié)助GC
f.item = null;
f.next = null; // help GC
// 把首節(jié)點的next作為新的首節(jié)點
first = next;
// 如果只有一個元素，刪除了，把last也置為空
// 否則把next的前置指針置為空
if (next == null)
last = null;
else
next.prev = null;
// 元素個數(shù)減1
size--;
// 修改次數(shù)加1
modCount++;
// 返回刪除的元素
return element;
}
// 刪除尾節(jié)點
private E unlinkLast(Node<E> l) {
// 尾節(jié)點的元素值
final E element = l.item;
// 尾節(jié)點的前置指針
final Node<E> prev = l.prev;
// 清空尾節(jié)點的內(nèi)容，協(xié)助GC
l.item = null;
l.prev = null; // help GC
// 讓前置節(jié)點成為新的尾節(jié)點
last = prev;
// 如果只有一個元素，刪除了把first置為空
// 否則把前置節(jié)點的next置為空
if (prev == null)
first = null;
else
prev.next = null;
// 元素個數(shù)減1
size--;
// 修改次數(shù)加1
modCount++;
// 返回刪除的元素
return element;
}
// 刪除指定節(jié)點x
E unlink(Node<E> x) {
// x的元素值
final E element = x.item;
// x的前置節(jié)點
final Node<E> next = x.next;
// x的后置節(jié)點
final Node<E> prev = x.prev;
// 如果前置節(jié)點為空
// 說明是首節(jié)點，讓first指向x的后置節(jié)點
// 否則修改前置節(jié)點的next為x的后置節(jié)點
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
// 如果后置節(jié)點為空
// 說明是尾節(jié)點，讓last指向x的前置節(jié)點
// 否則修改后置節(jié)點的prev為x的前置節(jié)點
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
// 清空x的元素值，協(xié)助GC
x.item = null;
// 元素個數(shù)減1
size--;
// 修改次數(shù)加1
modCount++;
// 返回刪除的元素
return element;
}
// remove的時候如果沒有元素拋出異常
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
// remove的時候如果沒有元素拋出異常
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
// poll的時候如果沒有元素返回null
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
// poll的時候如果沒有元素返回null
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
// 刪除中間節(jié)點
public E remove(int index) {
// 檢查是否越界
checkElementIndex(index);
// 刪除指定index位置的節(jié)點
return unlink(node(index));
}刪除元素的三種方法都是典型的雙鏈表刪除元素的方法，大致流程如下圖所示。
在隊列首尾刪除元素很高效，時間復(fù)雜度為O(1)。
在中間刪除元素比較低效，首先要找到刪除位置的節(jié)點，再修改前后指針，時間復(fù)雜度為O(n)。
棧
前面我們說了，LinkedList是雙端隊列，還記得雙端隊列可以作為棧使用嗎？
/**
* 利用LinkedList來模擬棧
* 棧的特點：先進后出
*/
public class Test {
private LinkedList<String> linkList = new LinkedList<String>();
// 壓棧
public void push(String str){
linkList.addFirst(str);
}
// 出棧
public String pop(){
return linkList.removeFirst();
}
// 查看
public String peek(){
return linkList.peek();
}
// 判斷是否為空
public boolean isEmpty(){
return linkList.isEmpty();
}
}
class Test1 {
public static void main(String[] args) {
// 測試棧
Test test = new Test();
test.push("我是第1個進去的");
test.push("我是第2個進去的");
test.push("我是第3個進去的");
test.push("我是第4個進去的");
test.push("我是第5個進去的");
// 取出
while (!test.isEmpty()){
String pop = test.pop();
System.out.println(pop);
}
// 打印結(jié)果
/*我是第5個進去的
我是第4個進去的
我是第3個進去的
我是第2個進去的
我是第1個進去的*/
}
}棧的特性是LIFO(Last In First Out)，所以作為棧使用也很簡單，添加刪除元素都只操作隊列首節(jié)點即可。
總結(jié)
（1）LinkedList是一個以雙鏈表實現(xiàn)的List，因此不存在容量不足的問題，所以沒有擴容的方法。
（2）LinkedList還是一個雙端隊列，具有隊列、雙端隊列、棧的特性。
（3）LinkedList在隊列首尾添加、刪除元素非常高效，時間復(fù)雜度為O(1)。
（4）LinkedList在中間添加、刪除元素比較低效，時間復(fù)雜度為O(n)。
（5）LinkedList不支持隨機訪問，所以訪問非隊列首尾的元素比較低效。
（6）LinkedList在功能上等于ArrayList + ArrayDeque。
（7）LinkedList是非線程安全的。
（8）LinkedList能存儲null值。
經(jīng)典面試題
談?wù)凙rrayList和LinkedList的區(qū)別。
可以分兩部分答：一個是數(shù)組與鏈表底層實現(xiàn)的不同，另一個是答ArrayList和LinkedList的實現(xiàn)細(xì)節(jié)。
- ArrayList的底層是數(shù)組，LinkedList的底層是雙向鏈表。
- 數(shù)組擁有O(1)的查詢效率，可以通過下標(biāo)直接定位元素；鏈表在查詢元素的時候只能通過遍歷的方式查詢，效率比數(shù)組低。
- 數(shù)組增刪元素的效率比較低，通常要伴隨拷貝數(shù)組的操作；鏈表增刪元素的效率很高，只需要調(diào)整對應(yīng)位置的指針即可。
以上是數(shù)組和鏈表的通俗對比，在日常的使用中，兩者都能很好地在自己的適用場景發(fā)揮作用。
我們常常用ArrayList代替數(shù)組，因為封裝了許多易用的api，而且它內(nèi)部實現(xiàn)了自動擴容機制，由于它內(nèi)部維護了一個當(dāng)前容量的指針size，直接往ArrayList中添加元素的時間復(fù)雜度是O(1)的，使用非常方便。而LinkedList常常被用作Queue隊列的實現(xiàn)類，由于底層是雙向鏈表，能夠輕松地提供先入先出的操作。
到此這篇關(guān)于Java集合之LinkedList源碼解析的文章就介紹到這了,更多相關(guān)LinkedList源碼解析內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
springboot2.1.7去除json返回字段中為null的字段
這篇文章主要介紹了springboot2.1.7去除json返回字段中為null的字段，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12
Java基礎(chǔ)學(xué)習(xí)之IO流應(yīng)用案例詳解
這篇文章主要為大家詳細(xì)介紹了Java?IO流的三個應(yīng)用案例：點名器、集合到文件和文件到集合，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以了解一下2022-09-09
Spring Boot自動引入依賴的版本信息可以在`spring-boot-starter-parent`和`spring-boot-dependencies`的pom文件中找到,如果需要修改依賴版本,可以在項目pom文件中添加覆蓋配置項并刷新依賴即可2025-01-01
Java中的使用及連接Redis數(shù)據(jù)庫(附源碼)
這篇文章主要介紹了Java中的使用及連接Redis數(shù)據(jù)庫(附源碼)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09
XXL-JOB是一個分布式任務(wù)調(diào)度平臺,用于解決分布式系統(tǒng)中的任務(wù)調(diào)度和管理問題,文章詳細(xì)介紹了XXL-JOB的架構(gòu),包括調(diào)度中心、執(zhí)行器和Web管理控制臺,并提供了使用步驟,包括下載、配置、啟動和創(chuàng)建執(zhí)行器和任務(wù),感興趣的朋友一起看看吧2025-01-01
這篇文章主要介紹了Java編譯時類型與運行時類型，文章以父類BaseClass和子類SubClass為例展開對主題的探討，具有一的?參考價值，需要的小伙伴可以參考一下2022-03-03
MyBatis-Plus與Druid結(jié)合Dynamic-datasource實現(xiàn)多數(shù)據(jù)源操作數(shù)據(jù)庫的示例
Dynamic-DataSource 可以和絕大多是連接層插件搭配使用,比如:mybatis,mybatis-plus,hibernate等，本文就來介紹一下MyBatis-Plus與Druid結(jié)合Dynamic-datasource實現(xiàn)多數(shù)據(jù)源操作數(shù)據(jù)庫的示例，感興趣的可以了解一下2023-10-10
這篇文章主要介紹了詳解Spring配置及事務(wù)的使用，文中附含詳細(xì)的示例代碼說明，有需要的朋友可以借鑒參考下，希望能夠有所幫助2021-09-09
Java快速實現(xiàn)PDF轉(zhuǎn)圖片功能實例代碼
PDFBox是一個開源Java類庫,用于讀取和創(chuàng)建PDF文檔,它支持文本提取、表單處理、文檔加密解密、合并分割、內(nèi)容覆蓋追加、文檔打印和轉(zhuǎn)換等功能,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下2024-09-09
解決Spring Security中AuthenticationEntryPoint不生效相關(guān)問題
這篇文章主要介紹了解決Spring Security中AuthenticationEntryPoint不生效相關(guān)問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-12-12