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

每個節(jié)點通常包含兩部分：

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

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

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

鏈表類型

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

單鏈表常用于：

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

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

表示多項式和稀疏矩陣

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

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

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

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

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

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

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

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

播放歌曲或視頻

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

循環(huán)隊列

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

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

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

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

鏈表的優(yōu)勢：

動態(tài)擴容和收縮

插入和刪除非常高效

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

鏈表的劣勢：

隨機訪問：不能通過索引直接訪問元素，需要遍歷查找特定的值

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