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

来源: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
更多相關文章
  • 一、 編碼規約 1.1 標簽 (1)【強制】PHP 程式可以使用或來界定 PHP 代碼,在 HTML 頁面中嵌入純變數時,可以使用這樣的形式,不可使用其他的標簽變種。 正例: <?php /** * 編碼規約 * Created by PhpStorm. * User: [email protected] ...
  • 在SpringBoot中配置 Druid 數據源及密碼加密的方法 前文集成 MyBatis Plus,實現了一組增刪改查介面。在啟動服務時,從控制臺中可以看出 Spring Boot 預設使用 Hikari 作為資料庫連接池,Hikari性能很優秀。在國內使用較多的連接池還屬阿裡開源的 Druid, ...
  • 前言 之前也瞭解到過一致性哈希演算法,但是沒有用go實現過,剛好最近看GeeCache,動手實現下一致性哈希演算法 正文: 我們先來想下一致性哈希演算法的數據結構含有哪些內容: 1.map 用來存儲虛擬節點對應的真實節點,是一個映射表 2.hash 哈希函數 3.key 哈希環,存儲所有虛擬節點 4.re ...
  • 前言 最近在學習C++的類如何構造,在W3Cschool上看到關於拷貝構造函數的一個例子,記錄一下。 案例背景 這篇文章大致是構造瞭如下的一個Line類: class Line{ public: int getLength(void); Line(int len); // 簡單構造函數 Line(c ...
  • JPA是Java Persistence API的簡稱,中文名Java持久層API,是JDK 5.0註解或XML描述對象-關係表的映射關係,並將運行期的實體對象持久化到資料庫中。 ...
  • 用Python來繪製自己的個人足跡地圖, 精確到市級別。 首先我們需要安裝以下Python的第三方模塊: echarts-china-cities-pypkg==0.0.9 echarts-china-provinces-pypkg==0.0.3 pyecharts==1.6.2 PyYAML==5 ...
  • 問題背景 大家看看這個頁面,有沒有發現什麼問題? 主頁:http://www.javastack.cn/ 是的,頁面 CSS 樣式全丟失了,導致頁面混亂。。 這個頁面是我人為刪除了樣式(為了演示),真正出現問題是另外一個頁面,最近棧長髮現有個頁面時不時就會出現樣式錯亂的問題,很詭異!! 於是這篇就記 ...
  • JProfiler 是一個功能強大的工具,您可以使用它以動態方式分析基於 Java 的應用程式,並使您能夠分析它們以優化性能。當您配置文件時,您需要最強大的工具。同時,您不想花時間學習如何使用該工具。JProfiler 就是這樣:既簡單又強大。 Mac版詳情:JProfiler 13 for Mac ...
一周排行
    -Advertisement-
    Play Games
  • 使用原因: 在我們服務端調用第三方介面時,如:支付寶,微信支付,我們服務端需要模擬http請求並加上一些自己的邏輯響應給前端最終達到我們想要的效果 1.使用WebClient 引用命名空間 using System.Net; using System.Collections.Specialized; ...
  • WPF 實現帶蒙版的 MessageBox 消息提示框 WPF 實現帶蒙版的 MessageBox 消息提示框 作者:WPFDevelopersOrg 原文鏈接: https://github.com/WPFDevelopersOrg/WPFDevelopers.Minimal 框架使用大於等於.N ...
  • 一、JSON(JavaScript Object Notation)的簡介: ① JSON和XML類似,主要用於存儲和傳輸文本信息,但是和XML相比,JSON更小、更快、更易解析、更易編寫與閱讀。 ② C、Python、C++、Java、PHP、Go等編程語言都支持JSON。 二、JSON語法規則: ...
  • 1.避免Scoped模式註冊的服務變成Singleton模式 當提供一個生命周期模式為Singleton的服務實例時,如果發現該服務中還依賴生命周期模式為Scoped的服務實例(Scoped服務實例將被一個Singleton服務實例所引用),那麼這個被依賴的Scoped服務實例最終會成為一個Sing ...
  • 索引時資料庫提高數據查詢處理性能的一個非常關鍵的技術,索引的使用可以對性能產生上百倍甚至上千倍的影響。接下來,會介紹索引的基本原理、概念,並深入學習資料庫中所使用的索引結構和存儲方式,以及如何管理、維護索引等。 1.索引的基本概念 索引時用來快速查詢表記錄的一種存儲結構,一般使用索引有一下兩個方面: ...
  • django2 路由控制器 Route路由,是一種映射關係。路由是把客戶端請求的url路徑和用戶請求的應用程式,這裡意指django裡面的視圖進行綁定映射的一種關係。 請求路徑和視圖函數不是一一對應的關係 在django中所有的路由最終都被保存到一個叫urlpatterns的文件里,並且該文件必須在 ...
  • 1、我們的目標是獲取微博某博主的全部圖片、視頻 2、拿到網址後 我們先觀察 打開F12 隨著下滑我們發現載入出來了一個叫mymblog的東西,展開響應發現需要的東西就在裡面 3、重點來了!!! 通過觀察發現第二頁比第一頁多了參數since_id 而第二頁的since_id參數剛好在上一頁中能獲取到, ...
  • 一、實現原理 在Servlet3協議規範中,包含在JAR文件/META-INFO/resources/路徑下的資源可以直接訪問。 二、舉例說明 如下圖所示,是我新建的一個Spring Boot Starter項目:zimug-minitor-threadpool,用於實現可配置、可觀測的線程池。其中 ...
  • 精華筆記: static final常量:應用率高 必須聲明同時初始化 由類名打點來訪問,不能被改變 建議:常量所有字母都大寫,多個單詞用_分隔 編譯器在編譯時會將常量直接替換為具體的數,效率高 何時用:數據永遠不變,並且經常使用 抽象方法: 由abstract修飾 只有方法的定義,沒有具體的實現( ...
  • Python有一個for...else語法,它的寫法如下 for i in range(0,100): if i == 3: break else: print("Not found") 該語句表示:若for迴圈遍歷完畢,則執行else部分的語句。也就是說上述代碼不會有任何輸出,而下述代碼會輸出“N ...