8 Common Data Structures in JavaScript

8 Common Data Structures in JavaScript

1. Stack

A stack data structure holds a list of elements and works on the principle of LIFO (Last in, First out). This means the element that is added most recently is also the element to be removed first. There are two main operations that occur at the top of the stack, which are push and pop. With the push method, you can add one or more elements to the end of the array. However, with the pop method, you can get rid of the element at the end of the array, which is then returned to the caller.

function Stack() {

this.count = 0;

  this.storage = {};

  this.push = function (value) {

    this.storage[this.count] = value;

    this.count++;

  }

  this.pop = function () {

if (this.count === 0) {

   return undefined;

}

    this.count--;

var result = this.storage[this.count];

delete this.storage[this.count];

return result;

  }

  this.peek = function () {

return this.storage[this.count - 1];

  } 

  this.size = function () {

return this.count;

  }

}

2. Queue

While similar to stacks in terms of concepts, queues, unlike stacks that process the elements based on recent ones entered, process the elements in the entered order. So, when you want to store the requests in the order they were received in, you can use a queue. To give an example, here’s a utilization of an array to run a queue.

function Queue() {

  var collection = [];

  this.print = function () {

    console.log(collection);

  }

  this.enqueue = function (element) {

    collection.push(element);

  }

  this.dequeue = function () {

return collection.shift();

  }

  this.front = function () {

return collection[0];

  } 

  this.isEmpty = function () {

return collection.length === 0;

  }

  this.size = function () {

return collection.length;

  }

}

3. Priority Queue

Priority queue is used for allocating priority to each element. The elements are sorted as per the priority level.

function PriorityQueue() {

  ...

  this.enqueue = function (element) {

if (this.isEmpty()) {

      collection.push(element);

} else {

   var added = false;

   for (var i = 0; i < collection.length; i++) {

     if (element[1] < collection[i][1]) {

          collection.splice(i, 0, element);

       added = true;

       break;

     }

   }

   if (!added) {

        collection.push(element);

   }

}

  }

}

4. Linked List

Linked lists use a referencing system instead of using physical placements of data in the memory. Linked lists store the elements in nodes. These nodes contain a pointer to the subsequent node, which creates a link between all the nodes. With a linked list system, you can efficiently insert and remove the items without reorganizing. Here’s an example for Linked List using nodes-

/** Node in the linked list **/

function Node(element) { 

// Data in the node

    this.element = element; 

// Pointer to the next node

    this.next = null;

}

    function LinkedList() { 

        var length = 0; 

        var head = null; 

        this.size = function () {

            return length; 

        } 

        this.head = function () {

            return head; 

        } 

        this.add = function (element) {   

            var node = new Node(element);

            if (head == null) { 

                head = node;  

         } else { 

                var currentNode = head; 

                while (currentNode.next) {        

                 currentNode = currentNode.next; 

                } 

                currentNode.next = node;

            }

            length++; 

        } 

        this.remove = function (element) {   

            var currentNode = head;

            var previousNode;

            if (currentNode.element === element) { 

                head = currentNode.next;

            } else { 

                while (currentNode.element !== element) {   

                 previousNode = currentNode;   

                 currentNode = currentNode.next;

          } 

                previousNode.next = currentNode.next;   

            }   

            length--; 

        } 

        this.isEmpty = function () {

            return length === 0; 

        } 

        this.indexOf = function (element) {   

            var currentNode = head;

            var index = -1;    

            while (currentNode) { 

                index++; 

                if (currentNode.element === element) {   

                 return index; 

                } 

                currentNode = currentNode.next;

         }   

            return -1; 

        } 

        this.elementAt = function (index) {   

            var currentNode = head;

            var count = 0;

            while (count < index) { 

                count++; 

                currentNode = currentNode.next;   

            }

            return currentNode.element; 

        } 

        this.addAt = function (index, element) {

            var node = new Node(element);

            var currentNode = head;

            var previousNode;

            var currentIndex = 0;

            if (index > length) {

                return false;

            }

            if (index === 0) { 

                node.next = currentNode; 

                head = node;

            } else { 

                while (currentIndex < index) {       

                 currentIndex++;   

                 previousNode = currentNode;   

                 currentNode = currentNode.next; 

                } 

                node.next = currentNode; 

                previousNode.next = node;

            }

            length++; 

        } 

        this.removeAt = function (index) {   

            var currentNode = head;

            var previousNode;

            var currentIndex = 0;

            if (index < 0 || index >= length) { 

                return null;    

            }

            if (index === 0) { 

                head = currentIndex.next;

            } else { 

                while (currentIndex < index) {       

                 currentIndex++;   

                 previousNode = currentNode;   

                 currentNode = currentNode.next; 

                } 

                previousNode.next = currentNode.next;   

            }

            length--;

            return currentNode.element; 

     }

}

5. Set

Set is a collection of distinct objects that are well-defined, and it lets you add data to a container. While a little similar to array, a set is not indexed and it does not allow repeating elements. We can declare MySet to differentiate set in ES6, and the following example demonstrates that. 

function MySet() { 

var collection = []; 

this.has = function (element) {

     return (collection.indexOf(element) !== -1); 

} 

this.values = function () {

     return collection; 

} 

this.size = function () {

     return collection.length; 

} 

this.add = function (element) {

     if (!this.has(element)) { 

            collection.push(element); 

            return true;

     }

     return false; 

} 

this.remove = function (element) {

     if (this.has(element)) { 

            index = collection.indexOf(element);     

            collection.splice(index, 1); 

         return true;

     }

     return false; 

} 

this.union = function (otherSet) {

     var unionSet = new MySet();

     var firstSet = this.values();

     var secondSet = otherSet.values();

     firstSet.forEach(function (e) { 

            unionSet.add(e);

     });

        secondSet.forEach(function (e) {     

            unionSet.add(e);

     });

     return unionSet;  } 

        this.intersection = function (otherSet) {

         var intersectionSet = new MySet();

         var firstSet = this.values();

            firstSet.forEach(function (e) {     

                if (otherSet.has(e)) {   

                    intersectionSet.add(e); 

                }

            });

            return intersectionSet; 

     } 

        this.difference = function (otherSet) {

         var differenceSet = new MySet();

         var firstSet = this.values();

            firstSet.forEach(function (e) {     

                if (!otherSet.has(e)) {   

                    differenceSet.add(e); 

                }

            });

            return differenceSet; 

     } 

        this.subset = function (otherSet) {   

         var firstSet = this.values();

            return firstSet.every(function (value) { 

                return otherSet.has(value);

            }); 

     }

}

6. Hash Table

A hash table is generally used in Object data structures, Map, or Dictionary as it queries a value through a key at a very high speed. When you use a hash table, a hash function is used to convert the keys into a list of numbers, which is called hash. A hash represents the value of the corresponding key. A hash points to a smaller subgroup of the table, which is called a storage bucket. The storage bucket is then searched for the key that was originally entered. It then returns the values associated with the key. Here’s a simple example of a Hash table in Javascript.

function hash(string, max) {

  var hash = 0;

  for (var i = 0; i < string.length; i++) {

hash += string.charCodeAt(i);

  }

  return hash % max;

}

function HashTable() {

  let storage = [];

  const storageLimit = 4;

  this.add = function (key, value) {

var index = hash(key, storageLimit);

if (storage[index] === undefined) {

      storage[index] = [

     [key, value]

   ];

} else {

   var inserted = false;

   for (var i = 0; i < storage[index].length; i++) {

     if (storage[index][i][0] === key) {

          storage[index][i][1] = value;

          inserted = true;

     }

   }

   if (inserted === false) {

        storage[index].push([key, value]);

   }

}

  }

  this.remove = function (key) {

var index = hash(key, storageLimit);

if (storage[index].length === 1 && storage[index][0][0] === key) {

   delete storage[index];

} else {

   for (var i = 0; i < storage[index]; i++) {

     if (storage[index][i][0] === key) {

       delete storage[index][i];

     }

   }

}

  } 

  this.lookup = function (key) {

var index = hash(key, storageLimit);

if (storage[index] === undefined) {

   return undefined;

} else {

   for (var i = 0; i < storage[index].length; i++) {

     if (storage[index][i][0] === key) {

       return storage[index][i][1];

     }

   }

}

  }

}

7. Tree

Tree is a non-linear, multi-layer data structure which proves to be highly efficient for several operations, such as insert and search. A tree has a root node, and other nodes branch from this root node. A root node has various child nodes, which have references to all the elements. And then there are more child nodes branching off from child nodes, and this continues. When a node has linked child nodes, it is called an internal node. And nodes that do not have child nodes are known as external nodes. A tree structure is helpful in storing hierarchical data, and it can help with searches where one needs to order the data.

class Node {

  constructor(data, left = null, right = null) {

this.data = data;

this.left = left;

this.right = right;

  }

}

class BST {

  constructor() {

this.root = null;

  }

  add(data) {

const node = this.root;

if (node === null) {

   this.root = new Node(data);

   return;

} else {

   const searchTree = function (node) {

     if (data < node.data) {

       if (node.left === null) {

            node.left = new Node(data);

            return;

       } else if (node.left !== null) {

            return searchTree(node.left);

       }

     } else if (data > node.data) {

       if (node.right === null) {

            node.right = new Node(data);

            return;

       } else if (node.right !== null) {

            return searchTree(node.right);

       }

     } else {

       return null;

     }

   };

   return searchTree(node);

}

  } 

  findMin() {

let current = this.root;

while (current.left !== null) {

   current = current.left;

}

return current.data;

  } 

  findMax() {

let current = this.root;

while (current.right !== null) {

   current = current.right;

}

return current.data;

  } 

  find(data) {

let current = this.root;

while (current.data !== data) {

   if (data < current.data) {

     current = current.left

   } else {

     current = current.right;

   }

   if (current === null) {

     return null;

   }

}

return current;

  } 

  isPresent(data) {

let current = this.root;

while (current) {

   if (data === current.data) {

     return true;

   }

   if (data < current.data) {

     current = current.left;

   } else {

     current = current.right;

   }

}

return false;

  }

  remove(data) {

const removeNode = function (node, data) {

   if (node == null) {

     return null;

   }

   if (data == node.data) {

     // no child node

     if (node.left == null && node.right == null) {

       return null;

     }

     // no left node

     if (node.left == null) {

       return node.right;

     }

     // no right node

     if (node.right == null) {

       return node.left;

     }

     // has 2 child nodes

     var tempNode = node.right;

     while (tempNode.left !== null) {

          tempNode = tempNode.left;

     }

        node.data = tempNode.data;

        node.right = removeNode(node.right, tempNode.data);

     return node;

   } else if (data < node.data) {

     node.left = removeNode(node.left, data);

     return node;

   } else {

        node.right = removeNode(node.right, data);

     return node;

   }

}

this.root = removeNode(this.root, data);

  }

}

8. Trie

Trie is a type of search tree, which is also known as ‘Prefix Tree’. It is useful for storing data in a step-by-step manner. When you use trie, you can store vocabulary for quick searches. It is especially useful for the auto-complete function. The steps in the tree are represented by nodes. Here’s an example of a trie structure-

/** Node in Trie **/

function Node() { 

this.keys = new Map(); 

this.end = false; 

this.setEnd = function () {

     this.end = true; 

}; 

this.isEnd = function () {

     return this.end; 

}

}

function Trie() { 

     this.root = new Node(); 

     this.add = function (input, node = this.root) {   

         if (input.length === 0) {

                node.setEnd(); 

                return;

         } else if (!node.keys.has(input[0])) {     

            node.keys.set(input[0], new Node()); 

                return this.add(input.substr(1), node.keys.get(input[0]));

         } else { 

                return this.add(input.substr(1), node.keys.get(input[0]));

            } 

     } 

        this.isWord = function (word) {   

         let node = this.root;

            while (word.length > 1) { 

                if (!node.keys.has(word[0])) {       

                    return false; 

                } else {   

                    node = node.keys.get(word[0]);      

                    word = word.substr(1); 

                }

            }

            return (node.keys.has(word) && node.keys.get(word).isEnd()) ? true : false; 

     } 

            this.print = function () {

                let words = new Array();

                let search = function (node = this.root, string) { 

                    if (node.keys.size != 0) {   

                        for (let letter of node.keys.keys()) {     

                            search(node.keys.get(letter), string.concat(letter));   

                        }   

                        if (node.isEnd()) {     

                            words.push(string);   

                        } 

                    } else {   

                        string.length > 0 ? words.push(string) : undefined;   

                        return;   

                    }

                };

                search(this.root, new String());   

                return words.length > 0 ? words : null; 

}

}

9. Graph

The graph data structure allows nodes to have zero or more adjacent elements. In a graph, which is also known as a network at times, there are sets of nodes, and these nodes have linkages or edges. Based on whether or not these linkages have directions, there are two groups of graphs- directed graphs and undirected graphs. 

Graphs can be represented in two ways. One is called the adjacent list, wherein the left side consists of all the nodes and the right side consists of the connected nodes. In another presentation of graphs, known as adjacency matrix, nodes are arranged in rows and columns. The relation between the nodes is denoted by the intersection of the row and the column. While 0 indicates no linkage, 1 indicates linkage, and >1 means different weightage. 

Breadth-First-Search method is generally used for querying for nodes in a graph, by searching through the whole tree network. Here’s an example of BFS for this operation in Javascript-

function bfs(graph, root) {

  var nodesLen = {};

  for (var i = 0; i < graph.length; i++) {

nodesLen[i] = Infinity;

  }

  nodesLen[root] = 0;

  var queue = [root];

  var current;

  while (queue.length != 0) {

current = queue.shift();

var curConnected = graph[current];

var neighborIdx = [];

var idx = curConnected.indexOf(1);

while (idx != -1) {

      neighborIdx.push(idx);

   idx = curConnected.indexOf(1, idx + 1);

}

for (var j = 0; j < neighborIdx.length; j++) {

   if (nodesLen[neighborIdx[j]] == Infinity) {

        nodesLen[neighborIdx[j]] = nodesLen[current] + 1;

        queue.push(neighborIdx[j]);

   }

}

  }

  return nodesLen;

}

Data Structure Interview Questions 

1. What is the difference between file structure and storage structure?

File structure represents data into secondary or auxiliary memory in devices, such as pen drives and hard disks. The data stored remains intact unless it is manually taken down. On the other hand, the data is stored in the main memory for storage structure, like in random access memory. When the function using this data is executed completely, the data gets deleted automatically.   

2. What is the difference between linear and non-linear data structures?

Linear data structures and non-linear data structures are different in that the data structure elements become a linear list or a sequence for linear data structures. However, for non-linear data structures, there is a traversal of nodes. Some examples of linear data structure are queues, stacks, and lists, while graphs and trees are non-linear ones. 

3. What is an array? 

A collection of similar types of data that are stored in contiguous locations and memory is called an array. Array represents the simplest form of data structure, and you can access the data element randomly with the help of its index number. 

4. What is a multidimensional array?

A multidimensional array represents data structures that are spread across more than a single dimension. For every point of storage, there are multiple index variables in a multidimensional array. 2D arrays are the most commonly used multidimensional arrays. 

5. How are linked lists more efficient than arrays?

There are multiple ways in which linked lists are more efficient than arrays, which are as follows-

• Insertion and Deletion- Since there is a need to create rooms for new elements by shifting the existing elements in an array, it can be an expensive process. However, linked lists only require updating of the address present in the next pointer of the node. 
• Dynamic Data Structure- Linked lists do not require an initial size to be specified at the time of creation. This means it can grow and shrink by allocation and deallocation of memory at runtime. This makes linked lists a dynamic data structure, unlike arrays where the size has to be specified. 
• No Memory Wastage- When in an array, a certain size of the memory is already declared and it is not completely utilized, this results in the wastage of space. However, since linked lists don’t demand any such declaration, it grows or shrinks based on the requirements of the program. 

6. What are the applications of stack?

Stack can be used for checking for balanced parentheses in an expression, to evaluate postfix expression, reverse a string, and to deal with issues of infix to postfix conversion. 

7. What is the process behind storing a variable in memory?

A variable is stored in memory on the basis of the needed amount of memory. Here are the steps that are followed for storing a variable in memory- 

• First, one has to assign the required amount of memory.
• This is followed by storing the variable on the basis of the data structure that is in use. For this, using concepts, such as dynamic allocation results in higher efficiency. With this, you can access the storage units in real time on the basis of the requirements. 

Conclusion

Now that you are aware of some of the common data structures in JavaScript, you can now go ahead and experiment with these in your own programs. If you are looking to master the different skills in full stack programming, then Simplilearn’s Post Graduate Program in Full Stack Web Development can be a perfect place to get started.

This six-month bootcamp certification program covers over 30 of today’s top Java and Full Stack skills. The curriculum sessions are delivered by top practitioners in the industry and, along with the multiple projects and interactive labs, make this a perfect program to give you the work-ready skills needed to land today’s top software development job roles.

If you have any doubts or queries regarding this article or the course, feel free to post them in the comments below. Our team will review and get back to you at the earliest.