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
  • Timer是什麼 Timer 是一種用於創建定期粒度行為的機制。 與標準的 .NET System.Threading.Timer 類相似,Orleans 的 Timer 允許在一段時間後執行特定的操作,或者在特定的時間間隔內重覆執行操作。 它在分散式系統中具有重要作用,特別是在處理需要周期性執行的 ...
  • 前言 相信很多做WPF開發的小伙伴都遇到過表格類的需求,雖然現有的Grid控制項也能實現,但是使用起來的體驗感並不好,比如要實現一個Excel中的表格效果,估計你能想到的第一個方法就是套Border控制項,用這種方法你需要控制每個Border的邊框,並且在一堆Bordr中找到Grid.Row,Grid. ...
  • .NET C#程式啟動閃退,目錄導致的問題 這是第2次踩這個坑了,很小的編程細節,容易忽略,所以寫個博客,分享給大家。 1.第一次坑:是windows 系統把程式運行成服務,找不到配置文件,原因是以服務運行它的工作目錄是在C:\Windows\System32 2.本次坑:WPF桌面程式通過註冊表設 ...
  • 在分散式系統中,數據的持久化是至關重要的一環。 Orleans 7 引入了強大的持久化功能,使得在分散式環境下管理數據變得更加輕鬆和可靠。 本文將介紹什麼是 Orleans 7 的持久化,如何設置它以及相應的代碼示例。 什麼是 Orleans 7 的持久化? Orleans 7 的持久化是指將 Or ...
  • 前言 .NET Feature Management 是一個用於管理應用程式功能的庫,它可以幫助開發人員在應用程式中輕鬆地添加、移除和管理功能。使用 Feature Management,開發人員可以根據不同用戶、環境或其他條件來動態地控制應用程式中的功能。這使得開發人員可以更靈活地管理應用程式的功 ...
  • 在 WPF 應用程式中,拖放操作是實現用戶交互的重要組成部分。通過拖放操作,用戶可以輕鬆地將數據從一個位置移動到另一個位置,或者將控制項從一個容器移動到另一個容器。然而,WPF 中預設的拖放操作可能並不是那麼好用。為瞭解決這個問題,我們可以自定義一個 Panel 來實現更簡單的拖拽操作。 自定義 Pa ...
  • 在實際使用中,由於涉及到不同編程語言之間互相調用,導致C++ 中的OpenCV與C#中的OpenCvSharp 圖像數據在不同編程語言之間難以有效傳遞。在本文中我們將結合OpenCvSharp源碼實現原理,探究兩種數據之間的通信方式。 ...
  • 一、前言 這是一篇搭建許可權管理系統的系列文章。 隨著網路的發展,信息安全對應任何企業來說都越發的重要,而本系列文章將和大家一起一步一步搭建一個全新的許可權管理系統。 說明:由於搭建一個全新的項目過於繁瑣,所有作者將挑選核心代碼和核心思路進行分享。 二、技術選擇 三、開始設計 1、自主搭建vue前端和. ...
  • Csharper中的表達式樹 這節課來瞭解一下表示式樹是什麼? 在C#中,表達式樹是一種數據結構,它可以表示一些代碼塊,如Lambda表達式或查詢表達式。表達式樹使你能夠查看和操作數據,就像你可以查看和操作代碼一樣。它們通常用於創建動態查詢和解析表達式。 一、認識表達式樹 為什麼要這樣說?它和委托有 ...
  • 在使用Django等框架來操作MySQL時,實際上底層還是通過Python來操作的,首先需要安裝一個驅動程式,在Python3中,驅動程式有多種選擇,比如有pymysql以及mysqlclient等。使用pip命令安裝mysqlclient失敗應如何解決? 安裝的python版本說明 機器同時安裝了 ...