[筆記] Master The Coding Interview – 9 @地瓜大的飛翔旅程

章節連結

課程相關資訊
內容
範例程式碼
相關文章

這篇是 Udemy 上的知名課程 – Master the Coding Interview 的部分進修心得。這篇對應的內容是「Data Structures: Linked Lists」關於鏈結陣列的第三部分簡介。

課程對應章節：103~106

請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。

內容

Doubly Linked Lists：讓鏈結陣列得以反向進行遍歷，也因此需要多一個連結指向前一個
single linked lists 的缺點就是沒辦法由後往前遍歷，但比較省記憶體
整體而言，Linked List 因為具有 Index 且照一定順序排列，所以要 insert , delete 等操作都會比較快速

範例程式碼

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

class DoublyLinkedList{
  constructor(value){
    this.head = {
      value: value,
      next: null,
      prev: null
    }
    this.tail = this.head;
    this.length = 1;
  }
  append(value){
    const newNode = new Node(value)
    newNode.prev = this.tail;
    this.tail.next = newNode /*將原本的 this.head 內的 pointer 改掉*/
    this.tail = newNode /*把 tail 更新成 newNode*/
    this.length ++
    return this
  }
  prepend(value){
    const newNode = new Node(value)
    newNode.next = this.head
    this.head.prev = newNode
    this.head = newNode
    this.length++
    return this
  }
  printList(){
    const array = []
    let currentNode = this.head
    while(currentNode !== null){
      array.push(currentNode.value)
      currentNode = currentNode.next
    }
    return array
  }
  insert(index, value){
    if(index >= this.length){
      return this.append(value)
    }
    if(index === 0){
      this.prepend(value)
      return this.printList()
    }
    const newNode = new Node(value)
    const pre = this.traverseToIndex(index-1) /*找到 insert 前一個*/
    const follower = pre.next /*將原先的下一個留下來*/
    pre.next = newNode /*將原先的下一個替換成新的 Node*/
    newNode.prev = pre
    newNode.next = follower
    follower.prev = newNode
    this.length++
  }
  remove(index){
    const pre = this.traverseToIndex(index-1) /*找到 delete 前一個*/
    const removedOne = pre.next
    pre.next = removedOne.next
    this.length--
    return this.printList()
  }
  traverseToIndex(index){
    let counter = 0
    let currentNode = this.head
    while(counter !== index){
      currentNode = currentNode.next
      counter++
    }
    return currentNode
  }
}

const myLinkedList = new DoublyLinkedList(10);
myLinkedList.append(6);
myLinkedList.append(12)
myLinkedList.prepend(1)
myLinkedList.printList()
myLinkedList.insert(2,99)
myLinkedList.printList()
myLinkedList.insert(888,100)
myLinkedList.printList()
myLinkedList.remove(2)

class Node{

constructor(value){

this.value = value

this.next = null

this.prev = null

}

class DoublyLinkedList{

constructor(value){

this.head = {

value: value,

next: null,

prev: null

}

this.tail = this.head;

this.length = 1;

}

append(value){

const newNode = new Node(value)

newNode.prev = this.tail;

this.tail.next = newNode /*將原本的 this.head 內的 pointer 改掉*/

this.tail = newNode /*把 tail 更新成 newNode*/

this.length ++

return this

}

prepend(value){

const newNode = new Node(value)

newNode.next = this.head

this.head.prev = newNode

this.head = newNode

this.length++

return this

}

printList(){

const array = []

let currentNode = this.head

while(currentNode !== null){

array.push(currentNode.value)

currentNode = currentNode.next

}

return array

}

insert(index, value){

if(index >= this.length){

return this.append(value)

}

if(index === 0){

this.prepend(value)

return this.printList()

}

const newNode = new Node(value)

const pre = this.traverseToIndex(index-1) /*找到 insert 前一個*/

const follower = pre.next /*將原先的下一個留下來*/

pre.next = newNode /*將原先的下一個替換成新的 Node*/

newNode.prev = pre

newNode.next = follower

follower.prev = newNode

this.length++

}

remove(index){

const pre = this.traverseToIndex(index-1) /*找到 delete 前一個*/

const removedOne = pre.next

pre.next = removedOne.next

this.length--

return this.printList()

}

traverseToIndex(index){

let counter = 0

let currentNode = this.head

while(counter !== index){

currentNode = currentNode.next

counter++

}

return currentNode

}

const myLinkedList = new DoublyLinkedList(10);

myLinkedList.append(6);

myLinkedList.append(12)

myLinkedList.prepend(1)

myLinkedList.printList()

myLinkedList.insert(2,99)

myLinkedList.printList()

myLinkedList.insert(888,100)

myLinkedList.printList()

myLinkedList.remove(2)