前言
鏈表和數(shù)組都是兩個底層的數(shù)據(jù)結(jié)構(gòu)讯檐，只不過我覺得這倆是相反的，在難易程度上鏈表類型更多一些挺物，想多難一些，但是其實都差不多
1.什么是鏈表飘弧？
它是通過指針姻乓，將一個個或者連接，或者不連接的內(nèi)存塊串聯(lián)起來的數(shù)據(jù)結(jié)構(gòu)眯牧，其中鏈表里的內(nèi)存塊叫做結(jié)點蹋岩，而結(jié)點中不光存儲所需要的數(shù)據(jù)結(jié)構(gòu)，還要存儲下一個結(jié)點的地址学少，而記錄下個結(jié)點地址的指針叫后繼指針剪个，在這其中有兩個節(jié)點比較特殊，分別是第一個節(jié)點和和最后一個節(jié)點版确，第一個節(jié)點叫頭結(jié)點扣囊，最后一個節(jié)點叫尾結(jié)點，頭結(jié)點記錄了鏈表的地址绒疗，尾結(jié)點不是指向下一個地址侵歇，而是指向一個空地址NULL
鏈表的分類
鏈表分為三種
1.單鏈表
頭結(jié)點記錄鏈表的地址，尾結(jié)點指向一NULL吓蘑，類似一條直線一樣的叫做單鏈表
2.雙向鏈表
每個節(jié)點不只有一個后繼指針Next惕虑，還有一個前驅(qū)指針prev指向前面的結(jié)點，因為需要額外的空間存儲另一個指針磨镶，所以雙向鏈表比單鏈表更占用空間
雙鏈表適合某種情況下的刪除和插入溃蔫，這里的某種情況是指需要對一個已知結(jié)點的前面的結(jié)點刪除或插入操作時，單鏈表需要重新遍歷O(n)琳猫，而雙向鏈表伟叛，還存儲前驅(qū)指針prev所以在O(1)時間就搞定了
3.循環(huán)鏈表
是一種特殊的單鏈表，只不過他的尾結(jié)點不是指向一個NULl地址脐嫂，而是指向頭結(jié)點统刮，他像一個環(huán)一樣首尾相連
鏈表的刪除和插入操作
在鏈表里，因為不需要保持?jǐn)?shù)據(jù)的連續(xù)性账千，所以插入和刪除操作速度快侥蒙，我們只需要考慮相鄰結(jié)點指針的改變時間復(fù)雜度為O(1)
空間換時間思想
- 對于速度慢的程序，可以使用消耗空間來換取時間來進(jìn)行優(yōu)化
- 對于占用內(nèi)存較大的程序蕊爵，我們可以采用消耗更多的時間來換取空間來優(yōu)化
鏈表和數(shù)組比較
數(shù)組：
優(yōu)點：簡單易用辉哥，因為是連續(xù)的內(nèi)存，所以可以借助CPU緩存機(jī)制來預(yù)讀數(shù)組中的數(shù)據(jù)，訪問頻率更高
缺點：大小固定醋旦，內(nèi)存分配固定
鏈表：
優(yōu)點：支持動態(tài)擴(kuò)容
缺點：沒辦法預(yù)讀內(nèi)存
如果你對代碼對內(nèi)存要求非常嚴(yán)格恒水，那么數(shù)組比較適合（因為練筆需要額外的內(nèi)存來存儲下一個結(jié)點的地址，而且鏈表的插入和刪除饲齐，會導(dǎo)致內(nèi)存頻繁的申請和釋放）
