鏈表是一種線性表數(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)，進(jìn)程調(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)存存儲指針。
下載文檔
