Data structures provide us with tools and techniques to store, organize, and manipulate data. Data structures make it easier for the programmer to access and modify data.

JavaScript has primitive and non-primitive data structures. Primitive data structures and data types are native to the programming language. Non-primitive data structures are those that are not defined by the programming language but rather by the programmer.

Primitive JavaScript data structures

• Arrays
• Objects
• Sets
• Maps

Non-primitive JavaScript data structures

• Stacks
• Queues
• Linked lists
• Trees
• Graphs

First, we'll take a look at the primitive JavaScript data structures and their time complexities. Then, we'll take a look at the non-primitive JavaScript data structures and their time complexities.

When it comes to the non-primitive data structures, we'll only cover the linear ones in this article. Linear Data Structures are ones where data is stored sequentially. The linear ones are stacks, queues, and linked lists.

Primitive JavaScript data structures

Arrays

An array is a linear data structure that stores a collection of elements. JavaScript arrays can hold elements of different types and can dynamically resize. You can perform operations like adding or removing elements, accessing elements by index, and iterating over the array.

const colors = ['red', 'green', 'blue'];
colors.push('yellow'); // Add an element to the end
colors.pop(); // Remove the last element
console.log(colors[colors.length - 1]); // Access the last element
console.log(colors[0]); // Access the first element

Big O time complexity of arrays

• Accessing an element by index: O(1).

  Accessing an element in an array by its index takes constant time. Arrays provide direct access to elements based on their indices via array[index].

• Inserting or removing an element at the end of the array: O(1).

  Adding or removing an element at the end of the array has a constant time complexity. JavaScript arrays are dynamically resizable, so adding or removing elements at the end does not require shifting or resizing the entire array.

  JavaScript provides the push and pop methods to insert or remove an element at the end of the array.

• Inserting or removing an element at the beginning or middle of the array: O(n).

  Inserting an element at the beginning or middle of the array requires shifting elements to make room and to adjust the array indices of existing array elements. Removing an element at the beginning or middle of the array requires shifting elements to fill the gap that was made by the removal.

  Both operations have a linear time complexity. This means that the operation time will increase linearly as the size of the input increases (represented by n).

  The JavaScript array methods used for these operations are unshift, shift, and splice.

• Searching for an element: O(n).

  Searching for an element in an array requires iterating over the array and comparing each element until a match is found or the end of the array is reached. In the worst case scenario, where the element is not present, or where the element is at the end of the array, it has a linear time complexity of O(n).

  The JavaScript array methods used for this operation are indexOf, includes, find, and findIndex.

• Sorting an array: O(n log n).

  The built-in sort method in JavaScript uses an optimized version of the Quicksort algorithm. To sort an array of n elements, it has an average time complexity of O(n log n).

Objects

JavaScript objects are key-value pairs where the keys are strings and the values can be of any type. Objects provide a way to store and retrieve data using descriptive keys.

const gray = {
  name: 'gray',
  hexCode: '#808080',
  webSafe: '#999999',
  rgb: '128, 128, 128',
};
console.log(gray.name); // 'gray'
gray.hexCode = '#666666'; // Modify a property

Sets

A JavaScript Set is a collection of unique elements. Values of any type can be stored in a Set. A Set has methods for adding, removing, and checking the existence of elements. Sets automatically remove duplicate items.

const colorsSet = new Set();
colorsSet.add('red');
colorsSet.add('green');
colorsSet.add('green'); // Duplicates are automatically removed
console.log(colorsSet.size); // 2
colorsSet.delete('green'); // Remove an element
console.log(colorsSet.has('red')); // true

Big O time complexity of Sets

• Adding an element: O(1).

  Adding an element to a Set using the add method has a constant time complexity.

• Checking the existence of an element:: O(1).

  Checking if an element exists in a Set using the has method results in a constant time complexity.

• Removing an element: O(1).

  Removing an element from a Set using the delete method has a constant time complexity

Maps

A JavaScript Map is a collection of key-value pairs. A Map is similar to an object. The difference that Maps have from objects is that they allow any type of key, not just strings. Maps preserve the insertion order of elements, meaning that the order in which elements are added to the Map is maintained. A Map provides methods to add, remove, and retrieve elements.

Keys in a Map are unique, meaning that each key can only exist once within the Map. However, values do not have to be unique. Different keys can be associated with the same value.

const gray = new Map();
gray.set('name', 'gray');
gray.set('hexCode', '#808080');
console.log(gray.get('name')); // 'gray'
gray.delete('hexCode'); // Remove a key-value pair
console.log(gray.has('hexCode')); // false

Big O time complexity of Maps

• Adding an element: O(1).

  Adding an entry to a Map using the set method has a constant time complexity.

• Checking the existence of a key:: O(1).

  Checking if a key exists in a Map using the has method has a constant time complexity. The same is true for accessing a value in a Map by its key using the get method.

• Removing an element: O(1).

  Removing an entry from a Map by its key using the delete method has a constant time complexity.

Non-primitive JavaScript data structures

Stacks

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle, where the last element added is the first one to be removed.

Common operations performed on a stack are:

• push (add an element to the top).
• pop (remove the top element).
• peek (access the top element without removing it).
• isEmpty (check if the stack is empty).

Here is a basic stack implemented with a JavaScript array. By using the built-in push and pop array methods, we can implement the stack behavior on an array.

let stack = [];
stack.push('red');
stack.push('green');
console.log(stack.pop()); // 'green'
console.log(stack.length); // 1

We can also implement a Stack using a JavaScript class. This class will encapsulate all the logic for the stack data structure. We can reuse this class whenever we need a stack data structure.

class Stack {
  constructor() {
    this.items = [];
  }

  getTop() {
    if (this.items.length === 0) {
      return null;
    }
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.items.length === 0) {
      return null;
    }
    return this.items.pop();
  }
}

We can use the Stack class by creating an instance of it and calling its methods.

const colorStack = new Stack();
console.log(colorStack.size()); // 0

colorStack.push('red');
colorStack.push('green');
console.log(colorStack.size()); // 2
console.log(colorStack.getTop()); // 'green'

colorStack.pop();
console.log(colorStack.size()); // 1
console.log(colorStack.getTop()); // 'red'

colorStack.pop();
console.log(colorStack.size()); // 0
console.log(colorStack.getTop()); // null

Big O time complexity of Stacks

• Accessing an element: O(n).

  To reach any specific element, all the elements before (or on top of) the element have to be removed from the stack. The worst case is that n elements need to be removed from the stack before being able to access the desired element.

• Insertion and deletion: O(1).

  The push and pop methods insert to and remove from the top of the stack in constant time.

Queues

A queue is a data structure that follows the First-In-First-Out (FIFO) principle. The first element added to the queue is the first one to be removed.

Common operations performed on a queue are:

• enqueue (add an element to the end).
• dequeue (remove the first element).
• peek (access the first element without removing it).
• isEmpty (check if the queue is empty).

Here is a basic queue implemented with a JavaScript array. By using the built-in push and shift array methods, we can implement the queue behavior on an array.

let queue = [];
queue.push('red');
queue.push('green');
console.log(queue.shift()); // 'red'
console.log(queue.length); // 1

We can also implement a Queue using a JavaScript class. This class will encapsulate all the logic for the queue data structure. We can reuse this class whenever we need a queue data structure.

class Queue {
  constructor() {
    this.items = [];
    this.front = null;
    this.back = null;
  }

  isEmpty() {
    return this.items.length === 0;
  }

  getFront() {
    if (this.isEmpty()) {
      return null;
    }

    return this.items[0];
  }

  size() {
    return this.items.length;
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    if (this.isEmpty()) {
      return null;
    }

    return this.items.shift();
  }
}

We can use the Queue class by creating an instance of it and calling its methods.

const colorQueue = new Queue();
console.log(colorQueue.size()); // 0

colorQueue.enqueue('red');
colorQueue.enqueue('green');
console.log(colorQueue.size()); // 2
console.log(colorQueue.getFront()); // 'red'

console.log(colorQueue.dequeue()); // 'red'
console.log(colorQueue.size()); // 1
console.log(colorQueue.getFront()); // 'green'

console.log(colorQueue.dequeue()); // 'green'
console.log(colorQueue.size()); // 0
console.log(colorQueue.getFront()); // null

Big O time complexity of Queues

• Accessing an element: O(n).

  To reach any specific element, all the elements after the element have to be removed from the queue. The worst case is that n elements need to be removed from the queue before being able to access the desired element.

• Insertion and deletion: O(1).

  Only the front element can be removed from the queue via the dequeue operation, using the shift method, and taking constant time. Insertion happens at the back of the queue via the enqueue operation, using the push method, and also taking constant time.

Linked list

A linked list is a linear data structure where each node in a list of nodes contains a value and a reference to the next node in the list. JavaScript doesn't have its own built-in linked list data structure. However, we can create our own.

First, let's define a class for a node. This class will represent nodes in the linked list and will contain a value and a reference to the next node.

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

Next, let's define a class for the linked list data structure in the same file. Let's call this class LinkedList. It will make use of the Node class to represent each of the nodes in the list.

The LinkedList class will contain two class-level variables, head and tail. The head variable will reference the head, or the starting node, of the linked list. The tail variable will reference the last node in the linked list.

We will define the following methods in the LinkedList class.

• append: add a node to the end of the linked list.
• prepend: add a node to the beginning of the linked list.
• insertAfter: add a node after a specific node.
• delete: delete a node containing a specific value.
• search: find a node by its value.
• print: a helper method to allow us to print the entire linked list to the console.

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

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

  // add node to end of linked list
  append(value) {
    // create new node with the provided value
    const newNode = new Node(value);

    if (!this.head) {
      // the new node is the only one in the list
      this.head = newNode;
      this.tail = newNode;
    } else {
      // point the current last node to the new last node
      this.tail.next = newNode;
      // the new node is now last in the list
      this.tail = newNode;
    }
  }

  // add node to beginning of linked list
  prepend(value) {
    // create new node with the provided value
    const newNode = new Node(value);

    if (!this.head) {
      // the new node is the only one in the list
      this.head = newNode;
      this.tail = newNode;
    } else {
      // point the new head node to the existing head
      newNode.next = this.head;
      // the new node is now first in the list
      this.head = newNode;
    }
  }

  // add new node after the target node
  insertAfter(value, target) {
    // create new node with the provided value
    const newNode = new Node(value);
    
    // search for target node
    let currentNode = this.head;
    while (currentNode) {
      if (currentNode.value === target) {
        // node after target node now comes after new node
        newNode.next = currentNode.next;
        // add new node after target node
        currentNode.next = newNode;

        // if the target node is the last node
        if (currentNode === this.tail) {
          // set the tail to the new node
          this.tail = newNode;
        }

        break;
      }

      // iterate to the next node
      currentNode = currentNode.next;
    }
  }

  // delete a node by value
  delete(value) {
    if (!this.head) {
      return;
    }

    // if the node to delete is the head
    if (this.head.value === value) {
      // set the new head to the next node
      this.head = this.head.next;

      // if there is no next node
      if (this.head === null) {
        // there's only a head and no tail
        this.tail = null;
      }

      return;
    }

    // if the node to delete is not the head, find it
    let currentNode = this.head;
    while (currentNode.next) {
      if (currentNode.next.value === value) {
        // set target node's 'next' to skip over the deleted node
        currentNode.next = currentNode.next.next;

        // if target node's 'next' is not a node
        if (currentNode.next === null) {
          // the target node is the tail
          this.tail = currentNode;
        }

        break;
      }

      // iterate to the next node
      currentNode = currentNode.next;
    }
  }

  // find a node by value
  search(value) {
    // start the search at the head node
    let currentNode = this.head;
    while (currentNode) {
      if (currentNode.value === value) {
        return currentNode;
      }

      // iterate to the next node
      currentNode = currentNode.next;
    }

    return null;
  }

  // print linked list to console
  print() {
    const values = [];
    
    // start getting node values from the head
    let currentNode = this.head;    
    while (currentNode) {
      values.push(currentNode.value);

      // iterate to the next node
      currentNode = currentNode.next;
    }

    console.log(values.join(" -> "));
  }
}

We can use the LinkedList class by creating an instance of it and calling its methods. Take a look at the sample execution flow and output below.

const linkedList = new LinkedList();
linkedList.append(1);
linkedList.print(); // "1"
linkedList.append(2);
linkedList.print(); // "1 -> 2"
linkedList.append(3);
linkedList.print(); // "1 -> 2 -> 3"
linkedList.prepend(0);
linkedList.print(); // "0 -> 1 -> 2 -> 3"
linkedList.insertAfter(4, 2);
linkedList.print(); // "0 -> 1 -> 2 -> 4 -> 3"
linkedList.delete(1);
linkedList.print(); // "0 -> 2 -> 4 -> 3"
console.log(linkedList.search(3)); // { value: 3, next: null }

Big O time complexity of Linked lists

• Accessing an element: O(n).

  To reach any specific element in a linked list, all the elements occurring before the element have to be traversed. The worst case is that n elements need to be traversed before finding and accessing the desired element.

• Insertion and deletion:

  Inserting or deleting an element at the head of the linked list can be done in O(1) constant time because we have a direct pointer to the head of the list.

  Inserting an element at any other location in the linked list will have a time complexity of O(n). The desired insertion location in the linked list will need to be reached by traversing the linked list.

  The worst case is that we would need to traverse the entire n elements of the linked list to get to the insertion location. The same time complexity goes for deleting an element from any location in the linked list that is not the head.

Conclusion

This article has been a crash course on data structures in JavaScript, providing you with data structure fundamentals and applying them to JavaScript.

We covered JavaScript's primitive data structures and their time complexities. Then, we learned how to build more complex linear data structures that are not defined by JavaScript. After building our own implementations of a stack, a queue, and a linked list, we looked at the time complexities of each.

What we haven't covered is non-linear data structures in JavaScript, such as trees, binary trees, and graphs. That'll be a topic for a future blog post.