- 數(shù)組
① 數(shù)組的定義上有個必要條件是：“存儲在連續(xù)的內(nèi)存空間里”的有序元素序列
② “JS 數(shù)組未必是真正的數(shù)組”
③ 區(qū)分JS數(shù)組 和 常規(guī)數(shù)組
常規(guī)數(shù)組： 數(shù)組元素內(nèi)容是一種類型的元素，如const arr = [1,2,3,4]，在存儲空間是連續(xù)內(nèi)存的
JS數(shù)組： 數(shù)組元素內(nèi)容不是同一種類型的元素，如const arr = ['haha', 1, {a:1}]，則在存儲上是一段非連續(xù)空間。此時，JS 數(shù)組不再具有數(shù)組的特征，其底層其實是由鏈表來實現(xiàn)的
鏈表
① 在存儲上是無序的，依靠next指針指向下一個node結(jié)點
② JS 中的鏈表，是以嵌套的對象的形式來實現(xiàn)的鏈表 與 數(shù)組
① 我們假設(shè)數(shù)組的長度是 n，那么因增加/刪除操作導致需要移動的元素數(shù)量，就會隨著數(shù)組長度 n 的增大而增大，呈一個線性關(guān)系。所以說數(shù)組增加/刪除操作對應的復雜度就是 O(n)；
在鏈表中，添加和刪除操作的復雜度是固定的——不管鏈表里面的結(jié)點個數(shù) n 有多大，只要我們明確了要插入/刪除的目標位置，那么我們需要做的都僅僅是改變目標結(jié)點及其前驅(qū)/后繼結(jié)點的指針指向。
因此我們說鏈表增刪操作的復雜度是常數(shù)級別的復雜度，用大 O 表示法表示為 O(1)
② 在數(shù)組中，我們直接訪問索引、可以做到一步到位，這個操作的復雜度會被降級為常數(shù)級別(O(1))；
隨著鏈表長度的增加，我們搜索的范圍也會變大、遍歷其中任意元素的時間成本自然隨之提高。這個變化的趨勢呈線性規(guī)律，用大 O 表示法表示為 O(n)
總結(jié)
鏈表的插入/刪除效率較高，而訪問效率較低；
數(shù)組的訪問效率較高，而插入效率較低
