Algorithm and Data Structure

Dive into the Power of JavaScript Algorithm and Data Structure

JavaScript is one of the most widely-used programming languages in the world of web development. It is a powerful and versatile language that enables developers to create dynamic and interactive websites and applications. As a developer, it is important to understand the fundamental concepts of data structures and algorithms to write clean, efficient and effective code. In this blog, we will dive into the power of JavaScript algorithm and data structure and how they can be used in your development.

Big O

• Time complexity
• Space complexity
  • Variables
  • Data Structures
  • Function Call
  • Allocations
• Readable
• What causes Space complexity ?
  • Variables
  • Data Structures
  • Function Call
  • Allocations

How to solve problems

• Analytic Skills
• Coding Skills
• Technical Skills
• Communication Skills

Data Structure

• Arrays
• Stacks
• Queues
• Linked Lists
• Trees
• Tries
• Graphs
• Hash Tables

Algorithms

• Sorting
• Dynamic Programming
• BFS + DFS (Searching)
• Recursion

Array

• push() O(1)

• pop() O(1)

• unshift() O(n)

• splice() O(n/2) --> O(n)

• Static VS. Dynamic Arrays

• Classes in JavaScript

  • reference type
  • context vs scope
  • instantiation

• class Player {
    constructor(name, type) {
      this.name = name
      this.type = type
    }
    introduce() {
      console.log(`Hi ${this.name}, ${this.type}`)
    }
  }
  
  class Wizard extends Player {
    constructor(name, type) {
      super(name, type)
    }
    play() {
      console.log(`Hello ${this.type}`)
    }
  }
  
  const wizard1 = new Wizard('Fangtai', 'Healer')
  

• Classical Inheritance

• const Player = function (name, type) {
    this.name = name
    this.type = type
  }
  
  Player.prototype.introduce = function () {
    console.log(`Hi ${this.name}, ${this.type}`)
  }
  
  const wizard1 = new Player('Fangtai', 'Healer')
  const wizard2 = new Player('David', 'Dark Magic')
  
  wizard1.play = function () {
    console.log(`Hello ${this.type}`)
  }
  
  wizard2.play = function () {
    console.log(`Hello ${this.type}`)
  }
  

• Implementing An Array

String Question

• Turn it into an Array question ~ Split()

• Reversing String

• const reverse3 = (str) => [...str].reverse().join('')
  

Hash Table

• Hash function (md5 Hash Generator)

• Collision

• How to use Linked List to solve Collision?

• class HashTable {
    constructor(size) {
      this.data = new Array(size)
    }
  
    hashMethod(key) {
      // Implement the hash function
    }
  
    set(key, value) {
      let index = this.hashMethod(key)
      if (!this.data[index]) {
        this.data[index] = []
      }
      this.data[index].push([key, value])
    }
  
    get(key) {
      let index = this.hashMethod(key)
      const currentBucket = this.data[index]
      if (currentBucket) {
        for (let i = 0; i < currentBucket.length; i++) {
          if (currentBucket[i][0] === key) {
            return currentBucket[i][1]
          }
        }
      }
      return undefined
    }
  
    // Other methods...
  }
  

Linked List

• Singly linked lists

• Doubly linked lists

• head

• pointer: a reference to something else in memory

• tail

• null In JavaScript, a linked list is a commonly used data structure. It consists of a series of nodes, each of which contains a data part and a reference to the next node. Linked lists are particularly suitable for those that require frequent insertion and deletion operations, because these operations are usually more efficient on linked lists than arrays.

• The following is a simple example of JavaScript implementing a one-way linked list.

• class ListNode {
    constructor(value) {
      this.value = value
      this.next = null
    }
  }
  
  class LinkedList {
    constructor() {
      this.head = null
    }
  
    // Add nodes to the head of the linked list
    addFirst(value) {
      const newNode = new ListNode(value)
      newNode.next = this.head
      this.head = newNode
    }
  
    // Add nodes at the end of the linked list
    addLast(value) {
      const newNode = new ListNode(value)
      if (!this.head) {
        this.head = newNode
        return
      }
      let current = this.head
      while (current.next) {
        current = current.next
      }
      current.next = newNode
    }
  
    // Find the node
    find(value) {
      let current = this.head
      while (current) {
        if (current.value === value) {
          return current
        }
        current = current.next
      }
      return null
    }
  
    // Delete the node
    delete(value) {
      if (!this.head) return
  
      if (this.head.value === value) {
        this.head = this.head.next
        return
      }
  
      let current = this.head
      while (current.next) {
        if (current.next.value === value) {
          current.next = current.next.next
          return
        }
        current = current.next
      }
    }
  
    // Print the linked list
    print() {
      let current = this.head
      while (current) {
        console.log(current.value)
        current = current.next
      }
    }
  }
  

• Doubly Linked List

• class DoublyListNode {
    constructor(value) {
      this.value = value
      this.next = null
      this.prev = null
    }
  }
  
  class DoublyLinkedList {
    constructor() {
      this.head = null
      this.tail = null
    }
  
    // Add nodes at the head of the linked list
    addFirst(value) {
      const newNode = new DoublyListNode(value)
      if (!this.head) {
        this.head = newNode
        this.tail = newNode
      } else {
        newNode.next = this.head
        this.head.prev = newNode
        this.head = newNode
      }
    }
  
    // Add nodes at the end of the linked list
    addLast(value) {
      const newNode = new DoublyListNode(value)
      if (!this.tail) {
        this.head = newNode
        this.tail = newNode
      } else {
        newNode.prev = this.tail
        this.tail.next = newNode
        this.tail = newNode
      }
    }
  
    // Delete the node
    delete(value) {
      let current = this.head
      while (current) {
        if (current.value === value) {
          if (current.prev) {
            current.prev.next = current.next
          } else {
            this.head = current.next
          }
          if (current.next) {
            current.next.prev = current.prev
          } else {
            this.tail = current.prev
          }
          return
        }
        current = current.next
      }
    }
  
    // Print the linked list (from beginning to end)
    printForward() {
      let current = this.head
      while (current) {
        console.log(current.value)
        current = current.next
      }
    }
  
    // Print the linked list (from end to end)
    printBackward() {
      let current = this.tail
      while (current) {
        console.log(current.value)
        current = current.prev
      }
    }
  }
  

• How to reverse Linked List

• For Singly Linked List

• class ListNode {
    constructor(value) {
      this.value = value
      this.next = null
    }
  }
  
  class LinkedList {
    constructor() {
      this.head = null
    }
  
    // ... Other methods...
  
    reverse() {
      let prev = null
      let current = this.head
      let next = null
  
      while (current) {
        next = current.next // Save the next node
        current.next = prev // Revers the pointer
        prev = current // prev move forward
        current = next // current moving forward
      }
  
      this.head = prev // Reset the header node
    }
  }
  

Stack and Queue

• Stack: FILO
  • Stack is a data structure of last-in-first-out (LIFO). In the stack, the last added element will be removed first. The two main operations of the stack are:
    • Push: Add an element to the top of the stack.
    • Pop: Remove the elements at the top of the stack. In JavaScript, it is easy to implement a stack using array push and pop methods.

• let stack = []
  stack.push(1) // The stack is now [1]
  stack.push(2) // The stack is now [1, 2]
  stack.push(3) // The stack is now [1, 2, 3]
  stack.pop() // Back 3, the stack is now [1, 2]
  

• Queue: FIFO
  • Queue is a first-in-first-out (FIFO) data structure. In the queue, the first element added will be removed first. The two main operations of the queue are:
    • Enqueue: Add an element at the end of the queue.
    • Dequeue: Remove the first element of the queue. In JavaScript, you can use the push method of the array to add elements, and use the shift method to remove elements at the front end of the queue.

• let queue = []
  queue.push(1) // The queue is now [1]
  queue.push(2) // The queue is now [1, 2]
  queue.push(3) // The queue is now [1, 2, 3]
  queue.shift() // Return 1, the queue is now [2, 3]
  

Tree

• Binary Tree

• Definition: Binary Tree is a tree data structure in which each node has at most two child nodes (0, 1, 2), commonly known as "left child node" and "right child node". The characteristic of the binary tree is that its structure allows for quick search, insertion and deletion operations.

• Features:

  • Order: Binary tree can be ordered. In this case, it is often called a binary search tree (BST). In BST, the value of the left child node is less than the value of its parent node, and the value of the right child node is greater than the value of its parent node.
  • Dynamic structure: Binary tree is a dynamic data structure that can efficiently insert and delete data.
  • Recursiveness: Each subtree of a binary tree is also a binary tree, which makes many binary tree algorithms based on recursion.
  • Imbalance: If it is not managed, the binary tree may become unbalanced and degenerate into a linked list in extreme cases, resulting in performance degradation.
  • Spatial efficiency: Compared with other linear data structures such as arrays, binary trees are usually more space-saving when storing hierarchical data.

• class BinaryTreeNode {
    constructor(value) {
      this.value = value
      this.left = null
      this.right = null
    }
  }
  
  class BinaryTree {
    constructor() {
      this.root = null
    }
  
    // Insert operation
    insert(value) {
      const newNode = new BinaryTreeNode(value)
  
      if (this.root === null) {
        this.root = newNode
      } else {
        this._insertNode(this.root, newNode)
      }
    }
  
    // Recursive insertion node
    _insertNode(node, newNode) {
      if (newNode.value < node.value) {
        if (node.left === null) {
          node.left = newNode
        } else {
          this._insertNode(node.left, newNode)
        }
      } else {
        if (node.right === null) {
          node.right = newNode
        } else {
          this._insertNode(node.right, newNode)
        }
      }
    }
  
    // Other operations, such as searching, traversing, etc.
  }
  

• About O(log n)