---
tags: DSA in JavaScript
---
# Ch.19-1 Singly Linked List (上)

現在開始資料結構的部分了，首先來介紹 singly linked list 單向鏈結串列，將一連串的資料節點一個接一個串起來的結構。
單向鏈結串列有三個屬性：

- head：代表串列開頭的節點
- tail：代表串列結尾的節點
- length：代表串列內的節點數量

而每個節點都會有兩個屬性：

- val：節點的值
- next：下一個節點，或是指向下一個節點的指標

因此鏈結串列大多有下列特性：

- 沒有索引 (indexes)
- 選取節點比陣列麻煩 (因為沒有索引)
- 方便插入 / 刪除節點

先來看看程式碼大概長什麼樣子

// 節點的結構
class Node {
  constructor(val) {
    this.val = val
    this.next = null
  }
}

// 單向鏈結串列，後面會加上串列的操作方法
class SinglyLinkedList {
  constructor() {
    this.head = null
    this.tail = null
    this.length = 0
  }
}

接下來看看單向鏈結串列的方法們，要使用的話可以將這些方法貼在 class 裡面。

### push `(val)`
在串列的最後新增一個節點，並回傳改變後的串列

push (val) {
    const newNode = new Node(val)
    // 如果串列沒有節點，就將串列的頭與尾設為 newNode
    if (!this.head) {
      this.head = newNode
      this.tail = newNode
    } else {
      this.tail.next = newNode
      this.tail = newNode
    }
    this.length++
    return this
}

### pop
移除串列中最後一個節點，並回傳該節點的值

pop () {
    // 在空串列中使用 pop，回傳 undefined
    if (!this.tail) return
    let currNode = this.head
    let lastNode = currNode
    // 找到倒數第二個節點
    while (currNode.next) {
      lastNode = currNode
      currNode = currNode.next
    }
    lastNode.next = null
    this.tail = lastNode
    this.length--
    // pop 後變成空串列的話，需要做額外處理
    if (!this.length) {
      this.head = null
      this.tail = this.head
    }
    return currNode.val
}

### shift
移除串列中第一個節點，並回傳該節點的值，可理解為開頭版的 `pop()`

shift () {
    // 串列為空時使用，回傳 undefined
    if (!this.head) return
    // 串列中本來就有 head 可以找到第一個節點
    const oldHead = this.head
    this.head = oldHead.next
    this.length--
    // 如果執行後變成空串列，就需要做額外處理
    if (!this.length) this.tail = null
    return oldHead.val
}

### unshift `(val)`
在串列的開頭新增一個節點，回傳改變後的串列，是開頭版的 `push(val)`

unshift (val) {
    const newNode = new Node(val)
    // 空串列時的額外處理
    if (!this.head) {
      this.head = newNode
      this.tail = newNode
    } else {
      newNode.next = this.head
      this.head = newNode
    }
    this.length++
    return this
}

從這些方法可以看出來，除了 `pop` 是 $O(n)$ 之外，串列在新增與刪除的時間複雜度幾乎是 $O(1)$，比起 array 的 `shift` 與 `unshift` 有效率許多。

下一篇會分享 `get`、`set`、`insert`、`remove`，以及較複雜的 `reverse` 方法。