學習Javascript的演算法和資料結構--連結串列

在上個筆記中，我們分享了JavaScript中的陣列，瞭解到陣列的一些特點，比如順序儲存資料，以及一些常用的操作的複雜度，比如陣列的訪問，arr［i］是O（1）的複雜度，但是如果是插入和刪除的話，就需要O（n）的時間複雜度了，接下來，我們要分享的資料結構——連結串列，它的插入、刪除的時間複雜度為O（1），相比陣列的話，好了很多。

先來張圖，瞭解一下連結串列的資料結構

連結串列的資料結構

從圖中我們可以看到，連結串列儲存不同於陣列，連結串列中的元素在記憶體中並不是連續放置的。每個元素由一個儲存元素本身的節點和一個指向下一個元素的引用（也稱指標或連結）組成。

在Javascript中，陣列已經是內部實現的，可以直接用，但是連結串列是沒有的，所以需要我們自己來實現。

對於連結串列，我們需要宣告一個Node的類，Node類表示我們想要新增到連結串列中的項。它包含一個 val屬性，該屬性表示要加入連結串列元素的值；以及一個next屬性，該屬性是指向連結串列中下一個元素的指標。

class Node { constructor（val） { this。val = val； this。next = null； }}

然後是我們的連結串列，在陣列中，我們可以直接訪問任何位置的任何元素，而要想訪問連結串列中間的一個元素，則需要從

起點

（

表頭

）開始迭代連結串列直到找到所需的元素。

所以我們的連結串列的實現如下

class LinkedList { constructor（compareFun） { this。compareFun = compareFun； // 輔助函式，主要用來對節點的val做對比，來構造連結串列結構 this。head = null； // t this。size = 0； // 記錄連結串列長度 }}

然後我們需要一步一步實現連結串列操作，需要的一些api方法，

1。向連結串列末尾新增元素（push）

class LinkedList { // 。。。。其他的一些方法 push（val） { const node = new Node（val）； let current； if （this。head == null） { this。head = node； } else { current = this。head； while（current。next ！= null） { current = current。next； } // 從頭遍歷到最後，找到node。next == null的節點，然後將節點賦值 current。next = node； } } this。size++；}

圖示：連結串列插入一個元素

插入一個元素

2。移除連結串列中的某個元素（remove）

class LinkedList { remove（index） { let current = this。head； if （index >= 0 && index < this。size） { if （index === 0） { // 特殊情況，要移除head，需要特別處理 this。head = current。next； } else { let prev = null； for （let i = 0； i < index； i++） { prev = current； current = current。next； } prev。next = current。next； } this。size——； return current。element； } return null； }}

圖示：連結串列刪除一個元素

連結串列刪除head

連結串列刪除其他的元素

3。連結串列仁義位置插入元素

class LinkedList { insert（index， val） { if （index >= 0 && index <= this。size） { const node = new Node（val）； const current = this。head； if （index === 0） { // 如果要插入的位置實在頭部 node。next = current。next； this。head = node； } else { let prev； for （let i = 0； i < index； i++） { pre = current； current = urrent。nextl } } } }}

圖示：連結串列任意位置插入一個元素