快捷導(dǎo)航

Java數(shù)據(jù)結(jié)構(gòu)之鏈表的概念及結(jié)構(gòu)

更新時(shí)間：2023年04月03日 16:11:33 作者：徐徐同學(xué)

這篇文章主要介紹了數(shù)據(jù)鏈表的概念及結(jié)構(gòu)，鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。想進(jìn)一步了解的同學(xué)，可以參考閱讀本文

1、鏈表的概念

概念：鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的

1、鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成。

2、結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)(malloc)生成。

3、每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域（詳見(jiàn)1.2 節(jié)點(diǎn)部分）。

4、相比于線性表順序結(jié)構(gòu)，鏈表操作復(fù)雜。但是由于不需按順序存儲(chǔ)，鏈表在插入的時(shí)候可以達(dá)到O(1)的復(fù)雜度，比順序表快得多；但是查找一個(gè)節(jié)點(diǎn)或者訪問(wèn)特定編號(hào)的節(jié)點(diǎn)則需要O(n)的時(shí)間，而順序表只需O(1)

2、結(jié)點(diǎn)

鏈表由一個(gè)個(gè)結(jié)點(diǎn)構(gòu)成，每個(gè)結(jié)點(diǎn)采用結(jié)構(gòu)體的形式。結(jié)構(gòu)體內(nèi)前面的變量按照需要給予，最后一個(gè)變量是這個(gè)結(jié)構(gòu)體類型的指針，用來(lái)存放下一節(jié)點(diǎn)的首地址‘

鏈表結(jié)點(diǎn)分為兩個(gè)域
數(shù)據(jù)域：存放各種實(shí)際的數(shù)據(jù)
指針域：存放下一結(jié)點(diǎn)的地址

（圖為帶哨兵位頭結(jié)點(diǎn)的鏈表）

3、鏈表的使用場(chǎng)景

線性表在 需要經(jīng)常插入或刪除數(shù)據(jù)元素 的情況下適合采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

因?yàn)閷?duì)于鏈表來(lái)說(shuō)，插入或刪除數(shù)據(jù)只需要?jiǎng)?chuàng)建一個(gè)結(jié)點(diǎn)、輸入數(shù)據(jù)、修改指針把該結(jié)點(diǎn)連接到鏈表中的某一位置即可；而對(duì)于順序表，插入一個(gè)數(shù)據(jù)可能需要搬移其他數(shù)據(jù)，復(fù)雜度高。

4、鏈表分類和常用結(jié)構(gòu)

雖然組合起來(lái)一共有8種鏈表可以選擇，但是實(shí)際中最常用的主要還是 無(wú)頭單向非循環(huán) 鏈表和 帶頭雙向循環(huán) 鏈表。

1、無(wú)頭單向非循環(huán)鏈表：俗稱 “單鏈表”。結(jié)構(gòu)簡(jiǎn)單，一般不會(huì)單獨(dú)用來(lái)存儲(chǔ)數(shù)據(jù)。實(shí)際上更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)（如哈希桶、圖的鄰接表、棧的鏈?zhǔn)浇Y(jié)構(gòu)等）

2、帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用來(lái)單獨(dú)存儲(chǔ)數(shù)據(jù)。實(shí)際使用的鏈表，大多都是帶頭雙向循環(huán)鏈表。雖然結(jié)構(gòu)最復(fù)雜，但是這種結(jié)構(gòu)會(huì)帶來(lái)很多優(yōu)勢(shì)。

5、與順序表的比較

鏈表： 鏈表是通過(guò)結(jié)點(diǎn)把離散的數(shù)據(jù)鏈接成一個(gè)表，通過(guò)對(duì)結(jié)點(diǎn)的插入、刪除操作從而實(shí)現(xiàn)對(duì)數(shù)據(jù)的存取。

順序表： 順序表是通過(guò)開(kāi)辟一段連續(xù)的內(nèi)存（直接使用數(shù)組或者 malloc后realloc擴(kuò)容）來(lái)存儲(chǔ)數(shù)據(jù)。

但是由于 realloc 擴(kuò)容分為原地?cái)U(kuò)容和異地?cái)U(kuò)容，前者代價(jià)較低，而后者擴(kuò)容時(shí)不僅需要拷貝數(shù)據(jù)，還要釋放舊空間。再者，擴(kuò)容時(shí)一般會(huì)擴(kuò)到原來(lái)容量的2倍，擴(kuò)容次數(shù)多了就容易造成空間的浪費(fèi)

順序表的每個(gè)成員對(duì)應(yīng)鏈表的結(jié)點(diǎn)；成員和結(jié)點(diǎn)的數(shù)據(jù)類型可以是標(biāo)準(zhǔn)的c類型或者是用戶自定義的結(jié)構(gòu)體類型。

比較對(duì)象	順序表	鏈表
存儲(chǔ)空間	連續(xù)	不連續(xù)
插入或刪除數(shù)據(jù)	可能要搬移數(shù)據(jù)，復(fù)雜度O(n)	只需修改指針
push	動(dòng)態(tài)順序表：空間不夠了需要擴(kuò)容	沒(méi)有“容量”的概念，push時(shí)直接malloc新的結(jié)點(diǎn)
應(yīng)用	需要頻繁訪問(wèn)	需要頻繁插入、刪除數(shù)據(jù)

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之鏈表的概念及結(jié)構(gòu)的文章就介紹到這了,更多相關(guān)Java 鏈表的概念結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: