Most commonly used JavaScript Data Structures you must know
Hey, it’s very interesting because today I am going to discuss and implement the most important Data Structures in Computer Science such as Stack, Queue, Linked List, Trees, and Hash Table. Let’s dive into it.
Stack
Stack is LIFO (Last In First Out) data structure which principle is the last element added to the Stack will be the first element removed from the Stack. We can do two things using Stack. Firstly, we can add data at the last to the Stack which is known as push, and secondly, we can remove last added data from the Stack which is known as pop.
// Building a Stack with an Array
const stack = [];stack.push(42);
console.log(stack); // expected output: [ 42 ]stack.push(22);
console.log(stack); // expected output: [ 42, 22 ]stack.pop();
console.log(stack); // expected output: [ 42 ]//N.B. Last Added 22 element is First Out.// Building a Stack with OOP
class Stack {
constructor () {
this.stack = [];
} push (value) {
this.stack.push(value);
} pop () {
return this.stack.pop();
} // peek() is used for showing the last element of the Queue.
// If you want, you can skip it.
peek () {
return this.stack[ this.stack.length - 1 ]
}
}const myStack = new Stack();myStack.push(55);
console.log(myStack); // expected output: Stack { stack: [ 55 ] }myStack.push(66);
console.log(myStack); //expected output: Stack Stack { stack: [ 55, 66 ] }myStack.pop();
console.log(myStack); // expected output: Stack { stack: [ 55 ] }//N.B. Last Added 66 element is First Out.
Queue
Queue is FIFO (First In First Out) data structure which principle is the first element added to the Queue will be the first element removed from the Queue. We can do two things using Queue as well. Firstly, we can add data at the first to the Queue which is known as enqueue, and secondly, we can remove first added data from the Queue which is known as dequeue.
Consider, some people are waiting for an airplane ticket in a line. In that case, the first person in line is the first person out. The Queue looks like that.
// Building a Queue with an array
const queue = []queue.unshift(32);
console.log(queue); // expected output: [ 32 ]queue.unshift(22);
console.log(queue); // expected output: [ 22, 32 ]queue.pop()
console.log(queue); // expected output: [ 22 ]// N.B. First Added 32 element is First Out from the Queue.// Building a Queue with OOP
class Queue {
constructor () {
this.queue = [];
} enQueue (value) {
this.queue.unshift(value);
} deQueue () {
return this.queue.pop();
} // peek() is used for showing the last element of the Queue.
// You can skip it.
peek () {
return this.queue[this.queue.length - 1]
}
}const myQueue = new Queue();
myQueue.enQueue(11);
console.log(myQueue); // expected output: Queue { queue: [ 11 ] }myQueue.enQueue(22);
console.log(myQueue); //expected output: Queue { queue: [ 22, 11 ] }myQueue.deQueue();
console.log(myQueue); // expected output: Queue { queue: [ 22 ] }// First added 11 element is First out.
Linked List
Linked List is one of the most interesting & important Data Structure. It is the list of elements called nodes that are connected together or linked together in a line. There are two types of linked list. For Example:
- Singly Linked List: Its node only points to the next Node.
2. Doubly Linked List: Its node not only points to the next Node but also points to the previous Node.
Linked List consists of nodes, and each node has a value and a pointer to another node or null. Excepting the last Node, every node of Linked List points to the next node. The last node points to the null. It gives us a great privilege to do efficient insertion and removal of items without the need for reorganization. The beginning of the Linked List is known as Head and the end of the Linked List is known as Tail.
The difference between Linked List and Array:
Implementation of Linked List:
class Node {
constructor (data, next = null) {
this.data = data;
this.next = next;
}
}class LinkedList {
constructor () {
this.head = null;
} insertFirst (value) {
this.head = new Node(value, this.head);
} size () {
let counter = 0;
let node = this.head;
while (node) {
counter++; //assigning node by next node again & again to reach last node
node = node.next;
}
return counter;
} getFirst () {
return this.head;
} getLast () {
if (!this.head) {
return null;
}
let node = this.head;
while (node) {
if (!node.next) {
return node;
}
// assigning node by next node again & again to get last node
node = node.next;
}
} clear () {
this.head = null;
} removeFirst () {
if (!this.head) {
return;
}
// first node will be the second node.
this.head = this.head.next;
} removeLast () {
if (!this.head) {
return;
}
// only one node will be assigned with null to remove
if (!this.head.next) {
this.head = null;
return;
} let previous = this.head;
let node = this.head.next;
// loop for getting before last & last node.
while (node.next) {
previous = node;
node = node.next;
}
// assigning last node with null.
previous.next = null;
} insertLast (value) {
const last = this.getLast();
if (last) {
last.next = new Node(value);
} else {
this.head = new Node(value);
}
} getAt (index) {
let counter = 0;
let node = this.head;
while (node) {
if (index === counter) {
return node;
}
counter++;
node = node.next;
}
// if hadn't any node & unable to find node return null;
return null;
} removeAt (index) {
if (!this.head) {
return;
}
// easily can remove the first node if index is0
if (index === 0) {
this.head = this.head.next;
return;
} // get the previous node by reusing getAt()
const previous = this.getAt(index - 1);//if previous is out bounce& previous.next(current)not exist return.
if (!previous || !previous.next) {
return;
}//assign previous.next(current node by previous.next.next(next node)
previous.next = previous.next.next;
} insertAt (index, value) {
if (!this.head) {
this.head = new Node(value);
return;
} // insert first node with provided value & next reference
if (index === 0) {
this.head = new Node(value, this.head);
return;
} // if index is out of bounce, add node to the end of the list.
// if index is out of bounce, assign previous with last node. const previous = this.getAt(index - 1) || this.getLast();
const node = new Node(value, previous.next);
previous.next = node;
}
}// play with Linked List
const myLinkedList = new LinkedList();myLinkedList.insertFirst(22);
myLinkedList.insertFirst(11);console.log(myLinkedList);
/* expected output:
LinkedList {
head: Node { data: 11, next: Node { data: 22, next: null } }
}
*/
console.log(myLinkedList.size()); // expected output: 2console.log(myLinkedList.removeAt(1));
console.log(myLinkedList);
/* expected output:
LinkedList { head: Node { data: 11, next: null } }
*/console.log(myLinkedList.insertAt(1, 50));
console.log(myLinkedList);
/* expected output:
LinkedList {
head: Node { data: 11, next: Node { data: 50, next: null } }
}
*/
Tree
Trees are a very commonly used data structure all around the world. They are widely used in HTML DOM, Network Routing, Abstract Syntax Tree, Artificial Intelligence, Folders in OS, Computer File System, etc.
Trees are data structures that consist of nodes in the parent-child relationship. In trees, there are many different paths we could take just like the journey of life.
Terminology :)
Root => The top node in a tree.
Parent => predecessor of any node
Child => descendant of any node
Siblings => A group of nodes with the same parent
Leaf => A node with no children
Edge => The connection between one and another.
Sub Tree => each child from a node forms a subtree recursively. Every child node will form a subtree on its parent node.
There are two ways for Traversing a Tree:
- Breadth-first Search: The Breadth-First Search (BFS) is an algorithm for traversing or searching tree or graph data structures. It explores all the nodes at the present depth before moving on to the nodes at the next depth level. Let’s look at a practical example to better illustrate this:
2. Depth-first Search: The Depth First Search (DFS) is an algorithm for traversing or searching tree or graph data structures which uses the idea of backtracking. It explores all the nodes by going forward if possible or uses backtracking. Let’s see an example to clear about that.
Implementation of Trees Data Structure:
class Node {
constructor (data = null) {
this.data = data;
this.children = [];
} add(data) {
const node = new Node(data);
this.children.push(node);
}
remove(data) {
this.children = this.children.filter(node => {
return node.data !== data;
});
}
}class Tree {
constructor () {
this.root = null;
} traverseBF(fn) {
const arr = [this.root];
while (arr.length) {
const node = arr.shift(); arr.push(...node.children);
fn(node);
}
} traverseDF(fn) {
const arr = [this.root];
while (arr.length) {
const node = arr.shift(); arr.unshift(...node.children);
fn(node);
}
}
}const myNode = new Node(32);
console.log(myNode);
// expected output: Node { data: 32, children: [] }myNode.add(11);
myNode.add(22);
myNode.add(33);
console.log(myNode);
/*
Output:
Node {
data: 32,
children: [
Node { data: 11, children: [] },
Node { data: 22, children: [] },
Node { data: 33, children: [] }
]
}
*/const myTree = new Tree();
myTree.root = myNode;
myTree.traverseBF((node) => console.log(node.data));
// expected output: 32 11 22 33myTree.traverseDF((node) => console.log(node.data));
// expected output: 32 11 22 33
Binary Search Tree (BST)
Binary Tree is a tree data structure in which each node has at most two children which are known as the left child and right child. Binary Seach Tree (BST) is a special binary tree which has some specific requirements. Such as:
The Requirements of Binary Search Tree (BST)
1. Every Parent node has at most two children
2. Every node to the left of a parent node is always less than the parent.
3. Every node to the right of a parent node is always greater than the parent.
Implementation of Binary Search Trees (BST):
class Node {
constructor (data) {
this.data = data;
this.left = null;
this.right = null;
} insert(data) {
if (data < this.data && this.left) {
this.left.insert(data);
} else if (data < this.data) {
this.left = new Node(data);
} else if (data > this.data && this.right) {
this.right.insert(data);
} else if (data > this.data) {
this.right = new Node(data);
}
} contains(data) {
if (this.data === data) {
return this;
}
if (this.data < data && this.right) {
return this.right.contains(data);
} else if (this.data > data && this.left) {
return this.left.contains(data);
} return null;
}
}// Let's play with BST
const myBST = new Node(30);
console.log(myBST);
// expected output: Node { data: 30, left: null, right: null }myBST.insert(20);
myBST.insert(40);
console.log(myBST);
/*
expected output:
Node {
data: 30,
left: Node { data: 20, left: null, right: null },
right: Node { data: 40, left: null, right: null }
}
*/
myBST.insert(15);
myBST.insert(25);
myBST.insert(35);
myBST.insert(45);
console.log(myBST);
/*
expecpted output:
Node {
data: 30,
left: Node {
data: 20,
left: Node { data: 15, left: null, right: null },
right: Node { data: 25, left: null, right: null }
},
right: Node {
data: 40,
left: Node { data: 35, left: null, right: null },
right: Node { data: 45, left: null, right: null }
}
}
*/
console.log(myBST.contains(40));
/*
expected output:
Node {
data: 40,
left: Node { data: 35, left: null, right: null },
right: Node { data: 45, left: null, right: null }
}
*/
Hash Table
Hash tables are used to store key-value pairs. They are like arrays, but the keys are not ordered. Unlike arrays, hash tables are fast for all of the following operations: finding values, adding new values, and removing values!
Nearly every programming language has some sort of hash table data structure such as Dictionaries in python, Objects in javascript and Maps in java, go & scala etc.
class HashTable {
constructor(size = 53) {
this.keyMap = new Array(size);
} _hash(key) {
let total = 0;
let WEIRD_PRIME = 31;
for (let i = 0; i < Math.min(key.length, 100); i++) {
let char = key[i];
let value = char.charCodeAt(0) - 96
total = (total * WEIRD_PRIME + value) % this.keyMap.length;
}
return total;
} set(key, value) {
let index = this._hash(key);
if (!this.keyMap[index]) {
this.keyMap[index] = [];
}
this.keyMap[index].push([key, value]);
} get(key) {
let index = this._hash(key);
if (this.keyMap[index]) {
for (let i = 0; i < this.keyMap[index].length; i++) {
if (this.keyMap[index][i][0] === key) {
return this.keyMap[index][i][1]
}
}
}
return undefined;
} keys() {
let keysArr = [];
for (let i = 0; i < this.keyMap.length; i++) {
if (this.keyMap[i]) {
for (let j = 0; j < this.keyMap[i].length; j++) {
if (!keysArr.includes(this.keyMap[i][j][0])) {
keysArr.push(this.keyMap[i][j][0])
}
}
}
}
return keysArr;
} values() {
let valuesArr = [];
for (let i = 0; i < this.keyMap.length; i++) {
if (this.keyMap[i]) {
for (let j = 0; j < this.keyMap[i].length; j++) {
if (!valuesArr.includes(this.keyMap[i][j][1])) {
valuesArr.push(this.keyMap[i][j][1])
}
}
}
}
return valuesArr;
}
}let myHashTable = new HashTable(17);
myHashTable.set("maroon", "#800000")
myHashTable.set("yellow", "#FFFF00")
myHashTable.set("olive", "#808000")
myHashTable.set("salmon", "#FA8072")
myHashTable.set("lightcoral", "#F08080")
myHashTable.set("mediumvioletred", "#C71585")console.log(myHashTable.get('salmon'));
// expected output: #FA8072console.log(myHashTable.get('maroon'));
// expected output: #800000myHashTable.keys().forEach(function(key){
console.log(myHashTable.get(key));
})/*
expected output:
#FA8072
#800000
#FFFF00
#808000
#F08080
#C71585
*/
Wow, this was a long one and I think, you pretty much enjoy it. In this article, I tried my best to cover most of the cool data structures in Computer Science. I think, it must help you to take serious interview preparation and will put you in a great position. If you have any suggestions or comments, feel free to share with me in the comment section below.
