Data Structures and their JS implementation
Though there are 8 data types in JS (number, bigInt, string, symbol, boolean, null, undefined and object) classical CS requires much more compllicated data representation and data collections. Let's take a look at most commonly used data structures and their JS representation.
Array
Array is an indexed collection and in JS there is a standard build-in object to represent an array.
// Create an array
let letters = Array.from('abc'); // ["a","b","c"]
let numbers= Array.of(1,2,3); // [1,2,3]
let zeros = new Array(3).fill(0); // [0,0,0];
let fruits = ['Apple', 'Banana'];
// Loop
fruits.forEach(function(item, index, array) { // loop over an array
console.log(item, index)
});
// Insert/remove
let newLength = fruits.push('Orange'); // add to the end
let last = fruits.pop() // remove item from the end
let first = fruits.shift() // remove item from the front
let newLength = fruits.unshift('Strawberry') // add to the front
let pos = fruits.indexOf('Banana'); // find item position in the array
let removedItem = fruits.splice(pos, 1) // remove an item
// Copy, concat
let shallowCopy = fruits.slice() // this is how to make a copy
const array1 = ['a', 'b', 'c'];
const array2 = ['d', 'e', 'f'];
const array3 = array1.concat(array2); // ["a", "b", "c", "d", "e", "f"]
// Useful methods
const words = ['spray', 'limit', 'elite', 'exuberant', 'destruction', 'present'];
const result = words.filter(word => word.length > 6);
const found = words.find(word => word.length > 10);
const array1 = [1, 4, 9, 16];
const map1 = array1.map(x => x * 2);
const reducer = (accumulator, currentValue) => accumulator + currentValue;
console.log(array1.reduce(reducer)); //30
console.log(Object.keys(fruits)) // ['0', '1', '2', '5'] array is an object in JS
List and Linked List
A linked list is a linear data structure similar to an array. However, unlike arrays, elements are not stored in a particular memory location or index. Nodes can easily be removed or added from a linked list without reorganizing the entire data structure. This is one advantage it has over arrays. Search operations are slow in linked lists. Unlike arrays, random access of data elements is not allowed. Nodes are accessed sequentially starting from the first node.
class ListNode {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
constructor(head = null) {
this.head = head;
this.size = 0;
}
// add(element)
// removeElement(element)
// isEmpty
}
let node1 = new ListNode(2);
let node2 = new ListNode(5);
node1.next = node2;
let list = new LinkedList(node1);
//Implementation of some methods
add(element){
var node = new ListNode(element);
var current;
if (this.head == null)
this.head = node;
else {
current = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
}
this.size++;
}
removeElement(element){
var current = this.head;
var prev = null;
while (current != null) {
if (current.data === element) {
if (prev == null) {
this.head = current.next;
} else {
prev.next = current.next;
}
this.size--;
return current.element;
}
prev = current;
current = current.next;
}
return -1;
}
Queue
Queue is a collection data structure providing last-in-first-out semantics (LIFO). In JS it can be implemented with built-in arrays methods: push and shift.
function Queue() {
this.elements = [];
}
Queue.prototype.enqueue = function (e) {
this.elements.push(e);
};
Queue.prototype.dequeue = function () {
return this.elements.shift();
};
Queue.prototype.isEmpty = function () {
return this.elements.length == 0;
};
// access the element at the front of the queue without modifying it
Queue.prototype.peek = function () {
return !this.isEmpty() ? this.elements[0] : undefined;
};
Queue.prototype.length = function() {
return this.elements.length;
}
let q = new Queue();
for (let i = 1; i <= 7; i++) {
q.enqueue(i); //[1,2,3,4,5,6]
}
console.log(q.peek()); // 1
Stack
Stack is a collection data structure providing first-in-first-out semantics (FIFO). In JS there are built-in arrays methods push and pop for implementing stack.
let stack = [];
stack.push(1); // [1]
stack.push(2); // [1,2]
stack.pop(); // 2
//Reverse a string using a stack
const reverseStr = function(str){
let stack = [];
for (let i = 0; i < str.length; i++) {
stack.push(str[i]);
}
let reverseStr = '';
while (stack.length > 0) {
reverseStr += stack.pop();
}
return reverseStr;
}
console.log(reverseStr('JavaScript Stack')); // "kcatS tpircSavaJ"
Map
Map is a collection of key-value pairs (similar to JS object). Thanks to ES6 JS now have build-in Map object.
ES6 also introduced the WeakMap object to JavaScript. So what is the difference between object, Map and WeakMap in JS?
Map and WeakMap allow to use objects as keys (unlike normal objects in JS).
The difference between Map and WeakMap lies in how the objects that are used as keys are treated during garbage collection. In very simple words Map doesn't allow garbage collector to remove deleted references to their keys, and WeakMap allows.
var mapPerson = new Map([ ["firstname", "bob"], ["lastname", "smith"], ["age", 36] ]);
//Map methods
mapPerson.set('city', 'NY');
mapPerson.has('age'); // true
mapPerson.get('age'); // 36
map.delete('lastname'); //true
for (const k of mapPerson.keys()) {
console.log(k)
}
for (const v of mapPerson.values()) {
console.log(v)
}
for (const [k, v] of mapPerson) {
console.log(k, v)
}
Set
ES6 also provides one more coleection of values: Set is a collection of unique values
let set = new Set();
let john = { name: "John" };
let pete = { name: "Pete" };
let mary = { name: "Mary" };
// visits, some users come multiple times
set.add(john);
set.add(pete);
set.add(mary);
set.add(john);
set.add(mary);
// set keeps only unique values
alert( set.size ); // 3
for (let user of set) {
alert(user.name); // John (then Pete and Mary)
}
Tree
function Node(data) {
this.data = data;
this.parent = null;
this.children = [];
}
function Tree(data) {
var node = new Node(data);
this._root = node;
}
Tree.prototype.traverseDF = function(callback) {
(function recurse(currentNode) {
for (var i = 0, length = currentNode.children.length; i < length; i++) {
recurse(currentNode.children[i]);
}
callback(currentNode);
})(this._root);
};
Tree.prototype.traverseBF = function(callback) {
var queue = new Queue();
queue.enqueue(this._root);
currentNode = queue.dequeue();
while(currentNode){
for (var i = 0, length = currentNode.children.length; i < length; i++) {
queue.enqueue(currentNode.children[i]);
}
callback(currentNode);
currentNode = queue.dequeue();
}
};
Tree.prototype.contains = function(callback, traversal) {
traversal.call(this, callback);
};
//example
tree.contains(function(node){
if (node.data === 'two') console.log(node);
}, tree.traverseBF);
Tree.prototype.add = function(data, toData, traversal) {
let child = new Node(data),
parent = null;
let findParent = (node) => {
if (node.data === toData) parent = node;
}
this.contains(findParent, traversal);
if (parent) {
parent.children.push(child);
child.parent = parent;
} else {
throw new Error('Cannot add node to a non-existent parent.');
}
};
// example
var tree = new Tree('CEO');
tree.add('VP of Engineering', 'CEO', tree.traverseBF);
function findIndex(arr, data) {
for (var i = 0; i < arr.length; i++) {
if (arr[i].data === data) return i;
}
return undefined;
}
Tree.prototype.remove = function(data, fromData, traversal) {
let tree = this,
parent = null,
index;
let findParent = (node) => {
if (node.data === fromData) parent = node;
}
this.contains(findParent, traversal);
if (parent) {
index = findIndex(parent.children, data);
if (index === undefined) {
throw new Error('Node to remove does not exist.');
} else {
childToRemove = parent.children.splice(index, 1);
}
} else {
throw new Error('Parent does not exist.');
}
return childToRemove;
};
Note: traversDF is immediately-invoking function and it runs from the root of the tree to each of it child. or every node it calls callback function (e.g. print node)
Graph
A graph is a data structure where a node can have zero or more adjacent elements. The connection between two nodes is called edge. Nodes can also be called vertices. The degree is the number of edges connected to a vertex. If the edges are bi-directional, then it's an undirected graph. If the edges have a direction, then it's a directed graph or di-graph for short.
The adjacency matrix is one way of representing a graph using a two-dimensional array (NxN matrix). In the intersection of nodes, there is 1 (or other weight) if they are connected and 0 or - if they are not connected.
Adjacency List is one of the most common ways to represent graphs. Each node has a list of all the nodes connected to it. Graphs can be represented as an adjacency list using an Array (or HashMap) containing the nodes. Each node includes a list (Array, linked list, set, etc.) that lists its adjacent nodes.
function GraphNode(val){
this.val = val;
this.edges = new Map();
}
class Graph(){
constructor(){
this.vertices = [];
this.adjList = new Map();
}
addVertex(v){
this.adjList.set(v, []);
}
addEdge(v, w){
this.adjList.get(v).push(w);
this.adjList.get(w).push(v); //if unweight graph
}
printGraph(){
var vertices = this.adjList.keys();
for (var v of vertices){
var edges = this.adjList.get(v);
var conc = "";
for (var i of edges) conc += i + " ";
console.log(v + " -> " + conc);
}
}
}
dfsUtil = function(vert, visited){
visited[vert] = true;
console.log(vert);
var neighbours = this.adjList.get(vert);
for (var i in neighbours) {
var elem = neighbours[i];
if (!visited[elem]) dfsUtil(elem, visited);
}
}
Graph.prototype.dfs = function(v){
let visited = {};
dfsUtil.call(this, v, visited);
}
Graph.prototype.bfs = function(startingNode){
let visited = {};
let toVisit = new Queue();
visited[startingNode] = true;
toVisit.enqueue(startingNode);
while (!toVisit.isEmpty()) {
let v = toVisit.dequeue();
console.log(v);
let list = this.adjList.get(v);
for (var i in list) {
var neighbour = list[i];
if (!visited[neighbour]) {
visited[neighbour] = true;
toVisit.enqueue(neighbour);
}
}
}
}
Heap
Heap or priority queue is a tree-based structure, with a maximum (or minimum) element on the root. In a max heap, for any given child node parent node value is greater than or equal to value of child.
class Heap{
constructor(){
this.heap = [];
}
size(){
return this.heap.length;
}
insert(value){
this.heap.push(value);
this.bubbleUp();
}
bubbleUp(){
let ind = this.heap.length-1;
while(ind > 0){
let el = this.heap[ind],
parentInd = Math.floor((ind-1)/2),
parent = this.heap[parentInd];
if(parent >= el) break;
//else swap
this.heap[ind] = parent;
this.heap[parentInd] = el;
ind = parentInd;
}
}
//extract max from heap
remove(){
let max = this.heap[0];
//set the smalest element at the top and sink it down
this.heap[0]= this.heap.pop();
this.sinkDown(0);
return max;
}
sinkDown(ind){
let leftInd = 2*ind+1,
rightInd = 2*ind+2,
largest = ind;
const length = this.heap.length;
// if left child is greater than parent
if(leftInd <= length && this.heap[leftInd]>this.heap[largest] ){
largest = leftInd;
}
// if right child is greater than parent
if(rightInd <= length && this.heap[rightInd]>this.heap[largest]) {
largest = rightInd;
}
// swap
if(largest !== ind){
[this.heap[largest], this.heap[ind]] = [this.heap[ind], this.heap[largest]]
this.sinkDown(largest);
}
}
}