Doubly Linked List

Singly Linked List 與 Doubly Linked List 差別在 Node 的指標一個只有下一個節點，另個有存上下兩個節點。

Doubly Linked List 中的節點有雙向指標 (prev、next)。

Singly Linked List: 15 -> 133 -> 5 -> -1 -> 0 -> 439 (單向)

Doubly Linked List: 15 <-> 133 <-> 5 <-> -1 <-> 0 <-> 439 (雙向)

Implementation

接著就照上面定義來實作。

class Node {
  constructor(val) {
    this.val = val
    this.next = null
    this.prev = null
  }
}

class DoublyLinkedList {
  constructor(val) {
    this.head = null
    this.tail = null
    this.length = 0
  }
}

也因為每個 Node 都有上下兩個指標，所以相關操作方法也都要做調整。

Push

push(val) {
  const node = new Node(val)
  if (this.length === 0) {
    this.head = node
    this.tail = node
  } else {
    this.tail.next = node
    node.prev = this.tail
    this.tail = node
  }
  this.length++
  return this
}

Pop

在移除 Node 時，也要把跟此 Node 的兩個指標都改成 null 避免此 Node 還能與其他 Node 有關聯。

pop() {
  if (this.length === 0) return undefined
  const popedNode = this.tail
  if (this.length === 1) {
    this.head = null
    this.tail = null
  } else {
    this.tail = popedNode.prev
    this.tail.next = null
    popedNode.prev = null
  }
  this.length--
  return popedNode
}

Shift

實作上和 Pop 幾乎一樣，差別在於方向而已。

shift() {
  if (this.length === 0) return undefined
  const shiftedNode = this.head
  if (this.length === 1) {
    this.head = null
    this.tail = null
  } else {
    this.head = shiftedNode.next
    this.head.prev = null
    shiftedNode.next = null
  }
  this.length--
  return shiftedNode
}

Unshift

unshift(val) {
  const node = new Node(val)
  if (this.length === 0) {
    this.head = node
    this.tail = node
  } else {
    this.head.prev = node
    node.next = this.head
    this.head = node
  }
  this.length++
  return this
}

Get

由於 Doubly Linked List 中的節點都是雙向綁定，故在需要遍歷整個 List 時，可以根據給定的 Index 來決定是要從頭遍歷還是從最後面開始遍歷。

get(index) {
  if (index < 0 || index >= this.length) return null
  let currentNode = null
  if (index <= this.length / 2) {
    currentNode = this.head
    while (index > 0) {
      currentNode = currentNode.next
      index--
    }
  } else {
    currentNode = this.tail
    while (this.length - index > 1) {
      currentNode = currentNode.prev
      index--
    }
  }
  return currentNode
}

Set

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

Insert

insert(index, val) {
  if (index < 0 || index > this.length) return false
  if (index === 0) return !!this.unshift(val)
  if (index === this.length) return !!this.push(val)
  const newNode = new Node(val)
  const nextNode = this.get(index)
  nextNode.prev.next = newNode
  newNode.prev = nextNode.prev
  nextNode.prev = newNode
  newNode.next = nextNode
  this.length++
  return true
}

Remove

remove(index) {
  if (index < 0 || index >= this.length) return undefined
  if (index === 0) return !!this.shift()
  if (index === this.length - 1) return !!this.pop()
  const targetNode = this.get(index)
  targetNode.prev.next = targetNode.next
  targetNode.next.prev = targetNode.prev
  targetNode.prev = null
  targetNode.next = null
  this.length++
  return true;
}

Reverse

reverse(){
  if (this.length <= 1) return this;

  let currentNode = this.head;
  this.head = this.tail;
  this.tail = currentNode;
  
  while(currentNode) {
    const prevNode = currentNode.prev;
    currentNode.prev = currentNode.next;
    currentNode.next = prevNode;
    currentNode = currentNode.prev;
  }
  
  return this;
}

Big O Complexity

Insertion	Removal	Search	Access
O(1)	O(1)	O(n)	O(n)

實際上 Search 與 Access 是 O(n / 2)，效能上比 Singly Linked List 好。

但也因為 Doubly Linked List 的每個 Node 多存了一個 Prev 指標，因此會需要用多一點的記憶體。