鏈表就先以單向鏈表為例夏伊，簡(jiǎn)單講解下，為何有時(shí)用鏈表吻氧，有時(shí)卻覺(jué)得數(shù)組(列表）溺忧。
首先必須初始化數(shù)組，然后把新節(jié)點(diǎn)的指針指向next盯孙，這個(gè)地方指針容易出錯(cuò)鲁森，須注意下。
刪除操作振惰，先找上節(jié)點(diǎn)歌溉，將其指針，直接指向next骑晶。這時(shí)痛垛，你會(huì)說(shuō)，咦透罢，cur.next指針沒(méi)有清空啊榜晦，emmm,那你也可以清空。指向null羽圃。
雙向列表實(shí)現(xiàn)乾胶，只要給next,加上pre屬性，讓它指向前面cur,就行朽寞。
循環(huán)列表實(shí)現(xiàn)時(shí)识窿，將頭節(jié)點(diǎn)的next屬性指向其本身，然一次添加元素即可脑融。
現(xiàn)在看看喻频，鏈表的優(yōu)勢(shì)和劣勢(shì)。
鏈表通過(guò)‘指針’將一組零散的內(nèi)存串聯(lián)起來(lái)肘迎，就可以充分利用內(nèi)存甥温；而數(shù)組內(nèi)存需連續(xù)的锻煌，足夠大的空間。
但是呢姻蚓，鏈表也得支持增改刪查宋梧，每次遍歷最優(yōu)時(shí)間復(fù)雜度O(1),最差時(shí)間復(fù)雜度O(n),而數(shù)組只要用下表就可以訪問(wèn)到，時(shí)間復(fù)雜度O(1),如果隨機(jī)查找狰挡，時(shí)間復(fù)雜度則是捂龄，O(n).
在開發(fā)中，一般用雙向列表或者循環(huán)列表加叁，這樣就能大大降低倦沧，所需的時(shí)間復(fù)雜度。其實(shí)仔細(xì)想想它匕，這就是用時(shí)間換空間的思路展融。
簡(jiǎn)單介紹下，CPU緩存：cpu從內(nèi)存中讀取數(shù)據(jù)時(shí)超凳，會(huì)把每次取到的數(shù)據(jù)加載到CPU的緩存中愈污。而CPU每次從內(nèi)存中讀取數(shù)據(jù)并不是只讀取那個(gè)特定要訪問(wèn)的地址，而是讀取一個(gè)數(shù)據(jù)塊轮傍，并保存到CPU緩存中暂雹，然后下次訪問(wèn)內(nèi)存數(shù)據(jù)的時(shí)候就會(huì)從CPU緩存中開始查找，如果沒(méi)找到创夜，就從內(nèi)存中取杭跪。這樣就實(shí)現(xiàn)了比內(nèi)存訪問(wèn)更快的機(jī)制。
對(duì)于數(shù)組而言驰吓，存儲(chǔ)空間是連續(xù)的涧尿，所以在加載某個(gè)下標(biāo)元素時(shí)，可以把以后的幾個(gè)下標(biāo)元素在也加載到CPU緩存這樣檬贰，執(zhí)行起來(lái)速度更快(比訪問(wèn)內(nèi)存)姑廉，比存儲(chǔ)空間不連續(xù)的鏈表存儲(chǔ)也快。
如果翁涤，我們能利用緩存鏈表桥言，那么又能降低操作鏈表的時(shí)間復(fù)雜度了。也可采用2-8策略葵礼，用過(guò)的元素放到鏈表最前面号阿，少用的自然就在后面了，這個(gè)實(shí)現(xiàn)鸳粉，可用哈希表來(lái)記錄數(shù)據(jù)的位置扔涧；緩存呢，注意一下，是否達(dá)到上限就行枯夜。
reference:極客時(shí)間 《數(shù)據(jù)結(jié)構(gòu)與算法之美》
? ? ? ? ? ? ? ?《數(shù)據(jù)結(jié)構(gòu)與算法javascript描述》
? ? ? ? ? ? ? ? ?部分源碼：https://github.com/Jiangjao/python_learn_demo/new/master
? ? ? ? ? ? ? ? ?部分圖片來(lái)源：leetcode 鏈表介紹
詳細(xì)細(xì)節(jié)弯汰，有時(shí)間再慢慢添加。
