1. 數(shù)組

數(shù)組定義

??數(shù)組（Array）是有序的元素序列。屬于線性結(jié)構(gòu)（有且僅有一個(gè)前驅(qū)、有且僅有一個(gè)后繼）。

數(shù)組特點(diǎn)

??數(shù)組的關(guān)鍵在于在內(nèi)存中的物理地址對(duì)應(yīng)的是一段連續(xù)的內(nèi)存。這意味著如果想要在任意位置刪除/新增一個(gè)元素，那么該位置往后的所有元素，都需要往前挪/往后挪一個(gè)位置。假設(shè)數(shù)組的長度是 n，那么因增加/刪除操作導(dǎo)致需要移動(dòng)的元素?cái)?shù)量，就會(huì)隨著數(shù)組長度 n 的增大而增大，呈一個(gè)線性關(guān)系。所以說數(shù)組增加/刪除操作對(duì)應(yīng)的時(shí)間復(fù)雜度就是 O(n)。

在js中的數(shù)組比較特殊，如果我們?cè)谝粋€(gè)數(shù)組中只定義了一種類型的元素，比如：

const arr = [1,2,3,4]

它是一個(gè)純數(shù)字?jǐn)?shù)組，那么對(duì)應(yīng)的確實(shí)是連續(xù)內(nèi)存。
但如果我們定義了不同類型的元素：

const arr = ['haha', 1, {a:1}]

它對(duì)應(yīng)的就是一段非連續(xù)的內(nèi)存。此時(shí)，JS 數(shù)組不再具有數(shù)組的特征，其底層使用哈希映射分配內(nèi)存空間，是由對(duì)象鏈表來實(shí)現(xiàn)的。
謹(jǐn)記“JS 數(shù)組未必是真正的數(shù)組”

2. 棧和隊(duì)列（操作受限的數(shù)組）

棧

??棧是一種后進(jìn)先出(LIFO，Last In First Out)的數(shù)據(jù)結(jié)構(gòu)。——只用 pop 和 push 完成增刪的“數(shù)組”

• 只允許從尾部添加元素
• 只允許從尾部取出元素

隊(duì)列

??隊(duì)列（Queue）是一種先進(jìn)先出（FIFO，F(xiàn)irst In First Out）的數(shù)據(jù)結(jié)構(gòu)?！挥?push 和 shift 完成增刪的“數(shù)組”。在棧元素出棧時(shí)，我們關(guān)心的是棧頂元素（數(shù)組的最后一個(gè)元素）；隊(duì)列元素出隊(duì)時(shí)，我們關(guān)心的則是隊(duì)頭元素（數(shù)組的第一個(gè)元素）。

3. 鏈表

??鏈表和數(shù)組相似，線性結(jié)構(gòu)（有且僅有一個(gè)前驅(qū)、有且僅有一個(gè)后繼），不同點(diǎn)在于，鏈表中，數(shù)據(jù)單位的名稱叫做“結(jié)點(diǎn)”，而結(jié)點(diǎn)和結(jié)點(diǎn)的分布，在內(nèi)存中可以是離散的。
一個(gè)內(nèi)容為1->2->3->4->5的鏈表，在內(nèi)存中的形態(tài)可以是散亂如下的：

在鏈表中，每一個(gè)結(jié)點(diǎn)的結(jié)構(gòu)都包括了兩部分的內(nèi)容：數(shù)據(jù)域和指針域。JS 中的鏈表，是以嵌套的對(duì)象的形式來實(shí)現(xiàn)的：

{
    // 數(shù)據(jù)域
    val: 1,
    // 指針域，指向下一個(gè)結(jié)點(diǎn)
    next: {
        val:2,
        next: ...
    }
}

數(shù)據(jù)域存儲(chǔ)的是當(dāng)前結(jié)點(diǎn)所存儲(chǔ)的數(shù)據(jù)值，而指針域則代表下一個(gè)結(jié)點(diǎn)（后繼結(jié)點(diǎn)）的引用。

創(chuàng)建鏈表:

function ListNode(val) {
    this.val = val;
    this.next = null;
}
const node = new ListNode(1)  
node.next = new ListNode(2)

鏈表元素的添加和刪除操作，本質(zhì)上都是在圍繞 next 指針做文章，例如在節(jié)點(diǎn)1和節(jié)點(diǎn)2之間插入節(jié)點(diǎn)3：

// 如果目標(biāo)結(jié)點(diǎn)本來不存在，那么記得手動(dòng)創(chuàng)建
const node3 = new ListNode(3)     
// 把node3的 next 指針指向 node2（即 node1.next）
node3.next = node1.next
// 把node1的 next 指針指向 node3
node1.next = node3

刪除節(jié)點(diǎn)3：

node1.next = node3.next 

在涉及鏈表刪除操作的題目中，重點(diǎn)不是定位目標(biāo)結(jié)點(diǎn)，而是定位目標(biāo)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。做題時(shí)，完全可以只使用一個(gè)指針（引用），這個(gè)指針用來定位目標(biāo)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。

總結(jié)：鏈表的插入/刪除效率較高，而訪問效率較低；數(shù)組的訪問效率較高，而插入效率較低。文章來源地址http://www.zghlxwxcb.cn/news/detail-837667.html

到了這里，關(guān)于線性數(shù)據(jù)結(jié)構(gòu)：數(shù)組、受限數(shù)組（棧、隊(duì)列）、線性表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！