Data structures implemented in JS

README.md

Data structures implemented in JS

heap.js

class Heap {
  constructor(comparator = (a, b) => a - b) {
    this._array = []
    this._comparator = comparator
  }

  push(obj) {
    this._array.push(obj)
    this._heapifyUp(this.size - 1)
  }

  pop() {
    if (this.empty) {
      return null
    }

    if (this.size === 1) {
      return this._array.pop()
    }

    var root = this._array[0]
    this._array[0] = this._array.pop()

    this._heapifyDown(0)

    return root
  }

  peek() {
    return this._array[0] || null
  }

  get size() {
    return this._array.length
  }

  get empty() {
    return this.size === 0
  }

  _getLeftIndex(idx) {
    return 2 * idx + 1
  }

  _getRightIndex(idx) {
    return 2 * idx + 2
  }

  _getParentIndex(idx) {
    return Math.floor((idx - 1) / 2)
  }

  _swap(i, j) {
    [this._array[i], this._array[j]] = [this._array[j], this._array[i]]
  }

  _heapifyDown(idx) {
    if (idx >= this.size) {
      return
    }

    var l = this._getLeftIndex(idx)
    var r = this._getRightIndex(idx)

    var refIdx = l

    if (r < this.size && this._comparator(this._array[r], this._array[l]) > 0) {
      refIdx = r
    }

    if (this._comparator(this._array[refIdx], this._array[idx]) > 0) {
      this._swap(idx, refIdx)

      this._heapifyDown(refIdx)
    }
  }

  _heapifyUp(idx) {
    if (idx === 0) {
      return
    }
    
    var parentIdx = this._getParentIndex(idx)

    if (this._comparator(this._array[idx], this._array[parentIdx]) > 0) {
      this._swap(idx, parentIdx)

      this._heapifyUp(parentIdx)
    }
  }
}

linked-list.js

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

class LinkedList {
  constructor() {
    this._head = null
    this._size = 0
  }

  insertHead(val) {
    return this.insertAt(0, val)
  }

  insertTail(val) {
    return this.insertAt(this._size, val)
  }

  insertAt(i, val) {
    if (i > this._size) {
      return
    }

    if (i === 0) {
      this._head = new Node(val, this._head)
      this._size++
      return
    }

    var node = this._head

    for (var j = 0; j < i - 1; j++) {
      node = node?.next
    }

    node.next = new Node(val, node.next)

    this._size++
  }

  removeHead() {
    return this.removeAt(0)
  }

  removeTail() {
    return this.removeAt(this._size - 1)
  }

  removeAt(i) {
    if (i >= this.size) {
      return
    }

    var node = this._head
    var prev = null

    for (var j = 0; j < i; j++) {
      prev = node
      node = node?.next
    }

    if (prev === null) {
      this._head = node?.next
    } else {
      prev.next = node?.next
    }
  }

  get head() {
    return this._head
  }

  toArray() {
    var arr = []

    var node = this._head

    while (node !== null) {
      arr.push(node.val)
      node = node.next
    }

    return arr
  }

  get empty() {
    return this._size === 0
  }

  get size() {
    return this._size
  }
}