鏈表是一種線性表數(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ǔ)指針。
下載文檔
