Data Structures Implementation in Javascript Part 1

This blog post will discuss how to implement Array Lists and Hash Tables in Javascript.

Array List

An Array List uses a dynamic array for storing elements. Array Lists are created with an initial size, when this size is exceeded, it gets enlarged automatically. The elements shift whenever an element is deleted. It can contain duplicate elements and the insertion order is maintained.

Array List’s adds and deletes are O(n) and the gets are O(1).

Properties

length — integer — How many elements in the array
push — function — Accepts a value and adds to the end of the list
pop — function — Removes the last value in the list and returns it
get — function — Accepts an index and returns the value at that position
delete — function — Accepts an index, removes value from list, collapses,
and returns removed value

Javascript Implementation

class ArrayList {
  constructor() {
    this.length = 0
    this.data = {}
  }
  push(value) {
    this.data[this.length] = value
    this.length++
  }
  pop() {
    const ans = this.data[this.length-1]
    delete this.data[this.length-1]
    this.length--
    return ans
  }
  get(index) {
    return this.data[index]
  }
  delete(index) {
    const ans = this.data[index]
    this._collapseTo(index)
    return ans
  }
  _collapseTo(index) {
    for (let i = index; i < this.length; i++) {
      this.data[i] = this.data[i+1]
    }
    delete this.data[this.length-1]
    this.length--
  }
  serialize() {
    return this.data
  }
}
let list = new ArrayList()
list.push(1)
list.push(2)
list.push(3)
list.push(4)
console.log(list.get(1))
console.log(list.serialize())
list.pop()
console.log(list.serialize())
list.delete(0)
console.log(list.serialize())

Output

2
{ '0': 1, '1': 2, '2': 3, '3': 4 }
{ '0': 1, '1': 2, '2': 3 }
{ '0': 2, '1': 3 }

Hash Table

A hash table is a data structure that allows you to keep a list of key-value pairs and provides a quick and efficient access to them. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found. Hash functions need to be idempotent, meaning a function given an input always outputs the same output. A good hashing algorithm has a good distribution of values spread out as evenly as possible in order to avoid collisions. Collisions are when something is hashed to an index that was already used in the hash table. The modulo operator (%) is used in the hash function to ensure that the numbers don’t exceed the max size of the hash table.

Hash tables have constant time (O(1)).

Properties

add — function — Takes a string as an input, hashes it, and puts in its table
check — function — Takes a string and returns true if it exists in its table; otherwise returns false
hash — function — Takes a string and a max number and return a number between 0 and the max number. function must be idempotent; the same string and max number will always yield the same output

Javascript Implementation

class HashTable {
  constructor() {
    this.table = new Array(255)
  }
  add(input) {
    this.table[this.hash(input, 255)] = input
  }
  check(input) {
    return !!this.table[this.hash(input, 255)]
  }
  hash(input, max) {
    let num = 0
    for (let i = 0; i < input.length; i++) {
      num += input.charCodeAt(i) * i
    }
    return num % max
  }
}
let hash = new HashTable
hash.add("bob")
hash.add("susan")
hash.add("steve")
console.log(hash.check("bob"))
console.log(hash.check("beth"))

Output

true
false

Thanks for reading!