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

来源: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
  • 在本篇教程中,我們學習瞭如何使用 Taurus.MVC WebMVC 框架創建一個簡單的頁面。 我們創建了一個控制器並編寫了一個用於呈現頁面的方法,然後創建了對應的視圖,並最終成功運行了應用程式。 在下一篇教程中,我們將繼續探索 Taurus.MVC WebMVC 框架的更多功能和用法。 ...
  • 一:背景 1. 講故事 很多.NET開發者在學習高級調試的時候,使用sos的命令輸出會發現這裡也看不懂那裡也看不懂,比如截圖中的這位朋友。 .NET高級調試屬於一個偏冷門的領域,國內可觀測的資料比較少,所以很多東西需要你自己去探究源代碼,然後用各種調試工具去驗證,相關源代碼如下: coreclr: ...
  • 我一直都以為c中除以2的n次方可以使用右移n位代替,然而在實際調試中發現並不都是這樣的。是在計算餘數是發現了異常 被除數:114325068 右移15計算結果:3488 除法取整計算結果:3489 右移操作計算餘數:33772 除法取整計算餘數:1005 顯然:這是不一樣的。 移位操作是一條cpu指 ...
  • 在上一篇文章中,我們介紹了ReentrantLock類的一些基本用法,今天我們重點來介紹一下ReentrantLock其它的常用方法,以便對ReentrantLock類的使用有更深入的理解。 ...
  • Excelize 是 Go 語言編寫的用於操作電子錶格辦公文檔的開源基礎庫,2024年2月26日,社區正式發佈了 2.8.1 版本,該版本包含了多項新增功能、錯誤修複和相容性提升優化。 ...
  • 雲採用框架(Cloud Adoption Framework,簡稱CAF)為企業上雲提供策略和技術的指導原則和最佳實踐,幫助企業上好雲、用好雲、管好雲,併成功實現業務目標。本雲採用框架是基於服務大量企業客戶的經驗總結,將企業雲採用分為四個階段,並詳細探討企業應在每個階段採取的業務和技術策略;同時,還 ...
  • 與TXT文本文件,PDF文件更加專業也更適合傳輸,常用於正式報告、簡歷、合同等場合。項目中如果有使用Java將TXT文本文件轉為PDF文件的需求,可以查看本文中介紹的免費實現方法。 免費Java PDF庫 本文介紹的方法需要用到Free Spire.PDF for Java,該免費庫支持多種操作、轉 ...
  • 指針和引用 當我們需要在程式中傳遞變數的地址時,可以使用指針或引用。它們都可以用來間接訪問變數,但它們之間有一些重要的區別。 指針是一個變數,它存儲另一個變數的地址。通過指針,我們可以訪問存儲在該地址中的變數。指針可以被重新分配,可以指向不同的變數,也可以為NULL。指針使用*運算符來訪問存儲在地址 ...
  • 即使再小再簡單的需求,作為研發開發完畢之後,我們可以直接上線麽?其實很多時候事故往往就是由於“不以為意”發生的。事故的發生往往也遵循“墨菲定律”,這就要求我們更要敬畏線上,再小的需求點都需要經過嚴格的測試驗證才能上線。 ...
  • 這裡給大家分享我在網上總結出來的一些知識,希望對大家有所幫助 一、是什麼 許可權是對特定資源的訪問許可,所謂許可權控制,也就是確保用戶只能訪問到被分配的資源 而前端許可權歸根結底是請求的發起權,請求的發起可能有下麵兩種形式觸發 頁面載入觸發 頁面上的按鈕點擊觸發 總的來說,所有的請求發起都觸發自前端路由或 ...