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