Data Structures with JavaScript

11 min readMay 8, 2020

A Day with JavaScript Data Structures - Milestone 2 (Week 2)

Today we will briefly discuss some basic data structures of JavaScript. We will be covering - Stack, Queue, Linked List, Hash Table, and Binary Search Tree and their implementations. So, let’s get into the article.

1. Data Structures?

Data structures are techniques for storing and organizing data that make it easier to modify, navigate, and access. Data structures determine how data is collected, the functions we can use to access it, and the relationships between data.

Data Structures in JavaScript

JavaScript has two types of data structures -

i) Primitive

ii) Non-primitive

i) Primitive data structures

Javascript has some native data structures, we call them Primitive data structures. Those are:

boolean, null, number, string

i) Non-primitive data structures

JavaScript also includes some non-primitive or user-defined data structures. These data structures are not defined by the programming language, which means these are not built-in. Some non-primitive or user-defined data structures in JavaScript are:

linear data structures, static data structures, and dynamic data structures, like queue and linked lists.

2. Stack

Stacks are dynamic data structures that follow the Last In First Out (LIFO) principle. The last item to be inserted into a stack is the first one to be deleted from it.

For example, you have a stack of trays on a table. The tray at the top of the stack is the first item to be moved if you require a tray from that stack.

3. Implementing Stack with JavaScript

Basically a stack in data structure has three basic operations:

push
pop
peek

Here’s an implementation of Stack with JavaScript:

class Stack {
  constructor() {
    // create our stack, which is an empty object
    this.stack = {}
  }
  // this method will push a value onto the top of our stack
  push(value) {

  }
  // this method is responsible for popping off the last value and returning it
  pop() {

  }

  // this will peek at the last value added to the stack
  peek() {

  }
}

push() method

class Stack {
  constructor() {
    this._storage = {};
    this._length = 0; // this is our length 
  }

  push(value) {
    // so add the value to the top of our stack
    this._storage[this._length] = value;
    // since we added a value, we should also increase the length by 1
    this._length++;
  }
  /// .....
}

pop() method

class Stack {
  constructor() {
    this._storage = {};
    this._length = 0;
  }
  
  pop() {
    const lastValIndex = this._length - 1;
    if (lastValIndex >= 0) {
      // we first get the last val so we have it to return
      const lastVal = this._storage[lastValIndex];
      // now remove the item which is the length - 1
      delete this._storage[lastValIndex];
      // decrement the length
      this._length--;
      // now return the last value
      return lastVal;
    }
    return false;
  }
}

peek() method

class Stack {
  constructor() {
    this._storage = {};
    this._length = 0;
  }
  
  peek() {
    const lastValIndex = this._length - 1;
    const lastVal = this._storage[lastValIndex];
    return lastVal;
  }
}

4. Queue

Queues are data structures that follow the First In First Out (FIFO) i.e. the first element that is added to the queue is the first one to be removed.

Elements are always added to the back and removed from the front. Think of it as a line of people waiting for a bus. The person who is at the beginning of the line is the first one to enter the bus.

5. Implementing Queue with JavaScript

A Queue basically has three operations:

enqueue
dequeue
peek

Here’s an implementation of Queue with JavaScript:

class Queue {
  constructor() {
    // array to hold our values
    this.queue = [];
    // length of the array - could also track this with queue.length
    this.length = 0;
  }

  enqueue(value) {
   
  }

  dequeue() {
    
  }
  
  peek() {
    
  }
}

enqueue() method

enqueue(value) {
  // add the value to the start of the queue
  this.queue.unshift(value);
  // update our length
  this.length++;
}

dequeue() method

dequeue() {
  // if we have any values
  if (this.length > 0) {
    // pop off the value that was added first
    this.queue.pop();
    // decrement the length
    this.length--;
  }
}

peek() method

peek() {
  const lastValIndex = this.length - 1;
  if (lastValIndex >= 0) {
    return this.queue[lastValIndex];
  }
  return false;
}

6. Linked list

A linked list is a way to store a collection of elements. Like an array, these can be character or integers. Each element in a linked list is stored in the form of a node.

Node:
A node is a collection of two sub-elements or parts. A data part that stores the element and a next part that stores the link to the next node.

Linked List:
A linked list is formed when many such nodes are linked together to form a chain. Each node points to the next node present in the order. The first node is always used as a reference to traverse the list and is called HEAD. The last node points to NULL.

7. Implementing Linked list with JavaScript

In the data structure, a Linked list basically has the following operations:

node
list of linked data
inserting data
removing data (from the specific index)
clearing the list

Here’s an implementation of Queue with JavaScript:

Node Class

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

LinkedList Class

class LinkedList {
  constructor() {
    this.head = null;
    this.size 0;
  }
}

insert() method

// insert will add to the end of our linked list
insert(data) {
  // create a node object using the data passed in
  let node = new Node(data);
  let current;
  // if we don't have a head, we make one
  if (!this.head) {
    this.head = node;
  } else {
    // if there is already a head, then we add a node to our list
    current = this.head;
    // loop until the end of our linked list (the node with no next value)
    while (current.next) {
      current = current.next;
    }
    // set the next value to be the current node
    current.next = node;
  }
  // increment the size
  this.size++;
}

removeAt() method

// Remove at index
  removeAt(index) {
    // check if index is a positive number and index isn't too large
    if (index > 0 && index > this.size) {
      return;
    }
    // start at our head
    let current = this.head;
    // keep a reference to the previous node
    let previous;
    // count variable
    let count = 0;
    // if index is 0, then point the head to the item second (index 1) in the list
    if (index === 0) {
      this.head = current.next;
    } else {
      // loop over the list and 
      while (count < index) {
        // first increment the count
        count++;
        // set previous to our current node
        previous = current;
        // now set our current node to the next node
        current = current.next;
      }
      // update the next pointer of our previous node to be the next node
      previous.next = current.next;
    }
    // since we removed a node we decrement, the size by 1
    this.size--;
  }

clearList() method

clearList() {
  this.head = null;
  this.size = 0;
}

8. Hash table

Hashing is a technique that is used to uniquely identify a specific object from a group of similar objects. Some examples of how hashing is used in our lives include:

i) In universities, each student is assigned a unique roll number that can be used to retrieve information about them.
ii) In libraries, each book is assigned a unique number that can be used to determine information about the book, such as its exact position in the library or the users it has been issued to, etc.

In both these examples, the students and books were hashed to a unique number.

Assume that we have an object and we want to assign a key to it to make searching easy. To store the key/value pair, we can use a simple array like a data structure where keys (integers) can be used directly as an index to store values. However, in cases where the keys are large and cannot be used directly as an index, we should use hashing.

What is Hash Table?

A hash table is a data structure that implements an associative array, which means it maps keys to values. A JavaScript object is a hash table, as it stores key-value pairs.

What is Hash Function?

A hash function is any function that can be used to map a data set of an arbitrary size to a data set of a fixed size, which falls into the hash table. The values returned by a hash function are called hash values, hash codes, hash sums, or simply hashes.

To achieve a good hashing mechanism, It is important to have a good hash function with the following basic requirements:

Easy to compute: It should be easy to compute and must not become an algorithm in itself.
Uniform distribution: It should provide a uniform distribution across the hash table and should not result in clustering.
Less collisions: Collisions occur when pairs of elements are mapped to the same hash value. These should be avoided.

9. Implementing Hash table with JavaScript

A Hash table in JavaScript need three operations:

insert
get
remove

Here’s an implementation of Hash table with JavaScript:

class HashTable {
  constructor(size) {
    // define the size of our hash table, which will be used in our hashing function
    this.size = size;
    this.storage = [];
  }
  insert(key, value) { }
  get() {}
  remove() {}
  // this is how we will hash our keys
  myHashingFunction(str, n) {
    let sum = 0;
    for (let i = 0; i < str.length; i++) {
      sum += str.charCodeAt(i) * 3;
    }
    return sum % n;
  }
}

insert() method

insert(key, value) {
  // will give us an index in the array
  const index = this.myHashingFunction(key, this.size);
  // handle collision - hash function returns the same
  // index for a different key - in complicated hash functions it is very unlikely
  // that a collision would occur
  if (!this.storage[index]) {
    this.storage[index] = [];
  }
  // push our new key value pair
  this.storage[index].push([key, value]);
}

if we call the insert method:

const myHT = new HashTable(5);
myHT.insert(“a”, 1);
myHT.insert(“b”, 2);

we will get the following output:

remove() method

remove(key) {
    // first we get the index of our key
    // remember, the hashing function will always return the same index for the same
    // key
    const index = this.myHashingFunction(key, this.size);
    // remember we could have more than one array at an index (unlikely)
    let arrayAtIndex = this.storage[index];
    if (arrayAtIndex) {
      // let's loop over all the arrays at that index
      for (let i = 0; i < arrayAtIndex.length; i++) {
        // get the pair (a, 1)
        let pair = arrayAtIndex[i];
        // check if the key matches the key param
        if (pair[0] === key) {
          // delete the arrayatindex
          delete arrayAtIndex[i];
          // job done, so break out of the loop
          break;
        }
      }
    }
}

get() method

get(key) {
    const index = this.myHashingFunction(key, this.size);
    let arrayAtIndex = this.storage[index];
    if (arrayAtIndex) {
      for (let i = 0; i < arrayAtIndex.length; i++) {
        const pair = arrayAtIndex[i];
        if (pair[0] === key) {
          // return the value
          return pair[1];
        }
      }
    }
  }

10. Binary Search Tree

What is Tree?
Trees are a relation-based data structure, which specializes in representing hierarchical structures. Like a linked list, nodes contain both elements of data and pointers marking its relation to immediate nodes.

What is Binary Search Tree?
Binary search trees sometimes called ordered or sorted binary trees, are a particular type of container: a data structure that stores “items” in memory.

A binary search tree includes the following terms:

Root: This is the very top node of a tree structure and does not have a parent
Parent: It is a child of a node but also the parent of a node
Child: This node is the child of a node and does not necessarily have a child

In a binary search tree, each node either has zero, one, or two children. The child on the left is called the left child, and the child on the right is the right child. In a binary search tree, the child on the left must be smaller than the child on the right.

Implementing BST with JavaScript

We will use the following terms to implement a Binary Search Tree with JavaScript:

Tree
Node
root
left
right
add
current
contains

Tree Class

class Tree {
   constructor(value) {
     this.root = null
   }

   add(value) {
    // we'll implement this below
   }

}

Node Class

class Node {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

add() method

add(value) {
    // if we do not have a root, then we create one
    if (this.root === null) {
      this.root = new Node(value);
      return;
    }
    let current = this.root;
    // keep looping
    while (true) {
      // go left if our current value is greater
      // than the value passed in
      if (current.value > value) {
        // if there is a left child, then run the
        // loop again
        if (current.left) {
          current = current.left;
        } else {
          current.left = new Node(value);
          return;
        }
      }
      // the value is smaller, so we go right
      else {
        // go right
        // if there is a left child, then run the
        // loop again
        if (current.right) {
          current = current.right;
        } else {
          current.right = new Node(value);
          return;
        }
      }
    }
}

if we call the add() method,

const t = new Tree();
t.add(2);
t.add(5);
t.add(3);

we will get the following output

contains() method

contains(value) {
  // get the root
  let current = this.root;
  // while we have a node
  while (current) {
    // check if our current node has the value
    if (value === current.value) {
      return true; // leave the function
    }
    // we decide on the next current node by comparing our value
    // against current.value - if its less go left else right
    current = value < current.value ? current.left : current.right;
  }
  return false;
}