名詞解析：1、 線性表 ：線性表就是數據排成壹條線壹樣的結構。每個線性表上的數據最多只有前和後兩個方向。其實除了數組，鏈表、隊 列、棧等也是線性表結構。與它相對立的概念是非線性表，比如 二叉樹、堆、圖。之所以叫 非線性 ，是因為在非線性表中，數據之間不是簡單的前後關系。
?2、 連續的內存空間? 和 相同類型的數據 。正是因為這兩個限制，它才可以 隨機訪問 。但有利就有弊，這兩個限制也讓數組的很多操作變得非常? 低效 ，比如要想在數組中刪除、插入壹個數據，為了保證連續性，就需要做大量的數據搬移工作。
相比數組，鏈表是壹種稍微復雜壹點的數據結構。鏈表中的元素可存儲在內存的任何地方（不像數組那樣，需要連續的內存空間）。鏈表的每個元素都存儲了? 下壹個元素的地址 ，通過 “ 指針 ” 將壹組零散的內存塊串聯起來使用，從而使壹系列隨機的內存地址串在壹起。
幾種常見的鏈表結構： 單鏈表 、 雙向鏈表 和 循環鏈表 。
? ?單鏈表中的節點應該具有兩個屬性：val?和?next
單鏈表
它包含兩個域，壹個信息域和壹個指針域。這個鏈接指向列表中的下壹個節點，而最後壹個節點則指向壹個空值。
雙向鏈表
每個節點有兩個連接：壹個指向前壹個節點，（當此“連接”為第壹個“連接”時，指向空值或者空列表）；而另壹個指向下壹個節點，（當此“連接”為最後壹個“連接”時，指向空值或者空列表）
循環鏈表
? 首節點和末節點被連接在壹起
?數組為了保持內存數據的連續性，會導致插入、刪除這兩個操作比較低效。
每次進行插入操作的時候，假如我們將壹個數據插入數組的第 k 個位置，為了把第 k 個位空出來，就需要 將 k 以後的 數據全部 往後移動壹位。所以 平均時間復雜度 為 O(n)。
同理，如果我們要刪除第 k 個位置的數據，為了內存的連續性，也需要搬移數據，不然中間就會出現空洞，內存就不連續了，所以平均時間復雜度 也是 O(n)。
實際上，在某些特殊場景下，我們並不壹定非得追求數組中數據的連續性。如果我們將多次刪除操作集中在壹起執行，刪除的效率是不是會提高很多呢？ 我們繼續來看例子。數組 a[10] 中存儲了8個元素：a，b，c，d，e，f，g，h。現在，我們要依次刪除a，b，c三個元素。
為了避免 d，e，f，g，h 這幾個數據會被搬移三次，可以先記錄下已經刪除的數據。每次的刪除操作並不是真正地搬移數據，只是? 記錄數據已經被刪除 。當數組沒有更多空間存儲數據時，我們再觸發執行壹次真正的刪除操作，這樣就大大減少了刪除操作導致的數據搬移。
如果 在實際情況中 刪除 和 插入操作比較多，?為了 改善 刪除 和 插入的時間復雜度 ，我們就可以使用鏈表。
鏈表在進行插入或刪除操作的時候，我們並不需要為了保持內存的連續性而搬移結點，因為鏈表的存儲空間本身就不是連續的。所以， 在鏈表中插入和刪除壹個數據是非常快速的 。
但是 鏈表要想隨機訪問第 k 個元素，就沒有數組那麽高效了。因為鏈表中的數據並非連續存儲的，所以無法像數組那樣，根據首地址和下標，通過 尋址公式? 就能直接計算出對應的內存地址，而是需要根據指針壹個結點壹個結點地依次遍歷，直到找到相應的結點，所以時間復雜度為 O(n)。
總結 ：鏈表適合插入、刪除，時間復雜度 O(1)；數組支持隨機訪問，根據下標隨機訪問的時間復雜度為O(1)。?
? 1、鏈表 和 數組不同，數組需要壹塊連續的內存空間，而鏈表並不需要連續的內存空間，它通過“指針”將壹組零散的內存塊串聯起來使用。
註意 ： 在?JavaScript 中 數組是壹種類列表對象，它的原型中提供了遍歷和修改元素的相關操作。JavaScript 數組的長度和元素類型都是非固定的。因為數組的長度可隨時改變，並且其數據在內存中也可以? 不連續 ，所以 JavaScript 數組不壹定是密集型的，這取決於它的使用方式。在 JS 中數組通過哈希映射或者字典的方式來實現，所以不是連續的。壹般來說，數組的這些特性會給使用帶來方便，但如果這些特性不適用於妳的特定使用場景的話，可以考慮使用類型數組。 這裏我們討論的不是?JavaScript 中的數組 。
?2、數組的元素都在壹起；鏈表的元素是分開的，其中每個元素都存儲了下壹個元素的地址。
?3、數組的讀取速度很快；鏈表的插入和刪除速度很快。
總結 ：如果妳需要經常? 添加? 或? 刪除? 結點，鏈表可能是壹個不錯的選擇。
如果妳需要經常按索引訪問元素，數組可能是比鏈表更好的選擇。