Arrays
Arrays vs Lists
| Arrays | Lists |
|---|---|
| Has fixed size. | No fixed size. |
| Created by specifying its size. | Created empty and values are added later. |
| Write: arr[index] = value; | Write: list.add(value); |
| Read: value = arr[index]; | Read: list.get(index); |
Push element at the end of the array
var arr = [2, 4, 6, 8];
arr.push(9); // [ 2, 4, 6, 8, 9 ]
Pop element from the end of the array
var arr = [2, 4, 6, 8];
arr.pop(); // [ 2, 4, 6, 8 ]
Have a look at Part 3 of this series to get more information about array methods.
Check out some interesting problems and solutions using arrays in javascript here.
List
The list is built out of an array. Lists come with functions that modify this array in such a way that we can give it more functionality. The list can be imagined as a class that has an array and methods to performs certain actions on this array. This is depicted in the below piece of code:
class List {
constructor() {
this.arr = new Array(5);
this.size = 0;
}
method() {
console.log("Hello World!");
}
push(value) {
this.arr[this.size] = value;
this.size++;
}
display() {
for (let i = 0; i < this.size; i++) {
console.log(this.arr[i]);
}
}
}
const l = new List();
l.method(); // Hello World!
l.push(6);
l.push(9);
l.display(); // 6 9
More programs on the list concept here.
Linked Lists
Linked Lists are a dynamic data structure that can utilise memory efficiently and can grow as required. The linked list takes constant time for insertion and deletion. The linked list consists of nodes each of which contains two parts data and next. Every node holds the data and the address to the next node.
function printList(node) {
let current = node
let result = "root -> "
while (current != null) {
result += current.data + " -> "
current = current.next
}
result += "null"
console.log(result)
}
class ListNode {
constructor(data, next) {
this.data = data
this.next = next
}
}
// start: null
// end: 1 -> 2 -> 3
function problem1() {
let root = null;
printList(root)
root = new ListNode(3)
let node = new ListNode(2)
node.next = root
root = node
node = new ListNode(1)
node.next = root
root = node
printList(root)
console.log()
}
// Insertion in the beginning
// start: 1 -> 2 -> 3
// end: 0 -> 1 -> 2 -> 3
function problem2() {
let root = new ListNode(1, new ListNode(2, new ListNode(3)))
printList(root)
let zero = new ListNode(0)
zero.next = root
root = zero
printList(root)
console.log()
}
// Insertion in the middle
// start: 1 -> 3 -> 4
// end: 1 -> 2 -> 3 -> 4
function problem3() {
let root = new ListNode(1)
root.next = new ListNode(3)
root.next.next = new ListNode(4)
printList(root)
let n2 = new ListNode(2)
root.next = n2
printList(root)
console.log()
}
// Insertion in the end
// start: 1 -> 2 -> 3
// end: 1 -> 2 -> 3 -> 4
function problem4() {
let root = new ListNode(1, new ListNode(2, new ListNode(3)))
printList(root)
let four = new ListNode(4)
root.next.next.next = four
printList(root)
console.log()
}
// Deletion in the middle
// start: 1 -> 99 -> 2 -> 3
// end: 1 -> 2 -> 3
function problem5() {
let root = new ListNode(1, new ListNode(99, new ListNode(2, new ListNode(3))))
printList(root)
root.next = root.next.next
printList(root)
console.log()
}
problem1()
problem2()
problem3()
problem4()
problem5()
This is a typical program for performing basic operations on a linked list. Check out more programs on the linked list here.
Stack
The stack is an efficient data structure that follows the LIFO rule(Last In First Out). The stack data structure can be thought of like a collection of disks on a music recorder. A disk can be placed upon another(push) and the recently placed disk can be removed to get access to the underlying disk(pop). You can see the topmost disk that is currently playing(peek). Stacks give constant time access to its topmost element but don't provide random access. Stacks have a great application in Undo/Redo operations, parenthesis matching and function call during backtracking. Let's see how to construct a Stack using an array:
class ArrayStack {
constructor() {
this.data = new Array(10);
this.size = 0;
}
isEmpty() {
return this.size === 0;
}
push(value) {
if (this.data.length === this.size) {
this.grow();
}
this.data[this.size] = value;
this.size++;
}
pop() {
let result = this.data[this.size - 1];
this.data[this.size - 1] = null;
this.size--;
return result;
}
peek() {
return this.data[this.size - 1];
}
size() {
return this.size;
}
grow() {
let data = new Array(this.data.length * 2);
for (let i = 0; i < this.data.length; i++) {
data[i] = this.data[i];
}
this.data = data;
}
}
let sl = new ArrayStack();
sl.push(1);
sl.push(32);
sl.push(122);
sl.push(9012);
while (!sl.isEmpty()) {
let val = sl.pop();
console.log(val); // 9012 122 32 1
}
It would be a better idea to implement stack using a linked list to optimize memory allocation. Linked list implementation of a stack and more such problems here.
Queue
The queue data structure works on the concept of FIFO(First In First Out). You can imagine this data structure as a line of people waiting to collect their tickets at a movie theatre. The people in the front collect their tickets and proceed to the theatre(dequeue). Then the next person in the queue walks up to the counter. Meanwhile more people arrive and join the queue at the end to collect their tickets(enqueue). The queue takes constant time to perform both enqueue and dequeue operations.
class Node {
constructor(data, next) {
this.data = data;
this.next = next;
}
}
class Queue {
constructor() {
this.front = null;
this.rear = null;
}
isEmpty() {
// Check if queue is empty
return this.front === null;
}
enqueue(value) {
// add elements to the end of the queue
let node = new Node(value);
if (this.isEmpty()) {
// if the queue is empty make front and rear point to the same first node
this.front = node;
this.rear = node;
} else {
// make rear point to the new node
this.rear.next = node;
this.rear = node;
}
}
dequeue() {
if (this.isEmpty()) {
// if queue is empty nothing to be dequeued
return null;
}
// reference to first element in queue
let result = this.front.data;
if (this.front === this.rear) {
// if only one node left then reset front and rearto null
this.front = null;
this.rear = null;
} else {
// front is the second element in the queue
this.front = this.front.next;
}
return result;
}
}
let q = new Queue();
q.enqueue("33");
q.enqueue("-22");
q.enqueue("11");
q.enqueue("90");
q.enqueue("99");
q.enqueue("-101");
while (!q.isEmpty()) {
console.log(q.dequeue()); // 33 -22 11 90 99 -101
}
This is the basic implementation of the queue data structure for more interesting problems on queue please click here.
Recursion
Recursion isn't a type of data structure but it will be essential in the topics that are covered later. Calling a function in itself is termed as recursion. A simple implementation of recursion is shown below:
let i = 0;
function display() {
console.log("Hello for the " + i + "th" + " time.");
if (i != 10) {
i++;
display();
}
}
display();
Recursions are very helpful when working with problems related to backtracking since it makes use of the call stack. More problems on recursion here.
Tree
The tree data structure is a collection of nodes connected by branches. The tree data structure is non-linear. The tree starts with a root node having children nodes and each of the children having more children nodes. Each node will have two-pointers which points to either of its children: left and right. The tree data structure is really efficient in performing complex database queries. Let's see a basic implementation of the tree data structure:
class Node {
constructor(data, left = null, right = null) {
this.data = data;
this.left = left;
this.right = right;
}
}
class Tree {
constructor() {
this.root = null;
}
collect() {
// return the value at every node
return this._collect(this.root, []);
}
_collect(curr, result = []) {
// recursion
if (curr === null) return result;
result.push(curr.data);
this._collect(curr.left, result);
this._collect(curr.right, result);
return result;
}
}
let t1 = new Node(12);
let t2 = new Node(-12);
let t3 = new Node(121);
let t4 = new Node(122);
let t5 = new Node(112);
let t6 = new Node(-1112);
let tree = new Tree();
tree.root = t1;
t1.left = t2;
t1.right = t3;
t3.right = t4;
t4.left = t5;
t5.left = t6;
console.log(tree.collect()); // [ 12, -12, 121, 122, 112, -1112 ]
Binary Search Tree: A binary search tree is a tree in which nodes which have lesser value is stored on the left branch and the greater numbers are stored on the right branch. The binary search tree implementation is given below:
class Node {
constructor(data, left = null, right = null) {
this.data = data;
this.left = left;
this.right = right;
}
}
class Tree {
constructor() {
this.root = null;
}
insert(value) {
if (this.root === null) {
this.root = new Node(value);
} else {
this._insert(this.root, value);
}
}
_insert(node, value) {
if (value < node.data && node.left === null) {
node.left = new Node(value);
} else if (value > node.data && node.right === null) {
node.right = new Node(value);
} else if (value < node.data) {
this._insert(node.left, value);
} else {
this._insert(node.right, value);
}
}
collect() {
return this._collect(this.root, []);
}
_collect(node, result) {
if (node === null) {
return result;
}
result.push(node.data);
this._collect(node.left, result);
this._collect(node.right, result);
return result;
}
}
let tree = new Tree();
tree.insert(43);
tree.insert(13);
tree.insert(23);
tree.insert(29);
tree.insert(115);
tree.insert(52);
tree.insert(102);
tree.insert(2);
console.log(tree.collect()); // [43, 13, 2, 23, 29, 115, 52, 102]
Trees are an amazing data structure to work with and has its applications practically in many fields. See more problems on trees here.
Hash Maps
The hash map data structure stores data in the form of a key-value pair like a table. Each value is associated with a unique key value such that it makes it easier to access any value in the hash table. The hash table data structure is the most sought after data structure as it has a constant time complexity to access, insert or delete an element in an average case scenario. Let's have a look at a simple implementation of the hash map:
class HashMap {
constructor() {
this.buckets = new Array(10);
}
hash(str) {
// return the sum of all letters in the string by their alphabetical index value
str = str.toLowerCase();
const ALPHABET = "abcdefghijklmnopqrstuvwxyz";
let sum = 0;
for (let i = 0; i < str.length; i++) {
sum += ALPHABET.indexOf(str.charAt(i));
}
return sum;
}
hashCode(key) {
// this is a hash function that returns the modulus of the string sum by the bucket length
let val = this.hash(key) % this.buckets.length;
return val;
}
put(key, value) {
// place the value in the hash map
let index = this.hashCode(key);
this.buckets[index] = value;
}
get(key) {
// get value of a key from hash map
let index = this.hashCode(key);
return this.buckets[index];
}
remove(key) {
// remove the value of a key from hash map
let index = this.hashCode(key);
this.buckets[index] = null;
}
}
let h = new HashMap();
h.put("Apples", 22);
h.put("Oranges", 11);
h.put("Pineapples", 16);
h.put("Grapes", 19);
console.log(h.get("Apples")); // 16
console.log(h.get("GRAPES")); // 19
console.log(h.get("Banana")); // undefined
The program takes a string and passes it into a hash function to generate a unique number for it to store it a unique index.
Sometimes the modulus gives the same number for two different strings which results in a collision. Such collisions can be solved in two ways:
- Linear Probing
- Linked Lists Check out the programs on solving such collisions using the above two methods here.
Graphs
The final and most important data structure are graphs. These data structures hold importance in a variety of applications from relationships on social networks to finding the closest route to a destination on maps. Below is a simple implementation of the graph data structure:
class Graph {
constructor() {
this.edges = {};
}
addNode(node) {
// Add a vertex to the graph
if (!this.edges[node]) {
this.edges[node] = [];
}
}
addBidirectionalEdge(n1, n2) {
// Add bidirectional edge between two nodes
this.addEdge(n1, n2);
this.addEdge(n2, n1);
}
addEdge(start, end) {
// Add an unidirectional edge between two nodes
this.edges[start].push(end);
}
getNeighbours(start) {
// Get the nodes connected to any node
return this.edges[start];
}
}
let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addBidirectionalEdge("A", "B");
g.addBidirectionalEdge("A", "C");
g.addBidirectionalEdge("B", "C");
g.addBidirectionalEdge("C", "D");
g.addBidirectionalEdge("D", "B");
g.addBidirectionalEdge("D", "E");
console.log(g.getNeighbours("B")); // [ 'A', 'C', 'D' ]
Checkout more problems on graphs here.
Conclusion
This has been a roller-coaster ride. Learning data structures can seem like a daunting task but it will all make sense when you get enough hold on them. Knowledge of data structures is a must before attending technical interviews. Javascript makes things easier to code these data structures by not accounting for any pointers, importing libraries, and other aspects that draw attention away from the main programming concept to be covered.
To get familiar with these concepts it will require a lot of practice and problem-solving. Head over to online coding platforms such as Hackerrank, HackerEarth, CodeChef, etc and keep practising.
I hope I have delivered javascript data structures concepts well. I also hope that you have a firm foundation now to kick things off with data structures problems.
Thank You!
Top comments (0)