Debug LinkedList

来源:https://www.cnblogs.com/noneplus/archive/2020/07/26/13381336.html
-Advertisement-
Play Games

Debug LinkedList源碼 前置知識 LinkedList基於鏈表,LinkedList的Node節點定義 成員變數 //鏈表中元素的數量 transient int size = 0; /** * 鏈表的頭節點:用於遍歷 */ transient Node<E> first; /** * ...


目錄

Debug LinkedList源碼

前置知識

  • LinkedList基於鏈表,LinkedList的Node節點定義

image-20200719145701402

  • 成員變數

     	//鏈表中元素的數量
        transient int size = 0;
    
        /**
         * 鏈表的頭節點:用於遍歷
         */
        transient Node<E> first;
    
        /**
    	* 鏈表的尾節點:用於添加元素
         */
        transient Node<E> last;
    

2.1 Debug 分析第一個元素是如何進入鏈表的

編寫測試代碼,打上斷點:

image-20200726161013956

進入方法內部:

  • add方法預設添加到鏈表的尾部
  • 該方法等同於addLast(區別就是add方法需要返回一個true,而addLast沒有任何返回值)

image-20200726161221902

image-20200726161546055

進入linkLast方法內部:

	/**
     * 當前方法執行完後,若添加的節點為第一個節點,鏈表的last和first都指向新節點
     */
    void linkLast(E e) {
        //獲取到鏈表的最後一個元素
        final Node<E> l = last;
        //創建一個節點,前一個節點為當前鏈表的last,後一個節點為空
        final Node<E> newNode = new Node<>(l, e, null);
        //修改last為新添加的節點
        last = newNode;
        //若鏈表為空,first節點為新添加的節點,否則添加前最後一個節點的next指向新節點
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
            
            //鏈表長度加一
        size++;
        	//鏈表修改次數加1
        modCount++;
    }
    
//=================================================================
    
    Node帶三個參數的構造函數:
    Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }

2.2 Debug 分析如何通過下標插入指定位置add(index,e)

編寫測試用例:

image-20200726163053756

進入方法內部:

public void add(int index, E element) {
		//檢查下標是否合法:大於等於0小於等於size【return index >= 0 && index <= size;】
        checkPositionIndex(index);

		//若等於size,相當於在鏈表尾部添加節點
        if (index == size)
            linkLast(element);
        else
        //linkBefore中的Before指的是傳入索引元素前
            linkBefore(element, node(index));
    }

進入node(index)方法:返回索引為index的元素

Node<E> node(int index) {
        // assert isElementIndex(index);

	   //查找元素的思路是遍歷一半,先折半分區,然後若在小於折半的區域就從first開始往後遍歷,反之從last往前遍歷
	   //右移一位相當於除以2
        if (index < (size >> 1)) {
        //獲取到first節點
            Node<E> x = first;
            //從first遍歷到index的位置
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
        
        //獲取到next的節點
            Node<E> x = last;
            //從last往前遍歷到index的位置
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

回到linkBefore方法:

void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        //獲取index節點的上一個節點
        final Node<E> pred = succ.prev;
        //創建新節點,下一個節點指向index節點,上一個節點指向index節點的上一個節點
        final Node<E> newNode = new Node<>(pred, e, succ);
        //index節點的上一個節點指向變為指向新節點
        succ.prev = newNode;
        //**若index節點的頭節點為空,相當於從頭部插入節點,直接將新節點賦給first節點
        if (pred == null)
            first = newNode;
        else
        //index的上一個節點的下一個節點指向改為新節點
            pred.next = newNode;
            
            //節點長度+1
        size++;
            //鏈表修改次數+1
        modCount++;
    }

2.3 Debug 分析如何通過下標獲取指定元素

編寫測試代碼,打上斷點:

image-20200726174022431

進入get方法內部:

public E get(int index) {
		//檢查下標範圍
        checkElementIndex(index);
        //遍歷一半,返回節點的值
        return node(index).item;
    }

LinkedList支持的查詢除了通過下標獲取外,還支持getLast和getFirst

image-20200726174631658

get(0)和getFirst時間複雜度有區別嗎?

理論上來說,getFirst和getLast都是直接獲取到節點,時間複雜度為O(1),而通過get(index)方法查詢節點,都會折半後遍歷一半的元素,時間複雜度為O(n)。但實際情況下,for迴圈遍歷的第一個元素就100%是頭節點或尾節點,不會進入之後的迴圈,實際運行的也是O(1)。

2.4 Debug 分析如何通過下標刪除元素

打上斷點:

image-20200726175453328

進入方法內部:

public E remove(int index) {
		//檢查下標範圍
        checkElementIndex(index);
        //node(index)獲取需要刪除的節點,折半遍歷
        return unlink(node(index));
    }

進入unlink方法內部:

刪除中間元素的過程圖:

image-20200726181403239

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節點
            first = next;
        } else {
        //若刪除的節點為中間節點,將當前節點的上一個節點的下一個節點指向變為當前節點的下一個節點(step1)
            prev.next = next;
            //當前節點的上一個節點指向置為null(step2)
            x.prev = null;
        }

        if (next == null) {
        //若刪除的節點為尾節點,將當前節點的上一個節點賦給last
            last = prev;
        } else {
        //若刪除的節點為中間節點,將當前節點的下一個節點的上一個節點指向變為當前節點的上一個節點(step3)
            next.prev = prev;
            //當前節點的下一個節點指向置為null(step4)
            x.next = null;
        }

		//節點元素內容置為空
        x.item = null;
        //鏈表長度-1
        size--;
        //鏈表修改次數+1
        modCount++;
        //返回刪除節點內容		
        return element;
    }

2.5 Debug 分析如何通過對象刪除節點(內容)

image-20200726181609167

public boolean remove(Object o) {
		//若節點為null,從first往下遍歷(說明LinkedList是允許為空值的,並且允許多個)
        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);
                    return true;
                }
            }
        }
        return false;
    }

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

-Advertisement-
Play Games
更多相關文章
  • 一、Tomcat的安裝及簡單使用 在網上找到你需要安裝的Tomcat版本,解壓到你需要安裝的目錄就可以了 目錄介紹: bin 專門用來存放 Tomcat 伺服器的可執行程式 conf 專門用來存放 Tocmat 伺服器的配置文件 lib 專門用來存放 Tomcat 伺服器的 jar 包 logs 專 ...
  • Java是啥 新手程式員通常會走入一個誤區,就是認為學習了一門語言,就可以稱為是某某語言工程師了。但事實上真的是這樣嗎?其實並非如此。 今天我們就來聊一聊,Java 開發工程師到底開發的是什麼東西。準確點來說,Java後端到底在做什麼? 基礎 大家都知道 Java 是一門後端語言,後端指的就是服務端 ...
  • 最近有很多小伙伴來問我,Java小白如何入門,如何安排學習路線,每一步應該怎麼走比較好。原本我以為之前的幾篇文章已經可以解決大家的問題了,其實不然,因為我之前寫的文章都是站在Java後端的全局上進行思考和總結的,忽略了很多小白們的感受,而很多朋友都需要更加基礎,更加詳細的學習路線。 所以,今天我們重 ...
  • 秋招總結 寫在最前 我寫過很多篇秋招總結,這篇文章應該是最後一篇總結,當然也是最完整,最詳細的一篇總結。秋招是我人生中一段寶貴的經歷,不僅是我研究生生涯交出的一份答卷,也是未來職業生涯的開端。僅以此文,獻給自己,以及各位在求職路上的,或者是已經經歷過校招的朋友們。不忘初心,方得始終。 前言 在下本是 ...
  • 一 JDBC簡介 Java DataBase Connectivity Java語言連接資料庫 官方(Sun公司)定義的一套操作所有關係型資料庫的規則(介面) 各個資料庫廠商去實現這套介面 提供資料庫驅動JAR包 可以使用這套介面(JDBC)編程 真正執行的代碼是驅動JAR包中的實現類 二 JDBC ...
  • 題目描述:這裡 思路: 一、部分分演算法 對於的數據,用暴力解決即可,時間複雜度 對於另外的數據(所有木棍長度相等),考慮用組合數學,答案為 二、正解 我們考慮對整個序列進行桶排序。 我們設每個數出現的次數為。 對於所有≥的數,加上比它小的所有數出現的次數,並加上這個數至這個數中所有數出現的個數。 特 ...
  • 區別維度: 1. 可變性 a. String用final修飾,不可變 b. Stringbuilder和StringBuffer均繼承抽象父類AbstractStringBuilder,其中也是用char[]數組儲存字元串,但無final修飾 2. 線程安全性:源碼中StringBuilder和St ...
  • 雖然Python的強項在人工智慧,數據處理方面,但是對於日常簡單的應用,Python也提供了非常友好的支持(如:Tkinter),本文主要一個簡單的畫圖小軟體,簡述Python在GUI(圖形用戶界面)方面的應用,僅供學習分享使用,如有不足之處,還請指正。 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 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 ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...