Data Structures in JavaScript

A data structure is a way of storing data in memory and a set of operations that it allows you to perform. This set of operations is called an interface. Different data structures may have the same interfaces but implement them differently. Therefore, the same operations for different data structures can vary in computational complexity.

Data structures are used to solve various tasks, such as searching, sorting, filtering, and much more.

Imagine that we have a list of 1000 names and we need to find a specific name in that list. One could go through each line of the list in order. This can take a lot of time, especially if the list is very large.

However, if you store names in another data structure, such as a hash table or a search tree, you can find the needed name much faster.

Arrays are one of the most common data structures in programming. They are used to store a collection of elements, such as numbers, strings, or objects.

Memory for an array in JavaScript is allocated dynamically, so arrays can change their size during the execution of the program. The actual location of elements in memory will differ for different programs. For small arrays, elements are likely to be located sequentially.

Arrays provide an interface for accessing elements by their index, for example, pizza[0].

Imagine that we have a pizza that needs to be divided into several pieces. You can use an array to store each piece of pizza separately:

        
          
          const pizza = ['piece 1', 'piece 2', 'piece 3', 'piece 4', 'piece 5']
          const pizza = ['piece 1', 'piece 2', 'piece 3', 'piece 4', 'piece 5']

        
        
          
            
            Copy
            Copied
            Failed to copy
          
        
      

Now we can divide the pizza into a few more pieces:

        
          
          pizza.splice(2, 0, 'piece 2.5')console.log(pizza)// ["piece 1", "piece 2", "piece 2.5",// "piece 3", "piece 4", "piece 5"]
          pizza.splice(2, 0, 'piece 2.5')
console.log(pizza)
// ["piece 1", "piece 2", "piece 2.5",
// "piece 3", "piece 4", "piece 5"]

        
        
          
            
            Copy
            Copied
            Failed to copy
          
        
      

A stack is a data structure that works on the principle of LIFO (Last In, First Out), which means "the last in is the first to come out". For example, when you do the dishes and stack the plates on top of each other. If you want to wipe them, you'll take the last washed plate first. This is the principle of a stack.

Stacks are used for retrieving data in reverse order. For instance, we want to keep a history of user actions in an application: when a user performs a new action, we put an element on the stack. When the user wants to undo an action, we take an element off the stack:

        
          
          let stack = []stack.push('action 1')stack.push('action 2')stack.push('action 3')console.log(stack) // ["action 1", "action 2", "action 3"]let lastAction = stack.pop()console.log(lastAction) // "action 3"console.log(stack) // ["action 1", "action 2"]
          let stack = []

stack.push('action 1')
stack.push('action 2')
stack.push('action 3')

console.log(stack) // ["action 1", "action 2", "action 3"]

let lastAction = stack.pop()

console.log(lastAction) // "action 3"
console.log(stack) // ["action 1", "action 2"]

        
        
          
            
            Copy
            Copied
            Failed to copy
          
        
      

In this example, we created an empty stack and added three actions to it. Then we removed the last action from the top of the stack using the pop() method.

In JavaScript, there is no special data structure for a stack, but you can use an array as in the example above.

A queue is a data structure that works on the principle of FIFO (First In, First Out), which means "the first to arrive is the first to be served". It can be compared to a queue for delicious pastries: the first person to arrive will be the first to get a pastry.

Queues are used to store data in the order they are added. For example, if we want to keep a list of tasks for the day, we will use a queue to store these tasks:

        
          
          let queue = []queue.push('task 1')queue.push('task 2')queue.push('task 3')console.log(queue) // ["task 1", "task 2", "task 3"]let firstTask = queue.shift()console.log(firstTask) // "task 1"console.log(queue) // ["task 2", "task 3"]
          let queue = []

queue.push('task 1')
queue.push('task 2')
queue.push('task 3')

console.log(queue) // ["task 1", "task 2", "task 3"]

let firstTask = queue.shift()

console.log(firstTask) // "task 1"
console.log(queue) // ["task 2", "task 3"]

        
        
          
            
            Copy
            Copied
            Failed to copy
          
        
      

In this example, we created an empty queue and added three tasks to it, then took the first from the front of the queue using the shift() method.

In JavaScript, there is no special data structure for a queue; the above example uses an array, however, this implementation has a disadvantage: removing an element from the front of the queue has linear complexity. Let's try to implement a queue a little differently to achieve constant complexity when removing an element from the front of the queue:

        
          
          class Queue {  #queue = {}  #head = 0  #tail = 0  push(data) {    this.#queue[this.#tail] = data    this.#tail++  }  get front() {    return this.#queue[this.#head]  }  get size() {    return this.#tail - this.#head  }  pop() {    if (this.size === 0) return    const data = this.#queue[this.#head]    delete this.#queue[this.#head]    this.#head++    return data  }}const queue = new Queue()queue.push('task 1')queue.push('task 2')queue.push('task 3')console.log(queue.front) // "task 1"console.log(queue.size) // 3queue.pop()console.log(queue.front) // "task 2"console.log(queue.size) // 2
          class Queue {
  #queue = {}
  #head = 0
  #tail = 0

  push(data) {
    this.#queue[this.#tail] = data
    this.#tail++
  }

  get front() {
    return this.#queue[this.#head]
  }

  get size() {
    return this.#tail - this.#head
  }

  pop() {
    if (this.size === 0) return

    const data = this.#queue[this.#head]
    delete this.#queue[this.#head]
    this.#head++
    return data
  }
}

const queue = new Queue()
queue.push('task 1')
queue.push('task 2')
queue.push('task 3')

console.log(queue.front) // "task 1"
console.log(queue.size) // 3

queue.pop()
console.log(queue.front) // "task 2"
console.log(queue.size) // 2

        
        
          
            
            Copy
            Copied
            Failed to copy
          
        
      

In this example, we use an object instead of an array to store the elements of the queue. We keep two pointers to the start and the end of the queue – private properties #head and #tail.

A linked list is a data structure that consists of nodes, each of which contains data and a reference to the next node in the list. A linked list can be imagined as a train, where each car is a node in the list. Each car contains cargo (data) and a connection to the next car (reference). The first car is the head of the list, and the last one, which does not have a connection to another, is the tail of the list. Thus, you can move through the train (the list) from one car (node) to another.

There are two main types of linked lists — singly linked and doubly linked.

• Singly linked list is a data structure made up of elements of one type, sequentially linked together by pointers. Each list element has a pointer to the next element. The last element points to nothing. The element that has no pointer is the first in the list.
• Doubly linked list is a data structure in which each element contains pointers to both the next and the previous elements. This allows you to traverse the list in both directions.

Linked lists are used to store data in the order they are added. One advantage of linked lists is that they allow for quick addition and removal of elements at any location. For example, if you want to keep a list of tasks to be performed in an application, you can use a linked list to store these tasks. Each node of the list will contain one task and a reference to the next subtask:

        
          
          class Node {  constructor(data) {    this.data = data    this.next = null  }}let head = new Node('Task 1')let secondNode = new Node('Subtask 1.1')let thirdNode = new Node('Subtask 1.1.2')head.next = secondNodesecondNode.next = thirdNodeconsole.log(head)// Node {//  data: "Task 1",//  next: Node {//    data: "Subtask 1.1",//    next: Node {//      data: "Subtask 1.1.2",//      next: null//    }//  }// }
          class Node {
  constructor(data) {
    this.data = data
    this.next = null
  }
}

let head = new Node('Task 1')
let secondNode = new Node('Subtask 1.1')
let thirdNode = new Node('Subtask 1.1.2')

head.next = secondNode
secondNode.next = thirdNode

console.log(head)
// Node {
//  data: "Task 1",
//  next: Node {
//    data: "Subtask 1.1",
//    next: Node {
//      data: "Subtask 1.1.2",
//      next: null
//    }
//  }
// }

        
        
          
            
            Copy
            Copied
            Failed to copy
          
        
      

In this example, we created three nodes of a singly linked list and connected them to each other using references. The first node is called the head of the list and contains a reference to the next node. Each subsequent node also contains a reference to the next node in the list. The last node points to null and is called the tail of the list.

Trees are a hierarchical structure that consists of connected nodes. Each tree node contains data and references to its child nodes. The top of the tree is called the root, and nodes that have no descendants are leaves.

Key terms used when dealing with trees:

• Children — nodes whose current node is a parent;
• Descendants — nodes that can be reached through parent connections. All your children, grandchildren, great-grandchildren, and so on will be your descendants;
• Siblings — nodes that share the same parent. Your siblings are people who have the same parents as you;
• Leaves — nodes with no descendants. For example, your relatives who have no children.

Let's create a tree with a parent with two children. Each of the children has their own children (grandchildren):

        
          
          class TreeNode {  constructor(value) {    this.value = value    this.children = []  }}const parent = new TreeNode('Parent')const child1 = new TreeNode('Child 1')const child2 = new TreeNode('Child 2')parent.children.push(child1)parent.children.push(child2)const grandChild1 = new TreeNode('Grandchild 1')const grandChild2 = new TreeNode('Grandchild 2')child1.children.push(grandChild1)child2.children.push(grandChild2)
          class TreeNode {
  constructor(value) {
    this.value = value
    this.children = []
  }
}

const parent = new TreeNode('Parent')
const child1 = new TreeNode('Child 1')
const child2 = new TreeNode('Child 2')

parent.children.push(child1)
parent.children.push(child2)

const grandChild1 = new TreeNode('Grandchild 1')
const grandChild2 = new TreeNode('Grandchild 2')

child1.children.push(grandChild1)
child2.children.push(grandChild2)

        
        
          
            
            Copy
            Copied
            Failed to copy
          
        
      

Trees help organize data hierarchically, process information, search for paths, and much more.

A binary tree is a data structure in which each node has no more than two children, usually referred to as "left child" and "right child". A special type of binary tree is the binary search tree. In a binary search tree, for each node, its value is greater than or equal to the value of any node in its left subtree and less than or equal to the value of any node in its right subtree. This property makes binary search trees efficient for search and insertion operations.

Graphs are a data structure that consists of nodes connected by edges. Graphs come in two main types: directed and undirected.

• Directed. In a directed graph, edges have direction. This means that if there is an edge from node A to node B, this does not guarantee the presence of an edge from node B to node A. In other words, A to B and B to A are not the same.
• Undirected. In an undirected graph, edges do not have direction. This means that if there is an edge between nodes A and B, you can move in either direction.

Let's imagine we have several cities located close to each other, and there are roads between them. In this context, nodes are cities, and edges are the roads connecting these cities:

        
          
          const roadMap = new Graph()roadMap.addVertex('Moscow')roadMap.addVertex('Saint Petersburg')roadMap.addVertex('Nizhny Novgorod')roadMap.addEdge('Moscow', 'Saint Petersburg')roadMap.addEdge('Moscow', 'Nizhny Novgorod')
          const roadMap = new Graph()
roadMap.addVertex('Moscow')
roadMap.addVertex('Saint Petersburg')
roadMap.addVertex('Nizhny Novgorod')
roadMap.addEdge('Moscow', 'Saint Petersburg')
roadMap.addEdge('Moscow', 'Nizhny Novgorod')

        
        
          
            
            Copy
            Copied
            Failed to copy
          
        
      

Graphs are used to model relationships between objects, find paths, optimize routes, and much more. The hierarchy of friends on Facebook or Google Maps roads are graphs.

Trees and linked lists are special cases of graphs.