- 數(shù)組
① 數(shù)組的定義上有個(gè)必要條件是：“存儲(chǔ)在連續(xù)的內(nèi)存空間里”的有序元素序列
② “JS 數(shù)組未必是真正的數(shù)組”
③ 區(qū)分JS數(shù)組 和 常規(guī)數(shù)組
常規(guī)數(shù)組： 數(shù)組元素內(nèi)容是一種類型的元素符相，如const arr = [1,2,3,4]绷旗，在存儲(chǔ)空間是連續(xù)內(nèi)存的
JS數(shù)組： 數(shù)組元素內(nèi)容不是同一種類型的元素虱咧，如const arr = ['haha', 1, {a:1}]舟误，則在存儲(chǔ)上是一段非連續(xù)空間限番。此時(shí)民傻，JS 數(shù)組不再具有數(shù)組的特征，其底層其實(shí)是由鏈表來實(shí)現(xiàn)的
鏈表
① 在存儲(chǔ)上是無序的恋谭，依靠next指針指向下一個(gè)node結(jié)點(diǎn)
② JS 中的鏈表糠睡，是以嵌套的對象的形式來實(shí)現(xiàn)的鏈表 與 數(shù)組
① 我們假設(shè)數(shù)組的長度是 n，那么因增加/刪除操作導(dǎo)致需要移動(dòng)的元素?cái)?shù)量疚颊，就會(huì)隨著數(shù)組長度 n 的增大而增大狈孔，呈一個(gè)線性關(guān)系信认。所以說數(shù)組增加/刪除操作對應(yīng)的復(fù)雜度就是 O(n)；
在鏈表中均抽，添加和刪除操作的復(fù)雜度是固定的——不管鏈表里面的結(jié)點(diǎn)個(gè)數(shù) n 有多大嫁赏，只要我們明確了要插入/刪除的目標(biāo)位置，那么我們需要做的都僅僅是改變目標(biāo)結(jié)點(diǎn)及其前驅(qū)/后繼結(jié)點(diǎn)的指針指向油挥。
因此我們說鏈表增刪操作的復(fù)雜度是常數(shù)級(jí)別的復(fù)雜度潦蝇，用大 O 表示法表示為 O(1)
② 在數(shù)組中，我們直接訪問索引深寥、可以做到一步到位攘乒，這個(gè)操作的復(fù)雜度會(huì)被降級(jí)為常數(shù)級(jí)別(O(1))；
隨著鏈表長度的增加惋鹅，我們搜索的范圍也會(huì)變大则酝、遍歷其中任意元素的時(shí)間成本自然隨之提高。這個(gè)變化的趨勢呈線性規(guī)律负饲，用大 O 表示法表示為 O(n)
總結(jié)
鏈表的插入/刪除效率較高堤魁，而訪問效率較低喂链；
數(shù)組的訪問效率較高返十，而插入效率較低
