6 JavaScript data structures you must know

When solving coding problems, efficiency is paramount – from the number of coding hours to runtime, to the amount of memory devoted to a solution. Thankfully, JavaScript developers use many pre-established data structures designed to solve common needs and solve real-world problems. Mastery over data structures is a major factor in marking the difference between a fresh developer and a practiced, hireable veteran.

Maybe you’re just starting out with data structures, or maybe you’ve been coding for years and just need a refresher. Today, we will walk you through the top 6 data structures that any JS developer needs to know.

Here is what we’ll cover today:

What are data structures
1. Array
2. Queues
3. Linked List
4. Trees
5. Graphs
6. Hashtable / map
Data structures interview questions
What to learn next

Ace the front-end interview with hands-on projects.
Review all the key concepts and practice dozens of top interview questions.

Ace the Front End Interview

What are data structures#

Data structures, at a high level, 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 are used in almost all areas of computer science and programming, from operating systems to basic vanilla code to artificial intelligence.

Data structures enable us to:

Manage and utilize large datasets

Search for particular data from a database

Design algorithms that are tailored towards particular programs

Handle multiple requests from users at once

Simplify and speed up data processing

Data structures are vital for efficient, real-world problem solving. After all, the way we organize data has a lot of impact on performance and useability. In fact, most top companies require a strong understanding of data structures.

Anyone looking to crack the coding interview will need to master data structures.

JavaScript has primitive and non-primitive data structures. Primitive data structures and data types are native to the programming language. These include boolean, null, number, string, etc.

Non-primitive data structures are not defined by the programming language but rather by the programmer. These include linear data structures, static data structures, and dynamic data structures, like queue and linked lists.

2. Queues#

Queues are conceptually similar to stacks; both are sequential structures, but queues process elements in the order they were entered rather than the most recent element.

As a result, queues can be thought of as a FIFO (First In, First Out) version of stacks. These are helpful as a buffer for requests, storing each request in the order it was received until it can be processed.

For a visual, consider a single-lane tunnel: the first car to enter is the first car to exit. If other cars should wish to exit, but the first stops, all cars will have to wait for the first to exit before they can proceed.

4. Trees#

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

Each tree has a “root” node, off of which all other nodes branch. The root contains references to all elements directly below it, which are known as its “child nodes”. This continues, with each child node, branching off into more child nodes.

Nodes with linked child nodes are called internal nodes while those without child nodes are external nodes. A common type of tree is the “binary search tree” which is used to easily search stored data.

These search operations are highly efficient, as its search duration is dependent not on the number of nodes but on the number of levels down the tree.

This type of tree is defined by four strict rules:

The left subtree contains only nodes with elements lesser than the root.

The right subtree contains only nodes with elements greater than the root.

Left and right subtrees must also be a binary search tree. They must follow the above rules with the “root” of their tree.

There can be no duplicate nodes, i.e. no two nodes can have the same value.

Advantages

Ideal for storing hierarchical relationships

Dynamic size

Quick at insert and delete operations

In a binary search tree, inserted nodes are sequenced immediately.

Binary search trees are efficient at searches; length is only $O(height)$ .

Disadvantages

Slow to rearrange nodes

Child nodes hold no information about their parent node

Binary search trees are not as fast as the more complicated hash table

Binary search trees can degenerate into linear search (scanning all elements) if not implemented with balanced subtrees.

Enjoying the article? Scroll down to sign up for our free, bi-monthly newsletter.

5. Graphs#

Graphs are a relation-based data structure helpful for storing web-like relationships. Each node, or vertex, as they’re called in graphs, has a title (A, B, C, etc.), a value contained within, and a list of links (called edges) it has with other vertices.

In the above example, each circle is a vertex, and each line is an edge. If produced in writing, this structure would look like:

V = {a, b, c, d}

E = {ab, ac, bc, cd}

While hard to visualize at first, this structure is invaluable in conveying relationship charts in textual form, anything from circuitry to train networks.

Applications#

Network representations

Modeling social networks, such as Facebook.

6. Hash Tables (Map)#

Hash tables are a complex data structure capable of storing large amounts of information and retrieving specific elements efficiently. This data structure relies on the concept of key/value pairs, where the “key” is a searched string and the “value” is the data paired with that key.

Each searched key is converted from its string form into a numerical value, called a hash, using a predefined hash function. This hash then points to a storage bucket – a smaller subgroup within the table. It then searches the bucket for the originally entered key and returns the value associated with that key.

Data structure interview questions#

For many developers and programmers, data structures are most important for cracking Javascript coding interviews. Questions and problems on data structures are fundamental to modern-day coding interviews. In fact, they have a lot to say over your hireability and entry-level rate as a candidate.

Today, we will be going over seven common coding interview questions for JavaScript data structures, one for each of the data structures we discussed above. Each will also discuss its time complexity based on the BigO notation theory.

Array: Remove all even integers from an array#

Problem statement: Implement a function removeEven(arr), which takes an array arr in its input and removes all the even elements from a given array.

Input: An array of random integers

[1,2,4,5,10,6,3]

Output: an array containing only odd integers

[1,5,3]

There are two ways you could solve this coding problem in an interview. Let’s discuss each.

Solution #1: Doing it “by hand”#

Stack: Check for balanced parentheses using a stack#

Problem statement: Implement the isBalanced() function to take a string containing only curly {}, square [], and round () parentheses. The function should tell us if all the parentheses in the string are balanced. This means that every opening parenthesis will have a closing one. For example, {[]} is balanced, but {[}] is not.

Input: A string consisting solely of (, ), {, }, [ and ]

exp = "{[({})]}"

Output: Returns False if the expression doesn’t have balanced parentheses. If it does, the function returns True.

True

To solve this problem, we can simply use a stack of characters. Look below at the code to see how it works.

index.js

Stack.js

"use strict";
module.exports = class Stack {
    constructor() {
        this.items = [];
        this.top = null;
    }
    getTop() {
        if (this.items.length == 0)
            return null;
        return this.top;
    }
    isEmpty() {
        return this.items.length == 0;
    }
    size() {
        return this.items.length;
    }
    push(element) {
        this.items.push(element);
        this.top = element;
    }
    pop() {
        if (this.items.length != 0) {
            if (this.items.length == 1) {
                this.top = null;
                return this.items.pop();
            } else {
                this.top = this.items[this.items.length - 2];
                return this.items.pop();
            }
        } else
            return null;
    }
}

This process will iterate over the string one character at a time. We can determine that the string is unbalanced based on two factors:

The stack is empty.

The top element in the stack is not the right type.

If either of these conditions is true, we return False. If the parenthesis is an opening parenthesis, it is pushed into the stack. If by the end all are balanced, the stack will be empty. If it is not empty, we return False. Since we traverse the string exp only once, the time complexity is O(n).

Queue: Generate Binary Numbers from 1 to n#

Problem statement: Implement a function findBin(n), which will generate binary numbers from 1 to n in the form of a string using a queue.

Input: A positive integer n

n = 3

Output: Returns binary numbers in the form of strings from 1 up to n

result = ["1","10","11"]

The easiest way to solve this problem is using a queue to generate new numbers from previous numbers. Let’s break that down.

index.js

Queue.js

"use strict";
module.exports = class Queue {
    constructor() {
        this.items = [];
        this.front = null;
        this.back = null;
    }
    isEmpty() {
        return this.items.length == 0;
    }
    getFront() {
        if (this.items.length != 0) {
            return this.items[0];
        } else
            return null;
    }
    size() {
        return this.items.length;
    }
    enqueue(element) {
        this.items.push(element);
    }
    dequeue() {
        if (this.items.length == 0) {
            return null;
        } else {
            return this.items.shift();
        }
    }
}

The key is to generate consecutive binary numbers by appending 0 and 1 to previous binary numbers. To clarify,

10 and 11 can be generated if 0 and 1 are appended to 1.

100 and 101 are generated if 0 and 1 are appended to 10.

Once we generate a binary number, it is then enqueued to a queue so that new binary numbers can be generated if we append 0 and 1 when that number will be enqueued.

Since a queue follows the First-In First-Out property, the enqueued binary numbers are dequeued so that the resulting array is mathematically correct.

Look at the code above. On line 7, 1 is enqueued. To generate the sequence of binary numbers, a number is dequeued and stored in the array result. On lines 11-12, we append 0 and 1 to produce the next numbers.

Those new numbers are also enqueued at lines 14-15. The queue will take integer values, so it converts the string to an integer as it is enqueued.

The time complexity of this solution is in O(n)O(n) since constant-time operations are executed for n times.

Linked List: Reverse a linked list#

Problem statement: Write the reverse function to take a singly linked list and reverse it in place.

Input: a singly linked list

LinkedList = 0->1->2->3-4

Output: a reverse linked list

LinkedList = 4->3->2->1->0

The easiest way to solve this problem is by using iterative pointer manipulation. Let’s take a look.

index.js

LinkedList.js

Node.js

"use strict";
const Node = require('./Node.js');
module.exports = class LinkedList {
  constructor() {
    this.head = null;
  }
  //Insertion At Head  
  insertAtHead(newData) {
    let tempNode = new Node(newData);
    tempNode.nextElement = this.head;
    this.head = tempNode;
    return this; //returning the updated list
  }
  isEmpty() {
    return (this.head == null);
  }
  //function to print the linked list
  printList() {
    if (this.isEmpty()) {
      console.log("Empty List");
      return false;
    } else {
      let temp = this.head;
      while (temp != null) {
        process.stdout.write(String(temp.data));
        process.stdout.write(" -> ");
        temp = temp.nextElement;
      }
      console.log("null");
      return true;
    }
  }
  getHead() {
    return this.head;
  }
  setHead(newHead) {
    this.head = newHead;
    return this;
  }
  getListStr() {
    if (this.isEmpty()) {
      console.log("Empty List");
      return "null";
    } else {
      let st = "";
      let temp = this.head
      while (temp != null) {
        st += String(temp.data);
        st += " -> ";
        temp = temp.nextElement;
      }
      st += "null";
      return st;
    }
  }
  insertAtTail(newData) {
    //Creating a new Node with data as newData
    let node = new Node(newData);
    //check for case when list is empty
    if (this.isEmpty()) {
      //Needs to Insert the new node at Head
      this.head = node;
      return this;
    }
    //Start from head
    let currentNode = this.head;
    //Iterate to the last element
    while (currentNode.nextElement != null) {
      currentNode = currentNode.nextElement;
    }
    //Make new node the nextElement of last node of list
    currentNode.nextElement = node;
    return this;
  }
  search(value) {
    //Start from the first element
    let currentNode = this.head;
    //Traverse the list until you find the value or reach the end
    while (currentNode != null) {
      if (currentNode.data == value) {
        return true; //value found
      }
      currentNode = currentNode.nextElement
    }
    return false; //value not found
  }
  deleteAtHead() {
    //if list is empty, do nothing
    if (this.isEmpty()) {
      return this;
    }
    //Get the head and first element of the list
    let firstElement = this.head;
    //If list is not empty, link head to the nextElement of firstElement
    this.head = firstElement.nextElement;
    return this;
  }
  deleteVal(value) {
    let deleted = null; //True or False
    //Write code here
    //if list is empty return false
    if (this.isEmpty()) {
      return false;
    }
    //else get pointer to head
    let currentNode = this.head;
    // if first node's is the node to be deleted, delete it and return true
    if (currentNode.data == value) {
      this.head = currentNode.nextElement;
      return true;
    }
    // else traverse the list
    while (currentNode.nextElement != null) {
      // if a node whose next node has the value as data, is found, delete it from the list and return true
      if (currentNode.nextElement.data == value) {
        currentNode.nextElement = currentNode.nextElement.nextElement;
        return true;
      }
      currentNode = currentNode.nextElement;
    }
    //else node was not found, return false
    deleted = false;
    return deleted;
  }
  deleteAtTail() {
    // check for the case when linked list is empty
    if (this.isEmpty()) {
      return this;
    }
    //if linked list is not empty, get the pointer to first node
    let firstNode = this.head;
    //check for the corner case when linked list has only one element
    if (firstNode.nextElement == null) {
      this.deleteAtHead();
      return this;
    }
    //otherwise traverse to reach second last node
    while (firstNode.nextElement.nextElement != null) {
      firstNode = firstNode.nextElement;
    }
    //since you have reached second last node, just update its nextElement pointer to point at null, skipping the last node
    firstNode.nextElement = null;
    return this;
  }
}

We use a loop to iterate through the input list. For a current node, its link with the previous node is reversed. then, next stores the next node in the list. Let’s break that down by line.

Line 22- Store the current node’s nextElement in next

Line 23 - Set current node’s nextElement to previous

Line 24 - Make the current node the new previous for the next iteration

Line 25 - Use next to go to the next node

Line 29 - We reset the head pointer to point at the last node

Since the list is traversed only once, the algorithm runs in O(n).

Tree: Find the Minimum Value in a Binary Search Tree#

Problem statement: Use the findMin(root) function to find the minimum value in a Binary Search Tree.

Input: a root node for a binary search tree

bst = { 6 -> 4,9 4 -> 2,5 9 -> 8,12 12 -> 10,14 } where parent -> leftChild,rightChild

Output: the smallest integer value from that binary search tree

2

Let’s look at an easy solution for this problem.

Solution: Iterative findMin( )#

This solution begins by checking if the root is null. It returns null if so. It then moves to the left subtree and continues with each node’s left child until the left-most child is reached.

index.js

BinarySearchTree.js

Node.js

"use strict";
const Node = require('./Node.js');
module.exports = class BinarySearchTree {
    constructor(rootValue) {
        this.root = new Node(rootValue);
    }
    insert(currentNode, newValue) {
        if (currentNode === null) {
            currentNode = new Node(newValue);
        } else if (newValue < currentNode.val) {
            currentNode.leftChild = this.insert(currentNode.leftChild, newValue);
        } else {
            currentNode.rightChild = this.insert(currentNode.rightChild, newValue);
        }
        return currentNode;
    }
    insertBST(newValue) {
        if(this.root==null){
            this.root=new Node(newValue);
            return;
        }
        this.insert(this.root, newValue);
    }
    preOrderPrint(currentNode) {
        if (currentNode !== null) {
            console.log(currentNode.val);
            this.preOrderPrint(currentNode.leftChild);
            this.preOrderPrint(currentNode.rightChild);
        }
    }
    inOrderPrint(currentNode) {
        if (currentNode !== null) {
            this.inOrderPrint(currentNode.leftChild);
            console.log(currentNode.val);
            this.inOrderPrint(currentNode.rightChild);
        }
    }
    postOrderPrint(currentNode) {
        if (currentNode !== null) {
            this.postOrderPrint(currentNode.leftChild);
            this.postOrderPrint(currentNode.rightChild);
            console.log(currentNode.val);
        }
    }
    search(currentNode, value) {
        if (currentNode !== null) {
            if (value == currentNode.val) {
                return currentNode;
            } else if (value < currentNode.val) {
                return this.search(currentNode.leftChild, value)
            } else {
                return this.search(currentNode.rightChild, value)
            }
        } else {
            return null;
        }
    }
    searchBST(value) {
        return this.search(this.root, value);
    }
    delete(currentNode, value) {
        if (currentNode == null) {
            return false;
        }
        var parentNode;
        while (currentNode && (currentNode.val != value)) {
            parentNode = currentNode;
            if (value < currentNode.val) {
                currentNode = currentNode.leftChild;
            } else {
                currentNode = currentNode.rightChild;
            }
        }
        if (currentNode === null) {
            return false;
        } else if (currentNode.leftChild == null && currentNode.rightChild == null) {
            if(currentNode.val==this.root.val){
                this.root=null;
                return true;
            }
            else if (currentNode.val < parentNode.val) {
                parentNode.leftChild = null;
                return true;
            } else {
                parentNode.rightChild = null;
                return true;
            }
        } else if (currentNode.rightChild == null) {
            if(currentNode.val==this.root.val){
                this.root=currentNode.leftChild;
                return true;
            }
            else if (currentNode.leftChild.val < parentNode.val) {
                parentNode.leftChild = currentNode.leftChild;
                return true;
            } else {
                parentNode.rightChild = currentNode.leftChild;
                return true;
            }
        } else if (currentNode.leftChild == null) {
            if(currentNode.val==this.root.val){
                this.root = currentNode.rightChild;
                return true;
            }
            else if (currentNode.rightChild.val < parentNode.val) {
                parentNode.leftChild = currentNode.rightChild;
                return true;
            } else {
                parentNode.rightChild = currentNode.rightChild;
                return true;
            }
        } else { 
            var minRight = currentNode.rightChild;
            while (minRight.leftChild !== null) {
                minRight = minRight.leftChild;
            }
            var temp=minRight.val;
            this.delete(this.root, minRight.val);
            currentNode.val = temp;
            return true;
        }
    }
}

index.js

Graph.js

LinkedList.js

Node.js

"use strict";
const LinkedList = require('./LinkedList.js');
const Node = require('./Node.js');
module.exports = class Graph {
  constructor(vertices) {
    
    this.vertices = vertices;
    
    this.list = [];
    
    var it;
    for (it = 0; it < vertices; it++) {
      let temp = new LinkedList();
      this.list.push(temp);
    }
  }
  addEdge(source, destination) {
    if (source < this.vertices && destination < this.vertices)
   
    this.list[source].insertAtHead(destination);
   
    return this;
  }
  printGraph() {
    console.log(">>Adjacency List of Directed Graph<<");
    var i;
    for (i = 0; i < this.list.length; i++) {
      process.stdout.write("|" + String(i) + "| => ");
      let temp = this.list[i].getHead();
      while (temp != null) {
        process.stdout.write("[" + String(temp.data) + "] -> ");
        temp = temp.nextElement;
      }
      console.log("null ");
    }
  }
  strGraph() {
    let str = "";
    var i;
    for (i = 0; i < this.list.length; i++) {
      str = str + "|" + String(i) + "| => ";
      let temp = this.list[i].getHead();
      while (temp != null) {
        str += ("[" + String(temp.data) + "] -> ");
        temp = temp.nextElement;
      }
      str += "null ";
    }
    return str;
  }
}

Hash Table: Convert Max-Heap to Min-Heap#

Problem statement: Implement the function convertMax(maxHeap) to convert a binary max-heap into a binary min-heap. maxHeap should be an array in the maxHeap format, i.e the parent is greater than its children.

Input: a Max-Heap

maxHeap = [9,4,7,1,-2,6,5]

Output: returns the converted array

result = [-2,1,5,9,4,6,7]

To solve this problem, we must min heapify all parent nodes. Take a look.

function minHeapify(heap, index) {
    var left = index * 2;
    var right = (index * 2) + 1;
    var smallest = index;
    if ((heap.length > left) && (heap[smallest] > heap[left])) {
        smallest = left
    }
    if ((heap.length > right) && (heap[smallest] > heap[right]))
        smallest = right
    if (smallest != index) {
        var tmp = heap[smallest]
        heap[smallest] = heap[index]
        heap[index] = tmp
        minHeapify(heap, smallest)
    }
    return heap;
}
function convertMax(maxHeap) {
    for (var i = Math.floor((maxHeap.length) / 2); i > -1; i--)
        maxHeap = minHeapify(maxHeap, i)
    return maxHeap
}
var maxHeap = [9,4,7,1,-2,6,5]
console.log(convertMax(maxHeap))

What to learn next#

There’s clearly a lot to learn when it comes to data structures in JavaScript. Hands-on practice is key to success with coding interviews. It’s important to move beyond theory and apply these concepts to real-world solutions.

Next, you’ll want to cover the following topics:

Advanced data structures (i.e. tries)

Applying data structures to algorithms

JavaScript design patterns

To get started with these concepts, check out Educative’s curated learning path Ace the Front End Interview. This path will help you make sure you shake off any cobwebs and make a lasting positive impression on your interviewers. You’ll review all the key concepts you need and dive deep into dozens of real questions along the way.

Happy learning!

Continue reading about JavaScript#

JavaScript Loops Tutorial: for loop, while loop, and more

15 JavaScript Tips: best practices to simplify your code

5 tried and true techniques to prepare for a coding interview

6 JavaScript data structures you must know

Ace the front-end interview with hands-on projects.
Review all the key concepts and practice dozens of top interview questions.

Ace the Front End Interview

What are data structures#

1. Array#

Applications#

2. Queues#

Applications#

3. Linked List#

Applications#

4. Trees#

Applications#

5. Graphs#

Applications#

6. Hash Tables (Map)#

Applications#

Data structure interview questions#

Array: Remove all even integers from an array#

Solution #1: Doing it “by hand”#

Solution #2: Using filter() and lambda function#

Stack: Check for balanced parentheses using a stack#

Queue: Generate Binary Numbers from 1 to n#

Linked List: Reverse a linked list#

Tree: Find the Minimum Value in a Binary Search Tree#

Solution: Iterative findMin( )#

Graph: Remove Edge#

Hash Table: Convert Max-Heap to Min-Heap#

Keep the learning going.#

What to learn next#

Continue reading about JavaScript#

6 JavaScript data structures you must know

Ace the front-end interview with hands-on projects. Review all the key concepts and practice dozens of top interview questions. Ace the Front End Interview

What are data structures#

1. Array#

Applications#

2. Queues#

Applications#

3. Linked List#

Applications#

4. Trees#

Applications#

5. Graphs#

Applications#

6. Hash Tables (Map)#

Applications#

Data structure interview questions#

Array: Remove all even integers from an array#

Solution #1: Doing it “by hand”#

Solution #2: Using filter() and lambda function#

Stack: Check for balanced parentheses using a stack#

Queue: Generate Binary Numbers from 1 to n#

Linked List: Reverse a linked list#

Tree: Find the Minimum Value in a Binary Search Tree#

Solution: Iterative findMin( )#

Graph: Remove Edge#

Hash Table: Convert Max-Heap to Min-Heap#

Keep the learning going.#

What to learn next#

Continue reading about JavaScript#

Ace the front-end interview with hands-on projects.
Review all the key concepts and practice dozens of top interview questions.

Ace the Front End Interview