刷題前必學！鏈表！用JavaScript學數據結構與算法详情 - 算法,數據結構,數據結構和算法,javascript,程序員 HowieCong 日志

🧑‍💻JavaScript數據結構與算法-HowieCong

務必要熟悉JavaScript使用再來學！

一、鏈表的基本形態

鏈表和數組都是有序的列表，都是線性結構（有且僅有一個前驅，有且僅有一個後續）；不同點在於，鏈表中，數據單位的名稱叫做“結點”，而結點和結點的分佈，在內存中都是離散的

1. 數組的“連續”

在內存中最為關鍵的一個特徵，就是對應一段位於自身上界和下界之間的，一段連續的內存空間。元素與元素之間，緊密相連，如下：

2. 鏈表的“離散

鏈表的結點，允許散落在內存空間的各個角落裏。內容為1->2->3->4->5的鏈表，它的內存形態可以散亂如下：

3. 區別

數組的元素是連續的，每個元素的內存地址可以根據其索引距離數組頭部的距離來計算。對數組來説，每一個元素都可以通過數組的索引下標直接定位
鏈表的元素和元素之間似乎毫無內存上的可分，沒有關聯時，就創造關聯！在鏈表中，每個結點的結構包括了兩部分的內容：數據域和指針域。JS中的鏈表，是以嵌套對象的形式來實現的：

{
    // 數據源
    val: 1,
    // 指針域，指向下一個結點
    next:{
        val: 2,
        next:{
            val:3,
            next:...
        }
    }
}

！！！數據域存儲的是當前結點所存儲的數據值，而指針域則代表下一個結點（後續結點）的引用。用next指針來記錄後續結點的引用，每一個結點至少都能知道自己後面的數值是哪位了，原來的相互獨立的結點之間從無關係都有關係了！！！主動才有故事啊

簡化來就是如下這樣：

要想訪問鏈表的每一個元素，都得從起點結點開始，逐個訪問next，一直訪問到目標結點為止，為了保證起點結點是可抵達的，我們還會設定一個head指針來專門指向鏈表的開始位置：

二、鏈表結點的創建

創建鏈表結點，需要一個構造函數

function ListNode(val){
    this.val = val;
    this.next = null;
}

使用構造函數去創建結點時，傳入val（數據域對應的值內容）、指定next（下一個鏈表結點）

const node = new ListNode(1)
node.next = new ListNode(2)

三、鏈表結點的添加

鏈表的結點間關係是通過next指針來維繫的，因此，鏈表元素的添加和刪除操作，本質上是在圍繞next指針來做文章
直接在尾部添加相對比較簡單方便，改變一個next指針就可以
如果在兩個結點間插入一個結點？
- 鏈表有時會有頭結點，這時即便你是在鏈表頭增加結點，其本質也是“在頭結點和第一個結點之間插入一個新結點”。
- 因此，任意兩結點間插入一個新結點這種類型的增加操作，將會是鏈表基礎中的一個關鍵考點
我們需要變更的是前驅結點和目標結點的next指針指向：如下
- 插入前：
- 插入後：

// 如果目標結點本來不存在，那麼記得手動創建
const new ListNode(3)
// 把node3的指針指向node2（node1.next）
node3.next = node1.next
// 把node1的next指針指向node3
node1.next = node3

四、鏈表結點的刪除

把重心放在next指針的調整上
如何把剛才添加進來的node3從現在的鏈表刪除？
刪除的標準：在鏈表的遍歷過程中，無法遍歷到某個結點的存在，按照這個標準，要想遍歷不到node3，我們直接讓它的前驅結點node1的next指針跳過它，指向node3的後續即可：

node3成為了一個完全不抵達的結點，它會被JS的垃圾回收器自動回收掉，這個過程如下代碼：

node1.next = node3.next

提醒:在涉及鏈表刪除操作的題目中，重點不是定位目標結點，而是定位目標結點的前驅結點。做題時，完全可以只使用一個指針（引用）這個指針用來定位目標結點的前驅結點

// 利用node1可以定位到node3
const target = node1.next
node1.next = target.next

五、鏈表和數組的辨析

1. JS數組未必是真正的數組

假設數組長度為n，那麼因為增加或刪除操作導致需要移動的元素數量，就會隨着數組長度n的增大而增大，呈現一個線性關係，所以説數組增加或刪除操作對應的複雜度為O(n)
JavaScript有點特別，JS數組未必是真正的數組！
- 我們在一個數組中只定義了一種類型的元素，如下
```
const arr = [1,2,3,4]
```
- 定義了不同類型的元素：
```
const arr = ['haha', 1, {a:1}]
```
對應的就是一段非連續的內存。JS 數組不再具有數組的特徵，其底層使用哈希映射分配內存空間，是由對象鏈表來實現的

2. 鏈表高效的增刪操作

在鏈表中，添加和刪除操作的複雜度是固定的
不管鏈表裏面的結點個數n有多大，只要我們明確了要插入/刪除的目標位置，那麼我們需要做的都僅僅是改變目標結點及其前驅/後繼結點的指針指向
因此鏈表增刪操作的複雜度是常數級別的複雜度，用大O表示法表示為 O(1)

3. 鏈表麻煩的訪問操作

鏈表也有一個弊端：當我們試圖讀取某一個特定的鏈表結點時，必須遍歷整個鏈表來查找它
比如説我要在一個長度為 n（n>10）的鏈表裏，定位它的第 10 個結點，如下：

// 記錄目標結點的位置 
const index = 10 
// 設一個遊標指向鏈表第一個結點，從第一個結點開始遍歷 
let node = head 
// 反覆遍歷到第10個結點為止 
for(let i=0;i<index&&node;i++) { 
    node = node.next 
}

隨着鏈表長度的增加，我們搜索的範圍也會變大、遍歷其中任意元素的時間成本自然隨之提高。這個變化的趨勢呈線性規律，用大O表示法表示為 O(n)
在數組中，我們直接訪問索引、可以做到一步到位，這個操作的複雜度會被降級為常數級別(O(1))，如下：

arr[9]

六、總結

鏈表的插入/刪除效率較高，而訪問效率較低

數組的訪問效率較高，而插入效率較低

可能會作為數據結構選型的依據來單獨考察

❓其他

1. 疑問與作者HowieCong聲明

如有疑問、出錯的知識，請及時點擊下方鏈接添加作者HowieCong的其中一種聯繫方式或發送郵件到下方郵箱告知作者HowieCong
若想讓作者更新哪些方面的技術文章或補充更多知識在這篇文章，請及時點擊下方鏈接添加里面其中一種聯繫方式或發送郵件到下方郵箱告知作者HowieCong
聲明：作者HowieCong目前只是一個前端開發小菜鳥，寫文章的初衷只是全面提高自身能力和見識；如果對此篇文章喜歡或能幫助到你，麻煩給作者HowieCong點個關注/給這篇文章點個贊/收藏這篇文章/在評論區留下你的想法吧，歡迎大家來交流！