一起探秘，不可不知雙向鏈表底層原理

来源:https://www.cnblogs.com/jiagooushi/archive/2022/08/05/16554293.html
-Advertisement-
Play Games

雙向鏈表與數據結構 引言 在上小節中 我們分析了ArrayList的底層實現， 知道了ArrayList底層是基於數組實現的，因此具有查找修改快而插入、刪除慢的特點 本章我們介紹的LinkedList是List介面的另一種實現 它的底層是基於雙向鏈表實現的 因此它具有插入、刪除快而查找修改慢的特點 ...


雙向鏈表與數據結構

引言
在上小節中
我們分析了ArrayList的底層實現，
知道了ArrayList底層是基於數組實現的，因此具有查找修改快而插入、刪除慢的特點
本章我們介紹的LinkedList是List介面的另一種實現
它的底層是基於雙向鏈表實現的
因此它具有插入、刪除快而查找修改慢的特點

什麼是LinkedList

LinkList是一個雙向鏈表（雙鏈表）；它是鏈表的一種，也是最常見的數據結構，其內部數據呈線性排列，屬於線性表結構.

file

它的每個數據結點中都有兩個指針，分別指向直接後繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和後繼結點，所以是雙向鏈表.

LinkList特點：

file

鏈表: 優勢：不是連續的記憶體，隨便插入（前、中間、尾部） 插入O(1) 劣勢：查詢慢O(N)

線程不安全的，允許為null，允許重覆元素

藍色表示；可隨意插入、刪除

查詢迴圈迴圈鏈表

總結

雙鏈表的節點既有指向下一個節節點的指針，也有指向上一個結點的指針（雙向讀）

所謂指針，就是指向其他節點的一個對象的引用（說白了就是定義了兩個成員變數）

雙向鏈表線程不安全的，允許為null，允許重覆元素

查詢O(n)

插入刪除O(1)

1.2 雙向鏈表繼承關係

file
LinkedList 是一個繼承於AbstractSequentialList的雙向鏈表。
LinkedList 實現 List 介面，能對它進行隊列操作。
LinkedList 實現 Deque 介面，能將LinkedList當作雙端隊列（double ended queue）使用。
LinkedList 實現了Cloneable介面，即覆蓋了函數clone()，能克隆。
LinkedList 實現java.io.Serializable介面，這意味著LinkedList支持序列化，能通過序列化去傳輸。

1.3 雙向鏈表源碼深度剖析

案例代碼

com.llist.LList

package com.llist;

import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedList;

public class LList {

    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<String>();
        linkedList.add("100");//尾插,等價於 linkedList.addLast()
        linkedList.add("200");
        linkedList.add("300");
       //*******中間插入linkedList..add(3,"700")*************
        linkedList.add("400");
        linkedList.add("500");
        linkedList.add("600");
        System.out.println(linkedList);
        linkedList.add(3,"700");//中間插入
        System.out.println(linkedList);
        //*******修改***************************************
        linkedList.set(3,"700000000");
        System.out.println(linkedList);
        //*******查詢***************************************
        System.out.println(linkedList.getFirst());//頭查
        System.out.println(linkedList.getLast());//尾查
//        for(int s=0;s<linkedList.size();s++){
//            System.out.println(linkedList.get(s));//隨機插
//        }

        //*******移除***************************************
        LinkedList<String> linkedListRemove = new LinkedList<String>();
        linkedListRemove.add("100");
        linkedListRemove.add("200");
        linkedListRemove.add("300");
        linkedListRemove.remove(1);//指定移除
        linkedListRemove.removeAll(linkedList);//也調用上面的unlink方法；LinkedList.ListItr.remove
    }

}

1.3.1 鏈表成員變數與內部類

我們先來定義幾個叫法，後面會用到它

file

    transient int size = 0;//元素個數
    transient Node<E> first;//頭結點引用（查詢時獲取）
    transient Node<E> last;//尾節點引用（查詢時獲取）



    private static class Node<E> { //鏈表節點元素，封裝了真實數據，同時加入了前後指針
        E item;//元素，這是放入的真實數據
        Node<E> next;//下一個節點，指針也是Node類型
        Node<E> prev;//上一個節點
      
				//構造器，前、值、後，很清晰
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;//新元素
            this.next = next;//下個節點
            this.prev = prev;//上個節點
        }
    }

1.3.2 雙向鏈表構造器

無參構造器: 沒有做任何事情

  public LinkedList() { //無參構造器
  }

有參構造器：傳入外部集合的構造器

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

秘密就藏在addAll上（重點，畫圖展示）

    public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index); //邊界判斷

        Object[] a = c.toArray();  //不管你傳啥類型，統一轉成數組
        int numNew = a.length;  //需要新插入的個數
        if (numNew == 0)
            return false;
      
				//兩個指針，這倆表示你要插入點的前後兩個節點。我們稱之為前置node和後置node
      	//比如你的index=2 ：  【 000  1111（pred） （index）  2222（succ） 33333 …… 】
        Node<E> pred, succ; 
        if (index == size) { //下麵就要定位到這倆指針的位置
            succ = null; //如果指定的index和尾部相等，很顯然後置是沒有的
            pred = last; //前置就是最後一個元素last
        } else {
            succ = node(index);  //否則的話，後置就是當前index位置的node，這個方法下麵有詳細介紹先不管它
            pred = succ.prev;  //前置就是當前index位置的prev，很好理解
        }

        for (Object o : a) { //開始迴圈遍歷插入元素
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);  //定義個新節點，包裝當前元素
            if (pred == null)   //如果前置為空，註意什麼時候才為空？只有頭插或當前list沒有元素的時候
                first = newNode; //說明是第一次放入元素，將first指向當前元素，完工
            else
                pred.next = newNode;  //否則的話，前置node的後指針指向當前元素（接上了）
            pred = newNode; //讓前置指針後移，指向剛新建的node，為下一次迴圈做準備
        } //依次迴圈，往上接，接完後，pred就是最後一個插入的元素

      	//全部迴圈接完以後，再來處理新接鏈條的後指針
        if (succ == null) { //如果後置是nul的話，說明我們一直在尾部插入
            last = pred; //將last指向最後一個插入的元素即可，它就是尾巴
        } else {
            pred.next = succ;  //否則的話，最後一個插入的next指向原來插入前的後置
            succ.prev = pred; //後置的前指針指向最後插入的元素，這兩步是一對操作缺一不可
        } //到此為止，截斷的後半截鏈條也對接上了。

        size += numNew;  //最後不要忘記，元素數量增加
        modCount++;  //操作計數器增加
        return true;
    }

1.3.3 鏈表插入（重點）

1） 雙向鏈表尾插法

1、add(E e)，

2、addLast；

調用的方法都一樣（linkLast）

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); //創建一個新節點，註意其前驅節點為l
        last = newNode;//尾指針指向新節點
        if (l == null)//如果原來的尾巴節點為空，則表示鏈表為空，則將first節點也賦值為newNode
            first = newNode;
        else
            l.next = newNode; // 否則的話，將原尾巴節點的後指針指向新節點，構成雙向環
        size++;// 計數
        modCount++; //計數
    }

結論：預設add就是尾插法，追加到尾部

2）雙向鏈表中間插入

目標：將700插入到400的位置

插入前

file

插入後的

file

雙向鏈表中間插入add(int index, E element)

//自定義插入
 linkedList.add(3,"700");

源碼如下

    public void add(int index, E element) {
        checkPositionIndex(index);//越界檢查

        if (index == size)//如果index就是指向的尾部，自然調尾插即可
            linkLast(element);
        else
            linkBefore(element, node(index));//否則的話，找到index位置的node，插隊到它前面去
    }

		/**
     * 那它怎麼找的呢？看以下方法（畫圖展示）
     */
    Node<E> node(int index) {
        // 這裡有一個討巧的設計！很靈活的應用了我們的first和last

        if (index < (size >> 1)) { // index如果小於鏈表長度的1/2 （size右移1就是除以2）
            Node<E> x = first;
            for (int i = 0; i < index; i++) //從鏈表頭開始移動 index 次
                x = x.next; //依次往後指
            return x;  //迴圈完後，就找到了index位置的node，返回即可
        } else { //  否則，說明index在鏈表的後半截，我們從鏈表尾部倒著往前找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--) //一直迴圈，直到index位置
                x = x.prev;
            return x; //抓到後返回，完工！
        }
    }

	//畫圖展示
	void linkBefore(E e, Node<E> succ) { //找到之後，也就是這裡的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++;//個數加1
        modCount++;//修改次數加1 
    }

1.3.4 雙向鏈表修改方法

非常簡單！

找到包裝值的node，修改掉裡面的屬性即可

public E set(int index, E element) {
    checkElementIndex(index);//越界檢查
    Node<E> x = node(index);//通過鏈表索引找到node
    E oldVal = x.item;//獲取原始值
    x.item = element;//新值賦值
    return oldVal;//返回老值
}

1.3.5 雙向鏈表查詢方法

簡單！

get(int index)：按照下標獲取元素； 通用方法
getFirst()：獲取第一個元素； 特有方法，直接拿指針就是
getLast()：獲取最後一個元素； 特有方法，同樣直接拿指針

    public E get(int index) {
        checkElementIndex(index);//越界檢查
        return node(index).item;//找到原始數組對應index的node
    }

System.out.println(linkedList.getFirst());//頭查

System.out.println(linkedList.getLast());//尾查

1.3.6 雙向鏈表刪除方法

remove(E e)：移除指定元素； 通用方法

removeAll(Collection<?> c) 移除指定集合的元素; 也調用的unlink方法

兩步走：1找，2刪

    public boolean remove(Object o) {
        if (o == null) { //如果要移除null元素
            for (Node<E> x = first; x != null; x = x.next) {  //從fist順著鏈表往後找
                if (x.item == null) { //發現就幹掉
                    unlink(x); //重點！幹掉元素調用的其實是unlink方法
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {  //如果不是移除null的話，路子一個樣，無非就是==換成equals判斷
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 畫圖展示：將要移除的Node，比如【100】【200】【300】
     */
    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;//上個為空，說明當前要移除的就是頭節點，將fist指針指向後置，我被移除後它升級為頭了
        } else {
            prev.next = next;  //否則，前置的後指針指向後置
            x.prev = null; //當前節點的前指針切斷！
        }

        if (next == null) {  
            last = prev;//後置為空說明當前要移除的是尾節點，我被移除後，我的前置成為尾巴
        } else {
            next.prev = prev; //否則，後置的前指針指向前置節點
            x.next = null; //當前節點的後指針切斷！
        }  //到這裡前後指針就理清了，該斷的斷了，該接的接了

        x.item = null;// 把當前元素改成null，交給垃圾回收
        size--;//鏈表大小減一
        modCount++;//修改次數加一
        return element; //已刪除元素
    }

本文由傳智教育博學谷 - 狂野架構師教研團隊發佈
如果本文對您有幫助，歡迎關註和點贊；如果您有任何建議也可留言評論或私信，您的支持是我堅持創作的動力
轉載請註明出處！


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

-Advertisement-
Play Games
更多相關文章
  • PHP最全編碼規約
    一、 編碼規約 1.1 標簽 （1）【強制】PHP 程式可以使用或來界定 PHP 代碼，在 HTML 頁面中嵌入純變數時，可以使用這樣的形式，不可使用其他的標簽變種。 正例： <?php /** * 編碼規約 * Created by PhpStorm. * User: [email protected] ...
  • 配置 Druid 數據源及密碼加密-SpringBoot 2.7 實戰基礎
    在SpringBoot中配置 Druid 數據源及密碼加密的方法 前文集成 MyBatis Plus，實現了一組增刪改查介面。在啟動服務時，從控制臺中可以看出 Spring Boot 預設使用 Hikari 作為資料庫連接池，Hikari性能很優秀。在國內使用較多的連接池還屬阿裡開源的 Druid， ...
  • 【golang】分散式緩存 - 一致性哈希演算法
    前言 之前也瞭解到過一致性哈希演算法，但是沒有用go實現過，剛好最近看GeeCache，動手實現下一致性哈希演算法 正文: 我們先來想下一致性哈希演算法的數據結構含有哪些內容: 1.map 用來存儲虛擬節點對應的真實節點，是一個映射表 2.hash 哈希函數 3.key 哈希環，存儲所有虛擬節點 4.re ...
  • [c++]關於拷貝構造函數和析構函數執行次數的思考
    前言 最近在學習C++的類如何構造，在W3Cschool上看到關於拷貝構造函數的一個例子，記錄一下。 案例背景 這篇文章大致是構造瞭如下的一個Line類： class Line{ public: int getLength(void); Line(int len); // 簡單構造函數 Line(c ...
  • JPA作持久層操作
    JPA是Java Persistence API的簡稱，中文名Java持久層API，是JDK 5.0註解或XML描述對象－關係表的映射關係，並將運行期的實體對象持久化到資料庫中。 ...
  • Python製作炫酷的個人足跡地圖
    用Python來繪製自己的個人足跡地圖， 精確到市級別。 首先我們需要安裝以下Python的第三方模塊: echarts-china-cities-pypkg==0.0.9 echarts-china-provinces-pypkg==0.0.3 pyecharts==1.6.2 PyYAML==5 ...
  • Nginx 限流的天坑！！
    問題背景 大家看看這個頁面，有沒有發現什麼問題？ 主頁：http://www.javastack.cn/ 是的，頁面 CSS 樣式全丟失了，導致頁面混亂。。 這個頁面是我人為刪除了樣式（為了演示），真正出現問題是另外一個頁面，最近棧長髮現有個頁面時不時就會出現樣式錯亂的問題，很詭異！！ 於是這篇就記 ...
  • JProfiler最新版(Java開發分析工具)
    JProfiler 是一個功能強大的工具，您可以使用它以動態方式分析基於 Java 的應用程式，並使您能夠分析它們以優化性能。當您配置文件時，您需要最強大的工具。同時，您不想花時間學習如何使用該工具。JProfiler 就是這樣：既簡單又強大。 Mac版詳情：JProfiler 13 for Mac ...
一周排行
    -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.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類