Singly LinkedList 隨筆


Javascript Algorithems and Data Structures Masterclass

基本結構

首先,建立兩個class,第一個稱Node,第二個是Singly LinkedList主要這支程式運作的地方。Node在初次建立時會產生兩個屬性,val存取值,next存取其他節點的位置。Singly LinkedList在初次建立時則有三個屬性,length紀錄鏈上的總節點數,head存取頭端節點位置,tail存取尾端節點位置。

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

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

push & pop

  push(val){
    let newNode = new Node(val)  // 建立一個新節點
    if(!this.head) {             // 初始化 singly linkedList
      this.head = newNode
      this.tail = this.head
    } else {
      this.tail.next = newNode // 新節點指給第一個或前一個節點
      this.tail = newNode      // 尾端移到最後的位子(也就是新節點上)
    }
      this.length++
      return this
  }

  pop() {
    if(!this.head) return undefined  // 在還沒push前
    let current = this.head
    let newTail = current
    while(current.next) { // 從頭開始拜訪每一個節點直到null
      newTail = current
      current = current.next
    }
    this.tail = newTail
    this.tail.next = null
    this.length--
    if(this.length === 0) { // 沒有這條判斷length會變負的
      this.head = null
      this.tail = null
    }
    return current
  }

unshift & shift

 shift() { 
    if(!this.head) return undefined
    let current = this.head  
    this.head = this.head.next  // 將頭端的位置移往下一個節點
    this.length--
    if(this.length === 0) this.tail = null //optimize shift
    return  current
  }

  unshift(val){  
    let newNode = new Node(val)
    if(!this.head) {  
      this.head = newNode
      this.tail = this.head
    } else { 
      newNode.next = this.head
      this.head = newNode 
    }
    this.length++
    return this
  }

get & set

  get(index) {
    if(index >= this.length || index < 0 ) return undefined
    let count = 0
    let current = this.head
    while(count < index) {
      current = current.next
      count++
    }
    return current
  }

  set(index, val) {
    let current = this.get(index)
    if(!current) {
      return undefined
    }else {
      return current.val = val
    }
  }

insert & remove

  insert(index, val){
    if(index < 0 || index > this.length) {
      return false
    }
    else if(index === 0){
      return !!this.unshift(val) // !! double exclamation point, bang bang
    }
    else if(index === this.length) {
      return !!this.push(val)
    }
    else {
      let newNode = new Node(val)  // NodeC
      let prev = this.get(index-1) // get "NodeA" -> NodeB
      newNode.next = prev.next     // NodeC -> NodeB
      prev.next = newNode          // NodeA -> NodeC
      this.length++
      return true
    }
  }

  remove(index) {
    if(index < 0 || index >= this.length) { // 注意edge case 和insert不一樣
      return false
    }
    else if(index === 0) {
      return this.shift()
    }
    else if(index === this.length -1) { // 注意edge case 和insert不一樣
      return this.pop()
    }
    else {
      let prev = this.get(index-1) // get "NodeA" -> NodeB
      let rmNode = prev.next       // NodeB
      prev.next = rmNode.next      // NodeA -> NodeC
      this.length--
      return rmNode
    }
  }

reverse

  reverse(){
    if(this.length < 2) return false
    let current = this.head
    this.head = this.tail
    this.tail = current
    let next
    let prev = null

    for(let i = 0; i < this.length; i++) {
      next = current.next
      current.next = prev // 讓它指向null
      prev = current
      current = next
    }
    return this
  }
#Singly Linkedlist #data structure #Reverse #javascript





個人學習筆記

留言討論