詳解Java線性結構中的鏈表
一. 鏈表簡介
1. 概念
線性表可以說是一種最基礎最簡單的數(shù)據(jù)結構,它表示的是一種線性結構,比較常見的線性結構包括數(shù)組和鏈表等。
所謂的鏈表,顧名思義,就是鏈式的線性表,即鏈表也是一種線性表。與數(shù)組不同的是,鏈表采用的是鏈式存儲,這種鏈式結構是非連續(xù)、非順序的內(nèi)存空間。鏈表中的每一個獨立的元素被稱為結點,故鏈表由一系列的結點組成。
其中鏈式存儲的含義如下:
假如我們需要存放一堆物品,但沒有足夠大的空間將所有的物品一次性放下,此時該如何既放下所有的物品,又能簡單的找到所有的物品位置呢?我們可以嘗試采用如下解決方案:存放物品時,每放置一件物品就在該物品上貼一個小紙條,標明下一件物品放在哪里。這樣,我們只需要記住第一件物品的位置,從第一件物品上的小紙條,就可以找到第二件物品,再根據(jù)第二件物品紙條的內(nèi)容就找到第三件物品。按照這個方法依次類推,我們便可以找到所有的物品,這就是所謂的鏈式存儲。
2. 表示方式
鏈表中的每個結點都由兩部分組成:數(shù)據(jù)域、指針域。數(shù)據(jù)域用來存放當前結點需要存儲的數(shù)據(jù)內(nèi)容,指針域用于存放當前結點的下一個結點的地址。如下圖所示:
圖1-鏈表的結構示意圖
上圖所示的節(jié)點細節(jié)如下:
- 首個結點中next1存放的是第二結點的內(nèi)存地址,因此用一個箭頭指向第二個結點,就可以表示兩個結點之間的關系。
- 最后一個結點的后面不再有其他結點,因此最后結點的next5指針域中沒有地址內(nèi)容,編程中可以用null表示。
3. 特點
通過上文所述,壹哥就可以給大家總結出鏈表的主要特點:
(1). 從內(nèi)存結構來看,鏈表的內(nèi)存結構是不連續(xù)的內(nèi)存空間,是將一組零散的內(nèi)存塊串聯(lián)起來,從而進行數(shù)據(jù)存儲的數(shù)據(jù)結構;
(2). 鏈表由一系列結點組成,每個結點包括兩個部分,一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域,另一個是存儲下一個結點地址的指針域。鏈表中數(shù)據(jù)元素的邏輯順序就是通過地址指針實現(xiàn)的;
(3). 鏈表和數(shù)組相比,內(nèi)存空間消耗更大,因為每個存儲數(shù)據(jù)的結點都需要額外的空間存儲地址指針。
二. 鏈表分類
在工作實踐中,開發(fā)者接觸到的鏈表主要有三種:單向鏈表、雙向鏈表、循環(huán)鏈表。下面壹哥給大家逐一進行介紹一下。
1. 單向鏈表
單向鏈表的每一個結點包含兩部分,一部分是存放數(shù)據(jù)的變量data,另一部分是指向下一個結點的指針next。 單鏈表只能單向讀取,其結構如下所示:
圖2-單向鏈表結構示意圖
我們以Java為例,給出單向鏈表的結構定義:
class Node{ Object value; Node next; }
2. 雙向鏈表
雙向鏈表,表示鏈表結點由三部分組成:數(shù)據(jù)域、下一結點指針域、前一結點指針域。 在雙向鏈表結構中,既可以從首個結點出發(fā),根據(jù)下一結點指針域依次找到所有結點;同理,也可以從指定的某個結點,根據(jù)結點中的前一結點指針地址,向前依次得到前面的結點。具體地,雙向鏈表的結構示意圖如下所示:
圖3-雙向鏈表結構示意圖
如上圖所示:
- 第1個結點作為整個鏈表的首結點,該結點的prev1指針內(nèi)容為null,表示沒有前一個結點。
- 第5個結點作為整個鏈表的最后結點,next5指針內(nèi)容為null,表示后續(xù)沒有下一個結點。
- 除此之外,中間三個結點,next指針和prev指針分別指向下一個結點和前一個結點,可以實現(xiàn)雙向查找。
使用Java進行雙向鏈表的結點結構定義如下:
class Node{ Object value; Node next; Node prev; }
3. 循環(huán)鏈表
如果,我們將鏈表的最后結點的next指針域做下修改,由原來的指向null修改為指向第1個結點,則整個鏈表就變成了一個環(huán)路。以單向鏈表進行操作,如下圖所示:
圖4-單向循環(huán)鏈表示意圖
如上圖,每個結點有數(shù)據(jù)域和指針域兩個部分,這種循環(huán)鏈表被稱之為單向循環(huán)鏈表。在計算機領域中,單向循環(huán)鏈表又稱約瑟夫環(huán)(Josephu Loop),這一點僅做了解即可。當然,雙向鏈表也可以調(diào)整為循環(huán)的鏈表,被稱之為雙向循環(huán)鏈表,如下圖所示:
圖5-雙向循環(huán)鏈表示意圖
三. 存儲原理
數(shù)組在內(nèi)存中的存儲方式是順序存儲(連續(xù)存儲),鏈表在內(nèi)存中的存儲方式則是隨機存儲,如下圖所示:
圖6-鏈表的內(nèi)存存儲示意圖
鏈表的每一個結點分布在內(nèi)存的不同位置,依靠next指針關聯(lián)起來。這樣可以靈活有效地利用零散的碎片空間。鏈表的第一個結點被稱為頭結點,沒有任何結點的next指針指向它,它的前置結點為空null。頭結點用來記錄鏈表的基地址。有了它,就可以遍歷得到整條鏈表的數(shù)據(jù)。鏈表的最后一個結點被稱為尾結點,它的next指向為空null。
四. 鏈表常見操作
本篇文章內(nèi)容,我們以單向鏈表為例,介紹鏈表的常見操作,主要包括:查找結點、更新結點、插入結點和刪除結點等操作。
1. 查找結點
在查找元素時,鏈表只能從頭結點開始向后,一個結點一個結點逐一查找,如下圖所示:
時間復雜度分析,分兩種情況:
- 查找頭結點:頭結點是鏈表的第一個結點,直接就能得到結果,因此查找頭結點時間復雜度是O(1)。
- 查找非頭結點:如果查找非頭結點,則需要從頭結點向后依次查找,知道整個鏈表的末尾,因此查找非頭結點的其他結點時,時間復雜度是O(n),最壞情況下時間復雜度也是O(n)。
2. 更新結點
更新結點操作需要兩個步驟:
- 找到要更新的結點;
- 將舊數(shù)據(jù)替換成新數(shù)據(jù)。
如下圖所示:
圖8-單向鏈表更新結點數(shù)據(jù)操作示意圖
與查找結點操作時間復雜度情況類似,更新時間復雜度分兩種情況:
- 更新頭結點:單向鏈表更新頭結點的時間復雜度是O(1);
- 更新非頭結點:更新其他結點的最壞情況時間復雜度是O(n)。
3. 插入結點
3.1 尾部插入
尾部插入即把最后一個結點的next指針指向新插入的結點即可,如下圖所示:
圖9-單向鏈表尾部插入結點示意圖
時間復雜度分析:如上圖所示,若尾部插入結點,則需要從頭開始遍歷,因此單向鏈表添加尾結點的時間復雜度是O(n)。
3.2 頭部插入
頭部插入新結點需要兩個步驟:
(1). 把新結點的next指針指向原先的頭結點;
(2). 把新結點變?yōu)殒湵淼念^結點。
如下圖所示:
圖10-單鏈表頭部插入結點示意圖
時間復雜度分析:因為直接將新節(jié)點的指針域指向頭結點即可完成操作,因此添加頭結點的時間復雜度是O(1)。
3.3 中間插入
在鏈表的中間位置插入結點同樣需要三步:
(1). 從頭結點開始向后查找,找到要插入的結點的位置;
(2). 新結點的next指針指向插入位置的結點;
(3). 插入位置前置結點的next指針指向新結點;
示意圖如下:
圖11-單向鏈表中間位置插入結點
時間復雜度分析:若執(zhí)行插入結點操作,首先需要從頭結點向后查找,找到要插入的位置。很明顯,與鏈表的規(guī)模有關,因此中間插入結點操作的時間復雜度是O(n)。
4. 刪除結點
4.1 尾部刪除
若希望刪除鏈表的最后一個結點,只需要將倒數(shù)第二個結點的指針域指向null即可,如下圖所示:
圖12-單向鏈表尾部刪除結點示意圖
時間復雜度分析:因為要從頭開始遍歷,所以單向鏈表刪除尾結點的時間復雜度是O(n)。
4.2 頭部刪除
頭部刪除與頭部插入操作類似,只需要把鏈表的頭結點設為原先頭結點的next指針即可如圖:
圖13-單向鏈表頭部刪除結點示意圖
時間復雜度分析:刪除頭結點的時間復雜度也是O(1)。
4.3 中間刪除
中間位置刪除結點操作類似于中間插入操作,需要三步:
(1). 從頭結點開始向后,找到要刪除結點的位置;
(2). 找到刪除結點的前一個結點和后一個結點;
(3). 將要刪除結點的前置結點的next指針,指向要刪除元素的下一個結點;
如下所示:
圖14-單向鏈表中間刪除結點示意圖
時間復雜度分析:因為需要從頭結點開始進行查找,因此時間復雜度與鏈表的規(guī)模有關,故單向鏈表刪除中間位置結點的時間復雜度是O(n)。
五. 結語
本篇文章,我們一起學習了鏈表的概念,認識了單向鏈表、雙向鏈表、循環(huán)鏈表等不同的鏈表類型。并以單向鏈表為例,分析了鏈表中的結點炒作及對應的時間復雜度分析,不知道你現(xiàn)在對鏈表了解了嗎?
以上就是詳解Java線性結構中的鏈表的詳細內(nèi)容,更多關于Java 鏈表的資料請關注腳本之家其它相關文章!
相關文章
java中VO和DTO之間的轉(zhuǎn)換實現(xiàn)
本文主要介紹了java中VO和DTO之間的轉(zhuǎn)換實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2022-05-05spring boot中的條件裝配bean的實現(xiàn)
這篇文章主要介紹了spring boot中的條件裝配bean的實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2019-12-12Java ThreadLocal原理解析以及應用場景分析案例詳解
這篇文章主要介紹了Java ThreadLocal原理解析以及應用場景分析案例詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-09-09SpringSessionRedis配置及發(fā)現(xiàn)的問題講解
今天小編就為大家分享一篇關于SpringSessionRedis配置及發(fā)現(xiàn)的問題講解,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧2019-03-03Mybatis-Plus中的MetaObjectHandler組件的使用
MetaObjectHandler是Mybatis-Plus中一個實用組件,專門用于自動處理實體對象中的特定字段,如創(chuàng)建時間、更新時間、創(chuàng)建人和修改人等,該接口允許開發(fā)者在不修改業(yè)務代碼的情況下,實現(xiàn)自動填充功能,極大地簡化了代碼的復雜性,感興趣的可以了解一下2024-10-10