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

来源: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
  • C#自增運算符詳解：++i與i++的區別及應用場景
    概述：在C#中，++i和i++都是自增運算符，其中++i先增加值再返回，而i++先返回值再增加。應用場景根據需求選擇，首碼適合先增後用，尾碼適合先用後增。詳細示例提供清晰的代碼演示這兩者的操作時機和實際應用。 在C#中，++i 和 i++ 都是自增運算符，但它們在操作上有細微的差異，主要體現在操作的 ...
  • Taurus.MVC 性能壓力測試（ap 壓測 和 linux 下wrk 壓測）：.NET 版本
    上次發佈了：Taurus.MVC 性能壓力測試（ap 壓測 和 linux 下wrk 壓測）：.NET Core 版本，今天計劃準備壓測一下 .NET 版本，來測試並記錄一下 Taurus.MVC 框架在 .NET 版本的性能，以便後續持續優化改進。 為了方便對比，本文章的電腦環境和測試思路，儘量和... ...
  • 一文讀懂.NET WebAPI中FromRoute、FromQuery、FromBody的關鍵角色與用法
    .NET WebAPI作為一種構建RESTful服務的強大工具，為開發者提供了便捷的方式來定義、處理HTTP請求並返迴響應。在設計API介面時，正確地接收和解析客戶端發送的數據至關重要。.NET WebAPI提供了一系列特性，如[FromRoute]、[FromQuery]和[FromBody]，用 ...
  • WPF/C#實現圖像濾鏡優化方案：打造炫目視覺體驗！
    原因：我之所以想做這個項目，是因為在之前查找關於C#/WPF相關資料時，我發現講解圖像濾鏡的資源非常稀缺。此外，我註意到許多現有的開源庫主要基於CPU進行圖像渲染。這種方式在處理大量圖像時，會導致CPU的渲染負擔過重。因此，我將在下文中介紹如何通過GPU渲染來有效實現圖像的各種濾鏡效果。 生成的效果 ...
  • Bogus 實戰：使用 Bogus 和 EFCore 生成模擬數據和種子數據【完整教程】
    引言 上一章我們介紹了在xUnit單元測試中用xUnit.DependencyInject來使用依賴註入，上一章我們的Sample.Repository倉儲層有一個批量註入的介面沒有做單元測試，今天用這個示例來演示一下如何用Bogus創建模擬數據 ，和 EFCore 的種子數據生成 Bogus 的優 ...
  • WPF隨筆收錄-實時繪製心率曲線
    一、前言 在自己的項目中，涉及到實時心率曲線的繪製，項目上的曲線繪製，一般很難找到能直接用的第三方庫，而且有些還是定製化的功能，所以還是自己繪製比較方便。很多人一聽到自己畫就害怕，感覺很難，今天就分享一個完整的實時心率數據繪製心率曲線圖的例子；之前的博客也分享給DrawingVisual繪製曲線的方 ...
  • wpf程式修改啟動入口註意事項
    如果你在自定義的 Main 方法中直接使用 App 類並啟動應用程式，但發現 App.xaml 中定義的資源沒有被正確載入，那麼問題可能在於如何正確配置 App.xaml 與你的 App 類的交互。 確保 App.xaml 文件中的 x:Class 屬性正確指向你的 App 類。這樣，當你創建 Ap ...
  • 記一次 .NET某爐膛鍋爐檢測系統 崩潰分析
    一：背景 1. 講故事 上個月有個朋友在微信上找到我，說他們的軟體在客戶那邊隔幾天就要崩潰一次，一直都沒有找到原因，讓我幫忙看下怎麼回事，確實工控類的軟體環境複雜難搞，朋友手上有一個崩潰的dump，剛好丟給我來分析一下。 二：WinDbg分析 1. 程式為什麼會崩潰 windbg 有一個厲害之處在於 ...
  • 一個.NET內置依賴註入的小型強化版
    前言 .NET生態中有許多依賴註入容器。在大多數情況下，微軟提供的內置容器在易用性和性能方面都非常優秀。外加ASP.NET Core預設使用內置容器，使用很方便。 但是筆者在使用中一直有一個頭疼的問題：服務工廠無法提供請求的服務類型相關的信息。這在一般情況下並沒有影響，但是內置容器支持註冊開放泛型服 ...
  • WPF隨筆收錄-DataGrid固定右側列
    一、前言 在項目開發過程中，DataGrid是經常使用到的一個數據展示控制項，而通常表格的最後一列是作為操作列存在，比如會有編輯、刪除等功能按鈕。但WPF的原始DataGrid中，預設只支持固定左側列，這跟大家習慣性操作列放最後不符，今天就來介紹一種簡單的方式實現固定右側列。（這裡的實現方式參考的大佬 ...
所有分類