集合框架——LinkedList集合源碼分析

来源:https://www.cnblogs.com/zhanghuaze/archive/2022/10/01/16747081.html
-Advertisement-
Play Games

總結： LinkedList繼承自List，具備有序性 LinkedList繼承自Deque，具備鏈表關聯性 LinkedList集合進行增刪改查操作底層實際是操作Node節點的前後鏈接關係 LinkedList進行增刪操作時，僅需要操作節點的前後鏈接關係，因此效率較ArrayList高 Linke ...


目錄

總結：

  1. LinkedList繼承自List，具備有序性
  2. LinkedList繼承自Deque，具備鏈表關聯性
  3. LinkedList集合進行增刪改查操作底層實際是操作Node節點的前後鏈接關係
  4. LinkedList進行增刪操作時，僅需要操作節點的前後鏈接關係，因此效率較ArrayList高
  5. LinkedList進行查找操作時，必須從頭或者從尾進行查找，因此較底層依靠數組進行存儲的ArrayList查找效率低

示例代碼

public class LinkedList01 {
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList(); //執行第1步
        linkedList.add(1); //執行第2步
        linkedList.add(2); //執行第3步
        linkedList.add(3); //執行第4步
        linkedList.add(1 , new Intger(8)); //執行第8步
        linkedList.add(5); 
        linkedList.remove(); //執行第5步
        linkedList.remove(2); //執行第6步
        linkedList.remove(new Integer(3)); //執行第7步
        System.out.println(linkedList);
    }
}

底層代碼

第1步（初始化集合）

//LinkedList類預設構造器
public LinkedList() {}
transient int size = 0;  //集合存放對象個數
transient Node<E> first;  //集合中第一個節點
transient Node<E> last;  //集合中最後一個節點
...
//AbstractSequentialList類預設構造器
protected AbstractSequentialList() {}
...
//AbstractList類預設構造器
protected AbstractList() {}
protected transient int modCount = 0;
...
//AbstractCollection類預設構造器
protected AbstractCollection() {}
...
//Object類預設構造器
public Object() {}

結果：還沒有存放對象，屬於空集合

第2步（往集合中添加一個元素）

public boolean add(E e) {  //e = 1
        linkLast(e); 
        return true;
}
...
void linkLast(E e) {
        final Node<E> l = last;//l = null
        final Node<E> newNode = new Node<>(l, e, null);//創建新的節點，當前節點的prev和next屬性均為null，將存入集合的對象賦值給item
        last = newNode;//LinkedList集合的last屬性指向新節點
        if (l == null)//此時i=null，條件成立
            first = newNode;//LinkedList集合的first屬性指向新節點
        else
            l.next = newNode;
        size++;//LinkedList集合的容量自加1
        modCount++;//LinkedList集合修改次數自加1
}
......
//Node是LinkedList類的內部類
private static class Node<E> {
        E item;  //LinkedLIst實際存放的對象
        Node<E> next;  //當前節點的下一個節點
        Node<E> prev; //當前節點的前一個節點

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
}

結果：集合中存放1個元素，LinkedList類中first與last屬性相同，Node類中prev與next屬性為null

第3步（往集合中添加第二個元素）

public boolean add(E e) {  //e = 2
        linkLast(e); 
        return true;
}
...
void linkLast(E e) {
        final Node<E> l = last;//l = 1，表示上一個節點
        final Node<E> newNode = new Node<>(l, e, null);//創建新的節點，節點的prev屬性指向上一個節點，item屬性存放當前對象
        last = newNode;//LinkedList集合的last屬性指向新節點
        if (l == null)//此時i！=null，條件不成立
            first = newNode;
        else
            l.next = newNode;//上一個節點的next屬性指向當前節點，即新創建的節點
        size++;//LinkedList集合的容量自加1
        modCount++;//LinkedList集合修改次數自加1
}

結果：

第4步（往集合中添加第三個元素）

public boolean add(E e) {  //e = 3
        linkLast(e); 
        return true;
}
...
void linkLast(E e) {
        final Node<E> l = last;//l = 2，表示上一個節點
        final Node<E> newNode = new Node<>(l, e, null);//創建新的節點，節點的prev屬性指向上一個節點，
item屬性存放當前對象
        last = newNode;//LinkedList集合的last屬性指向新節點
        if (l == null)//此時i！=null，條件不成立
            first = newNode;
        else
            l.next = newNode;//上一個節點的next屬性指向當前節點，即新創建的節點
        size++;//LinkedList集合的容量自加1
        modCount++;//LinkedList集合修改次數自加1
}

結果：

LinkedList添加元素流程示意圖

第5步（刪除集合中第一個元素）

public E remove() {
        return 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; //將集合中第一個節點的item 屬性賦值給element
        final Node<E> next = f.next; //將集合中第一個節點的next屬性賦值給next
        f.item = null;
        f.next = null; // help GC
        first = next; //將原集合中的第二個節點賦給集合的first屬性
        if (next == null)
            last = null;
        else
            next.prev = null;//將原集合中的第二個節點的prev屬性賦值為null
        size--; //集合元素個數自減1
        modCount++; //集合修改次數自加1
        return element; //返回被刪除的節點item值
}

第6步（根據索引來刪除集合中的元素）

public E remove(int index) { //index = 2
        checkElementIndex(index); //1.嵌套執行下邊兩個方法①和②，確定索引正確後繼續往下執行
        return unlink(node(index)); //2.執行方法③與④
}
...
//方法①
private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
...
//方法②
private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
}
...
//方法③
Node<E> node(int index) { //index = 2, size = 4
        // assert isElementIndex(index);
        if (index < (size >> 1)) { //index < size/2時
            Node<E> x = first; //x記錄首個節點
            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;
        }
}
...
//方法④
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; //此時該節點中的屬性item、prev、next均為null
        size--; //集合元素個數自減1
        modCount++; //集合修改次數自加1
        return element; //返回被刪除節點中的內容
}

第7步（根據對象內容來刪除集合中的元素）

//本方法可以用來刪除集合中對象和null
public boolean remove(Object o) { o = new Integer(3)
        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); //調用方法與第6步中流程一致
                    return true;
                }
            }
        }
        return false;
}

第8步（根據索引位置往集合中添加元素）

public void add(int index, E element) { //index=1, element = new Integer(8)
        checkPositionIndex(index); //檢查索引沒有問題

        if (index == size) //如果索引與集合大小相等
            linkLast(element);
        else
            linkBefore(element, node(index)); //node(index)方法找到該索引位置的節點，然後採用linkBefore方法在其節點前鏈接入新的節點
}
...
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++;
}
...
void linkBefore(E e, Node<E> succ) { //e = new Integer(8)待鏈接入的節點，succ為原index位置的節點
        // 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++;
}

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

-Advertisement-
Play Games
更多相關文章
  • 使用 Python 處理 Json 數據
    一、引言：什麼是 JSON JSON (Java Script Object Notation) 是一種很常用的數據格式，它常常用在 web 應用程式中。它可以表示結構化的數據。 下麵是常見的 JSON 文件結構 { "name": "Kamishiro Rize", "age": "22", "o ...
  • 常見的垃圾回收機制
    如何工作 在某些 Java 虛擬機中，堆的實現截然不同：它更像一個傳送帶，每分配一個新對象，它就向前移動一格。 這意味著對象存儲空間的分配速度特別快。Java 的"堆指針"只是簡單地移動到尚未分配的區域，所以它的效率與 C++ 在棧上分配空間的效率相當 垃圾回收器工作時，一邊回收記憶體，一邊使堆中的對 ...
  • 對c++的一些思考（一）
    Java基礎之運算符 1.1 運算符介紹 1.1.1 運算符介紹 運算符是一種特殊的符號，用以表示數據的運算、賦值和比較等，運算符可分為： 1）算術運算符 2）賦值運算符 3）關係運算符 [比較運算符] 4）邏輯運算符 5）位運算符 [需要二進位] 6）三元運算符 1.2 算術運算符 1.2.1 介 ...
  • python-數據描述與分析(1)
    數據描述與分析 在進行數據分析之前，我們需要做的事情是對數據有初步的瞭解，這個瞭解就涉及對行業的瞭解和對數據本身的敏感程度，通俗來說就是對數據的分佈有大概的理解，此時我們需要工具進行數據的描述，觀測數據的形狀等；而後才是對數據進行建模分析，挖掘數據中隱藏的位置信息。目前在數據描述和簡單分析方面做的比 ...
  • 學習筆記——Django項目中的請求與響應
    2022-10-01 ALLOWED_HOSTS "ALLOWED_HOSTS"的含義： 它是指允許放在“ALLOWED_HOSTS”的主機進行訪問後端 “ALLOWED_HOSTS”的說明： 它一般預設是“127.0.0.1”，如果添加上其他的主機的話，其他主機也可訪問此項目的view，但是此時， ...
  • 學習筆記——Django項目中的結果集、分頁
    2022-10-01 結果集的含義： 結果集就是在查詢過程中，返回的一個列表的集合。 常見的結果集在一些函數中查詢會返回，具體包括的函數有： filter、exclude、order_by 結果集的兩大特性： （1）惰性 指的是查詢時，如果不用則在mysql日誌中不會有查詢記錄。反之，如果使用（一般 ...
  • Java之POI導出Excel(二)：多個sheet
    相信在大部分的web項目中都會有導出導入Excel的需求，之前我也寫過一篇導出單個sheet工作表的文章，沒看過的小伙伴可以去看哈，鏈接也給大家放出來了：導出單個sheet 但是在我們日常的工作中，需求往往沒這麼簡單，可能需要將數據按類型分類導出或者數據量過大，需要分多張表導出等等。遇到類似的需求該 ...
  • Java之POI導出Excel(一)：單sheet
    相信在大部分的web項目中都會有導出導入Excel的需求，今天我們就來看看如何用Java代碼去實現 用POI導出Excel表格。 一、pom引用 pom文件中，添加以下依賴 查看代碼 <!--Excel工具--> <dependency> <groupId>org.apache.poi</group ...
一周排行
    -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.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類