鏈表是一種線性表數(shù)據(jù)結(jié)構(gòu)，它通過(guò)指針將一組零散的內(nèi)存塊串(節(jié)點(diǎn))連接在一起組成的存儲(chǔ)結(jié)構(gòu)。每個(gè)節(jié)點(diǎn)包含兩部分內(nèi)容：節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)和節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)的指針(next)。

每個(gè)節(jié)點(diǎn)通常包含兩部分：

數(shù)據(jù)：保存與節(jié)點(diǎn)關(guān)聯(lián)的實(shí)際值

指針：保存下一個(gè)節(jié)點(diǎn)的內(nèi)存地址(引用)

鏈表的入口點(diǎn)稱為表頭，通過(guò)頭節(jié)點(diǎn)訪問(wèn)鏈表，最后一個(gè)節(jié)點(diǎn)稱為尾節(jié)點(diǎn)，指向null或者nullptr，表示列表的結(jié)束。

鏈表類型

單鏈表中每個(gè)節(jié)點(diǎn)包含了實(shí)際數(shù)據(jù)和下一個(gè)節(jié)點(diǎn)的引用，并且它只允許單向遍歷整個(gè)鏈表。

單鏈表常用于：

內(nèi)存管理，實(shí)現(xiàn)內(nèi)存池，動(dòng)態(tài)分配和回收

數(shù)據(jù)庫(kù)索引，插入和刪除

表示多項(xiàng)式和稀疏矩陣

操作系統(tǒng)，進(jìn)程調(diào)度和管理系統(tǒng)資源

劣勢(shì)：隨機(jī)訪問(wèn)性能較差，數(shù)據(jù)丟失的脆弱性，不能用于并行處理。

雙鏈表中每個(gè)節(jié)點(diǎn)包含了前一個(gè)和后一個(gè)節(jié)點(diǎn)的引用，允許向前或者向后兩個(gè)方向遍歷鏈表，但需要額外的內(nèi)存用于向后引用。

雙鏈表常用于：hash表，基于key高效存儲(chǔ)和檢索數(shù)據(jù)

劣勢(shì)：消耗更多內(nèi)存，訪問(wèn)元素更慢

循環(huán)鏈表中，最后一個(gè)節(jié)點(diǎn)指向第一個(gè)節(jié)點(diǎn)，循環(huán)列表可以是單向也可以是雙向的。遍歷循環(huán)列表時(shí)，可以從任意節(jié)點(diǎn)開(kāi)始，并沿任意方向向前或向后比那里鏈表。

循環(huán)鏈表常用于：

資源分配，實(shí)現(xiàn)循環(huán)調(diào)度

播放歌曲或視頻

緩存，固定大小的數(shù)據(jù)結(jié)構(gòu)

循環(huán)隊(duì)列

鏈表可以執(zhí)行的操作

插入：向鏈表中添加新節(jié)點(diǎn)需要調(diào)整現(xiàn)有節(jié)點(diǎn)的指針，插入可以在鏈表的開(kāi)始、結(jié)束或任何位置執(zhí)行

刪除：從鏈表中刪除一個(gè)節(jié)點(diǎn)需要調(diào)整相鄰節(jié)點(diǎn)的指針，以填補(bǔ)被刪除節(jié)點(diǎn)留下的空白，刪除可以在鏈表的開(kāi)始、結(jié)束或任何位置執(zhí)行

搜索：在鏈表中搜索一個(gè)特定的值需要從頭節(jié)點(diǎn)開(kāi)始遍歷鏈表，直到找到該值或達(dá)到鏈表末尾

鏈表的優(yōu)勢(shì)：

動(dòng)態(tài)擴(kuò)容和收縮

插入和刪除非常高效

結(jié)構(gòu)靈活

鏈表的劣勢(shì)：

隨機(jī)訪問(wèn)：不能通過(guò)索引直接訪問(wèn)元素，需要遍歷查找特定的值

額外內(nèi)存：鏈表需要額外的內(nèi)存存儲(chǔ)指針。