詳解Java LinkedList

来源:https://www.cnblogs.com/KRDecad3/archive/2023/11/02/17803102.html
-Advertisement-
Play Games

LinkedList簡介 LinkedList是List介面的實現類，基於雙向鏈表實現，繼承自AbstractSequentialList類，同時也實現了Cloneable、Serializable介面。此外還實現了Queue和Deque介面，可以作為隊列或雙端隊列使用。 LinkedList的插入 ...


LinkedList簡介

LinkedList是List介面的實現類，基於雙向鏈表實現，繼承自AbstractSequentialList類，同時也實現了Cloneable、Serializable介面。此外還實現了Queue和Deque介面，可以作為隊列或雙端隊列使用。

image

LinkedList的插入刪除時間複雜度：

  • 在頭部或尾部插入刪除元素，只需要修改頭節點或尾節點的指針即可完成，時間複雜度為O(1)；
  • 在其他位置插入刪除元素，需要遍歷到指定位置，再修改指定節點的指針，平均要移動n/2個位置，時間複雜度為O(n)。

LinkedList沒有像ArrayList有RandomAccess介面的標記，因為LinkedList基於鏈表實現，鏈表節點之間的記憶體地址不連續，只能通過指針來定位，因此無法實現快速隨機訪問。

常用方法

public class LinkedListTest {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
		//添加元素
        linkedList.add(2);
        linkedList.addFirst(1);
        linkedList.add(3);
        linkedList.add(4);
        linkedList.addLast(5);
		//獲取元素
        System.out.println(linkedList.get(1));
        System.out.println(linkedList.getFirst());
        System.out.println(linkedList.getLast());
		//創建雙端隊列
        Deque<String> deque = new LinkedList<>();
		//元素入隊
        deque.offer("a");
        deque.offer("b");
        deque.offer("c");
		//獲取隊頭元素，但不刪除隊頭元素
        System.out.println(deque.peek());
		//元素出隊
        String a = deque.poll();
        System.out.println(a);
    }
}

LinkedList核心源碼分析

下麵以JDK17的LinkedList代碼進行分析。

類屬性

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
	//LinkedList大小
    transient int size = 0;

    //首節點
    transient Node<E> first;

    //尾節點
    transient Node<E> last;
}

LinkedList中的節點由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;
	}
}

構造方法

//創建一個空鏈表對象
public LinkedList() {
}

//傳入一個集合，將集合中的元素存入鏈表
public LinkedList(Collection<? extends E> c) {
	this();
	addAll(c);
}

添加元素

因為LinkedList基於雙向鏈表實現，並且實現了List和Queue介面，所有有多種添加元素的方法。
add方法

//在鏈表尾部添加元素
public boolean add(E e) {
	linkLast(e);
	return true;
}

//尾插法
void linkLast(E e) {
	final Node<E> l = last;
	final Node<E> newNode = new Node<>(l, e, null);
	last = newNode;
	if (l == null)
		first = newNode;
	else
		l.next = newNode;
	size++;
	modCount++;
}

//在指定下標出添加元素
public void add(int index, E element) {
	//檢查下標是否越界
	checkPositionIndex(index);
	//如果下標是最後位置則使用尾插法
	if (index == size)
		linkLast(element);
	else
		linkBefore(element, node(index));
}

//在指定節點之前插入元素
void linkBefore(E e, Node<E> succ) {
	// assert succ != null;
	final Node<E> pred = succ.prev;
	final Node<E> newNode = new Node<>(pred, e, succ);
	succ.prev = newNode;
	if (pred == null)
		first = newNode;
	else
		pred.next = newNode;
	size++;
	modCount++;
}

//插入鏈表頭部
public void addFirst(E e) {
	linkFirst(e);
}
//頭插法
private void linkFirst(E e) {
	final Node<E> f = first;
	final Node<E> newNode = new Node<>(null, e, f);
	first = newNode;
	if (f == null)
		last = newNode;
	else
		f.prev = newNode;
	size++;
	modCount++;
}

//插入鏈表尾部
public void addLast(E e) {
	linkLast(e);
}

獲取元素

LinkedList提供了三個get方法獲取元素。

//獲取鏈表第一個元素
public E getFirst() {
	final Node<E> f = first;
	if (f == null)
		throw new NoSuchElementException();
	return f.item;
}

//獲取鏈表最後一個元素
public E getLast() {
	final Node<E> l = last;
	if (l == null)
		throw new NoSuchElementException();
	return l.item;
}

//根據下標獲取鏈表中的元素
public E get(int index) {
	//檢查下標是否越界
	checkElementIndex(index);
	//遍歷鏈表，返回查找到的節點值
	return node(index).item;
}

node方法就是用來遍歷鏈表的：

Node<E> node(int index) {
	// assert isElementIndex(index);
	//如果下標小於LinkedList的一半則從頭節點開始遍歷，否則從尾節點開始
	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;
	}
}

刪除元素

removeFirst方法，刪除鏈表頭節點

public E removeFirst() {
	final Node<E> f = first;
	if (f == null)
		throw new NoSuchElementException();
	return unlinkFirst(f);
}

private E unlinkFirst(Node<E> f) {
	// assert f == first && f != null;
	//保留待刪除節點的信息
	final E element = f.item;
	//記錄待刪除節點的後繼
	final Node<E> next = f.next;
	f.item = null;
	f.next = null; // help GC
	first = next;
	if (next == null)
		last = null;
	else
		next.prev = null;
	size--;
	modCount++;
	return element;
}

removeLast方法，刪除鏈表尾節點

public E removeLast() {
	final Node<E> l = last;
	if (l == null)
		throw new NoSuchElementException();
	return unlinkLast(l);
}

private E unlinkLast(Node<E> l) {
	// assert l == last && l != null;
	final E element = l.item;
	//記錄待刪除節點的前驅
	final Node<E> prev = l.prev;
	l.item = null;
	l.prev = null; // help GC
	last = prev;
	if (prev == null)
		first = null;
	else
		prev.next = null;
	size--;
	modCount++;
	return element;
}

public boolean remove(Object o) {
	if (o == null) {
		for (Node<E> x = first; x != null; x = x.next) {
			if (x.item == null) {
				unlink(x);
				return true;
			}
		}
	} else {
		for (Node<E> x = first; x != null; x = x.next) {
			if (o.equals(x.item)) {
				unlink(x);
				return true;
			}
		}
	}
	return false;
}

public E remove(int index) {
	checkElementIndex(index);
	return unlink(node(index));
}

//實際執行刪除節點的方法
E unlink(Node<E> x) {
	// assert x != null;
	//保留待刪除節點的信息，記錄前驅和後繼
	final E element = x.item;
	final Node<E> next = x.next;
	final Node<E> prev = x.prev;

	if (prev == null) {
		first = next;
	} else {
		prev.next = next;
		x.prev = null;
	}

	if (next == null) {
		last = prev;
	} else {
		next.prev = prev;
		x.next = null;
	}

	x.item = null;
	size--;
	modCount++;
	return element;
}

隊列操作

返回隊頭元素：

public E peek() {
	final Node<E> f = first;
	return (f == null) ? null : f.item;
}

隊頭元素出隊，調用了刪除鏈表頭節點的方法：

public E poll() {
	final Node<E> f = first;
	return (f == null) ? null : unlinkFirst(f);
}

入隊，調用了add方法：

public boolean offer(E e) {
	return add(e);
}

此外還有一些雙端隊列的方法，如offerFirst、offerLast、peekFirst、peekLast、pollFirst、pollLast等。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 常用集合線程安全分析
    ArrayList在多線程情況下，不安全 具體代碼 package com.shaonian.juc.list_thread_secure; import java.util.ArrayList; import java.util.List; import java.util.UUID; /** * ...
  • JUC併發編程學習筆記（四）8鎖現象
    8鎖現象 八鎖->就是關於鎖的八個問題 鎖是什麼，如何判斷鎖的是誰 對象、class模板 深刻理解鎖 鎖的東西無外乎就兩樣：1、同步方法的調用者，2、Class模板。 同一個鎖中，只有當前線程資源釋放後才會被下一個線程所接手。 同步方法的調用者是兩個不同的實例時，互不相關。 靜態同步方法(stati ...
  • JUC併發編程學習筆記（三）生產者和消費者問題
    生產者和消費者問題 synchronized版-> wait/notify juc版->Lock 面試：單例模式、排序演算法、生產者和消費者、死鎖 生產者和消費者問題 Synchronized版 package org.example.pc; public class A { public stati ...
  • JUC併發編程學習筆記（二）Lock鎖(重點)
    Lock鎖(重點) 傳統的synchronized 傳統的解決多線程併發導致的一些問題我們會使用synchronized關鍵字來解決，synchronized的本質就是隊列、鎖。 Lock的實現類有：可重覆鎖（最常用）、讀鎖、寫鎖 在創建可重覆鎖時，可傳入boolean類型值來決定該鎖是公平鎖（先來 ...
  • Educational Codeforces Round 134 (Div.2) D 題解
    進程和線程 進程 一個程式，如QQ.exe，是程式的集合 一個進程往往可以包含多個線程，至少包含一個 java預設有兩個線程，GC垃圾回收線程和Main線程 線程：一個進程中的各個功能 java無法真正的開啟線程，因為java是運行在虛擬機上的，所以只能通過C++,通過native本地方法調用C++ ...
  • 編譯原理
    Java 程式員或者是 Java 工程師在逐漸成長為高級開發的時候，他 看問題的方式寫工作的方式都有自己的一套方式。每個人的工作效率不一樣，但是都要達到同一個目的。對於開發 任務而言，測試通過是最低的要求。Java 的集成開發環境十分優秀，從西方美國的 Eclipse 到歐洲的 Idea，程式員開發 ...
  • 大數據
    寫程式軟體處理用戶量和數據量。用戶量一大，併發量線程安全問題就會出現。軟體一開始是 使用 C/S 的應用架構模式。客戶端和伺服器端通過互聯網相互訪問。Windows 的客戶端軟體通過 C++編寫出來，不同的操作系統支持的客戶端軟體編寫語言不一樣。B/S 架構模式現在很受大眾的歡迎，一臺電腦的應用可 ...
  • Spring Boot 實現 PDF 水印，實戰來了！
    來源：cnblogs.com/hushaojun/p/16285486.html 簡介 PDF（Portable Document Format，攜帶型文檔格式）是一種流行的文件格式，它可以在多個操作系統和應用程式中進行查看和列印。在某些情況下，我們需要對 PDF 文件添加水印，以使其更具有辨識度或 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類