理解 數(shù)組與鏈表
1. 數(shù)組
① 數(shù)組的定義上有個(gè)必要條件是：“存儲(chǔ)在連續(xù)的內(nèi)存空間里”的有序元素序列慎恒。
② “JS 數(shù)組未必是真正的數(shù)組”
③ 區(qū)分JS數(shù)組 和 常規(guī)數(shù)組
常規(guī)數(shù)組： 數(shù)組元素內(nèi)容是一種類(lèi)型的元素，如const arr = [1,2,3,4]颂翼，在存儲(chǔ)空間是連續(xù)內(nèi)存的达皿。
JS數(shù)組： 數(shù)組元素內(nèi)容不是同一種類(lèi)型的元素乔遮，如const arr = ['haha', 1, {a:1}]沪编，則在存儲(chǔ)上是一段非連續(xù)空間帖池。此時(shí)，JS 數(shù)組不再具有數(shù)組的特征慌申，其底層其實(shí)是由鏈表來(lái)實(shí)現(xiàn)的陌选。
2. 鏈表
① 在存儲(chǔ)上是無(wú)序的理郑，依靠next指針指向下一個(gè)node結(jié)點(diǎn)
② JS 中的鏈表，是以嵌套的對(duì)象的形式來(lái)實(shí)現(xiàn)的
3. 鏈表 與 數(shù)組
① 我們假設(shè)數(shù)組的長(zhǎng)度是 n咨油，那么因增加/刪除操作導(dǎo)致需要移動(dòng)的元素?cái)?shù)量您炉，就會(huì)隨著數(shù)組長(zhǎng)度 n 的增大而增大，呈一個(gè)線性關(guān)系役电。所以說(shuō)數(shù)組增加/刪除操作對(duì)應(yīng)的復(fù)雜度就是 O(n)赚爵。
在鏈表中，添加和刪除操作的復(fù)雜度是固定的——不管鏈表里面的結(jié)點(diǎn)個(gè)數(shù) n 有多大法瑟，只要我們明確了要插入/刪除的目標(biāo)位置冀膝，那么我們需要做的都僅僅是改變目標(biāo)結(jié)點(diǎn)及其前驅(qū)/后繼結(jié)點(diǎn)的指針指向。 因此我們說(shuō)鏈表增刪操作的復(fù)雜度是常數(shù)級(jí)別的復(fù)雜度霎挟，用大 O 表示法表示為 O(1)
② 在數(shù)組中窝剖，我們直接訪問(wèn)索引、可以做到一步到位酥夭，這個(gè)操作的復(fù)雜度會(huì)被降級(jí)為常數(shù)級(jí)別(O(1))：
隨著鏈表長(zhǎng)度的增加枯芬，我們搜索的范圍也會(huì)變大、遍歷其中任意元素的時(shí)間成本自然隨之提高采郎。這個(gè)變化的趨勢(shì)呈線性規(guī)律千所，用大 O 表示法表示為 O(n)。
簡(jiǎn)單來(lái)說(shuō)：
鏈表的插入/刪除效率較高蒜埋，而訪問(wèn)效率較低淫痰；
數(shù)組的訪問(wèn)效率較高，而插入效率較低
