---
tags: DSA in JavaScript
---
# Ch19-2 Singly Linked List (下)
上一篇講解到比較常用的 `push`、`pop`、`unshift`、`shift` 方法後，這篇主要會有

- [`get`](#`get(index)`)
- [`set`](#`set(index,value)`)
- [`insert`](#`insert(index,value)`)
- [`remove`](#`remove(index)`)
- [`reverse`](#`reverse()`)

### `get(index)`
可以拿到特定位置的節點，後面的方法都會使用到 `get`

get (index) {
  if (index < 0 || index >= this.length) return null
  let currNode = this.head
  // 因為沒有索引(index)，因此只能使用迴圈遍歷尋找特定位置
  for (let i = 0; i < index; i++) {
    currNode = currNode.next
  }
  return currNode
}

### `set(index,value)`
更改特定位置節點的值，有了 `get` 方法之後簡潔許多，最後回傳 true / false

set (index, value) {
  const currNode = this.get(index)
  if (!currNode) return false
  currNode.val = value
  return true
}

### `insert(index,value)`
在特定位置插入一個新節點，並回傳最後結果 true / false

insert (index, value) {
  if (index < 0 || index > this.length) return false
  if (index === this.length) {
    this.push(value)
    return true
  }
  if (index === 0) {
    this.unshift(value)
    return true
  }

  const newNode = new Node(value)
  const prevNode = this.get(index - 1)
  const temp = prevNode.next
  newNode.next = temp
  prevNode.next = newNode
  this.length++
  return true
}

### `remove(index)`
移除指定位置的節點，並回傳被移除的節點

remove (index) {
  if (index < 0 || index >= this.length) return
  // 如果想要移除最尾端的節點，改呼叫 pop
  if (index === this.length - 1) return this.pop()
  // 如果是指定依開始的節點，則使用 shift 方法
  if (index === 0) return this.shift()
  // 找到指定節點與它的前一個節點
  const prevNode = this.get(index - 1)
  const removedNode = prevNode.next
  // 將前一個節點的 next 指向指定節點的下個節點
  prevNode.next = removedNode.next
  this.length--
  return removedNode.val
}

### `reverse()`
將串列中所有節點的先後順序倒轉，最後回傳串列本身
較難實作的題目，因為每個節點只有 next 屬性只向下個節點，因此操作比較複雜

reverse () {
  // 先將頭尾對調
  const tail = this.tail
  this.tail = this.head
  this.head = tail
  // 這邊是設定從結尾(原本的頭)開始
  // 新建 prev，起始值為 null，代表(舊的)前一個節點
  let curr = this.tail
  let prev = null
  let oldNext
  while (curr !== null) {
    // 先將原先的下個節點用 oldNext 儲存起來，避免操作變數時覆蓋過去
    oldNext = curr.next
    // 改變 curr 的下一個節點為 prev
    curr.next = prev
    // 將 curr 變成 prev，oldNext 變為下一個 curr，下面一位～
    prev = curr
    curr = oldNext
  }
  return this
}