快捷導(dǎo)航

LinkList的底層數(shù)據(jù)結(jié)構(gòu)及優(yōu)缺點(diǎn)詳解

更新時(shí)間：2025年11月21日 09:54:38 作者：IT小鳥(niǎo)鳥(niǎo)

鏈表由節(jié)點(diǎn)組成,每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)域和指針域,節(jié)點(diǎn)在內(nèi)存中非連續(xù)分布,通過(guò)指針鏈接形成邏輯上的線性關(guān)系,鏈表支持動(dòng)態(tài)大小、高效插入/刪除,但隨機(jī)訪問(wèn)效率低,且需要手動(dòng)管理指針

底層數(shù)據(jù)結(jié)構(gòu)

鏈表由一系列 節(jié)點(diǎn)（Node） 組成，每個(gè)節(jié)點(diǎn)包含兩部分：

數(shù)據(jù)域：存儲(chǔ)實(shí)際數(shù)據(jù)。
指針域：存儲(chǔ)指向下一個(gè)節(jié)點(diǎn)（單向鏈表）或前驅(qū)/后繼節(jié)點(diǎn)（雙向鏈表）的地址。
物理存儲(chǔ)：節(jié)點(diǎn)在內(nèi)存中 非連續(xù)分布，通過(guò)指針鏈接形成邏輯上的線性關(guān)系。
核心操作：通過(guò)指針的重新指向?qū)崿F(xiàn)插入/刪除，無(wú)需移動(dòng)其他元素。

優(yōu)點(diǎn)

1.動(dòng)態(tài)大小

無(wú)需預(yù)先分配固定內(nèi)存，可動(dòng)態(tài)擴(kuò)展或收縮，避免內(nèi)存浪費(fèi)。

2.高效插入/刪除

時(shí)間復(fù)雜度：O(1)（已知節(jié)點(diǎn)位置時(shí)，如頭/尾操作）。
僅需修改指針，無(wú)需移動(dòng)其他元素（與數(shù)組的 O(n) 對(duì)比明顯優(yōu)勢(shì)）。

3.靈活的存儲(chǔ)結(jié)構(gòu)

適用于頻繁修改的場(chǎng)景（如隊(duì)列、圖鄰接表）。
雙向鏈表支持反向遍歷，提升某些操作效率。

缺點(diǎn)

1.隨機(jī)訪問(wèn)低效

必須從頭節(jié)點(diǎn)遍歷，時(shí)間復(fù)雜度 O(n)，而數(shù)組通過(guò)索引訪問(wèn)為 O(1)。

2.額外內(nèi)存開(kāi)銷

每個(gè)節(jié)點(diǎn)需存儲(chǔ)指針，占用額外空間（尤其是雙向鏈表，每個(gè)節(jié)點(diǎn)多一個(gè)指針）。

3.緩存不友好

內(nèi)存非連續(xù)分布，導(dǎo)致 CPU 緩存命中率低，遍歷效率低于數(shù)組。

4.代碼復(fù)雜度

需要手動(dòng)管理指針，易出現(xiàn)內(nèi)存泄漏或指針錯(cuò)誤（如雙向鏈表的指針維護(hù)）。

不同鏈表類型的對(duì)比

類型	特點(diǎn)	適用場(chǎng)景
單向鏈表	每個(gè)節(jié)點(diǎn)僅指向下一個(gè)節(jié)點(diǎn)，內(nèi)存占用較少	簡(jiǎn)單插入/刪除（如棧、LRU緩存）
雙向鏈表	支持雙向遍歷，插入/刪除更靈活，但內(nèi)存占用更高	頻繁雙向操作（如雙向隊(duì)列）
循環(huán)鏈表	尾節(jié)點(diǎn)指向頭節(jié)點(diǎn)，形成環(huán)，適合周期性操作（如輪詢調(diào)度）	循環(huán)隊(duì)列、輪詢?nèi)蝿?wù)管理