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

章節連結

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

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

課程對應章節：94~99

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

內容

延續上篇的內容，將 node 的生成獨立成一個 class，並加上 insert 、remove 和 reverse 方法。

範例程式碼

/*若要打造一個 1 -> 10 -> 6 -> 12 的 Linked Lists*/
/*ES6 寫法*/
class Node{
  constructor(value){
    this.value = value
    this.next = null
  }
}

class LinkedList{
  constructor(value){
    this.head = {
      value: value,
      next: null
    }
    this.tail = this.head;
    this.length = 1;
  }
  append(value){
    const newNode = new Node(value)
    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 = 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 holdingPointer = pre.next /*將原先的下一個留下來*/
    pre.next = newNode /*將原先的下一個替換成新的 Node*/
    newNode.next = holdingPointer
    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
  }
  reverse(){
    if(!this.head.next) return this.head;
    let first = this.head /*從頭取出第一個 Node*/
    this.tail = this.head /*把原先第一個存到最後*/
    let second = first.next /*把原先 1st 的指向取出*/
    while(second){
      const temp = second.next /*把原先 3rd 指向 取出*/
      second.next = first /*原先 2nd 指向第一個*/
      first = second /*原先 1st, 2nd 互換*/
      second = temp 
    }
    this.head.next = null
    this.head = first
    return this
  }
}

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

100

101

/*若要打造一個 1 -> 10 -> 6 -> 12 的 Linked Lists*/

/*ES6 寫法*/

class Node{

constructor(value){

this.value = value

this.next = null

}

class LinkedList{

constructor(value){

this.head = {

value: value,

next: null

}

this.tail = this.head;

this.length = 1;

}

append(value){

const newNode = new Node(value)

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 = 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 holdingPointer = pre.next /*將原先的下一個留下來*/

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

newNode.next = holdingPointer

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

}

reverse(){

if(!this.head.next) return this.head;

let first = this.head /*從頭取出第一個 Node*/

this.tail = this.head /*把原先第一個存到最後*/

let second = first.next /*把原先 1st 的指向取出*/

while(second){

const temp = second.next /*把原先 3rd 指向取出*/

second.next = first /*原先 2nd 指向第一個*/

first = second /*原先 1st, 2nd 互換*/

second = temp

}

this.head.next = null

this.head = first

return this

}

const myLinkedList = new LinkedList(10);

myLinkedList.append(6);

myLinkedList.append(12)

myLinkedList.prepend(1)

myLinkedList.printList()

myLinkedList.insert(2,99)

myLinkedList.insert(888,100)

myLinkedList.printList()

myLinkedList.remove(2)

myLinkedList.printList()

myLinkedList.reverse()

myLinkedList.printList()