Javascript Data Structures

Debunking time complexity notation Name Notation Description Constant Time 1 No Matter how many elements we’re working with, the algorithm/operation will always take the same amount of time Logarithmic Time log(n) if doubling the number

Debunking time complexity notation

NameNotationDescription
Constant Time1No Matter how many elements we’re working with, the algorithm/operation will always take the same amount of time
Logarithmic Timelog(n)if doubling the number of elements you are iterating doesn’t double the amount of work. Always assume that searching operation are log(n)
Linear TimenIterating through all elements in a collection of data. If you see a for loop spanning from ‘0’ to ‘array.length’ we have ‘n’ or linear runtime. number of elements is the time taken.
Quasilinear Timen*log(n)if doubling the number of elements you are iterating doesn’t double the amount of work.
Always assume that any sorting operation is n*log(n)
Quadratic Timen^2 or nxnEvery element in a collection has to be compared to every other element. ” The handshake problem”
Exponential Time2^non adding single element to a collection, the processing power required doubles.

Big ‘O’ Notation

O(n)Linear
O(1)Constant
O(n^2)Quadratic

Fibonacci Series

Print out the n-th entry in the Fibonacci series. The Fibonacci series is an ordering of numbers where each number is the sum of the preceding two.
Example of Series [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Given a number N return the Fibonacci element at that position

Example: Fib(15) =610

function fib(n) {
	let arr=[0,1];

	for(let i=1; i<n; i++)
	{
		arr[i+1] = arr[i] + arr[i-1];
	}

	return arr[arr.length-1];

}


console.log(fib(15));

Recursive solution with Memoize

function memoize(fn)
{
	//stores all the calls to our function here we mean fib function.
	const cache ={};
    
	//...args basically means arguments of our function 
	//i mean the function that is being sent to the memoize 
	//can contain n number of arguments so this takes care of it.
	//It takes all the arguments and assign them as an array 
	//to this variable called args
    return function(...args)
    {
		if(cache[args])
		{
        	return cache[args];
        }
        
		//when ever we call a function with an array of arguments
		//then we have to use the Apply helper
        const result = fn.apply(this, args);
        cache[args] = result;
        return result;
    }
}

function fib(n) {
	if(n<2)
	{
		return n;
	}

	return fib(n-1) + fib(n-2);
}

	fib = memoize(fib);

console.log(fib(15));

The Queue

These are mainly used as part of run time optimization. It follows FIFO i.e “First In First Out”. Below is a basic structure of a queue.

class Queue {

	constructor(){
		this.data =[];
	}
 
	add(arg)
	{
		this.data.unshift(arg);
	}
 
	remove()
	{
 		return this.data.pop();
	}
 
}

const q = new Queue();
q.add(1);
q.remove(); // returns 1;

Queue Problem: Weave

Implement a weave function which receives 2 queues as arguments and combine the contents of each into a new, third queue. The newly formed queue should have alternating content of the two queues. Also if the queues are not of the same size when combining undefined shouldn’t be inserted. Only use add, remove and peek of array methods to get it done.

Also implement a peek function which doesn’t remove the element from the queue.

Basic Queue Class:

class Queue {
  constructor() {
    this.data = [];
  }

  add(record) {
    this.data.unshift(record);
  }

  remove() {
    return this.data.pop();
  }
  
  peek() {
	return this.data[this.data.length-1];
  }
}

weave function:

function weave(sourceOne, sourceTwo) {
	
	const queueThree = new Queue();
	
	//while(sourceOne.data.length+sourceTwo.data.length>0)
	while(sourceOne.peek() || sourceTwo.peek())
	{
		if(sourceOne.peek())
		{
			queueThree.add(sourceOne.remove());
		}
		if(sourceTwo.peek())
		{
			queueThree.add(sourceTwo.remove());
		}
	}

	return queueThree;
}

test cases:

const queueOne = new Queue();
queueOne.add(1);
queueOne.add(2);
queueOne.add(2);
queueOne.add(2);
queueOne.add(2);
queueOne.add(2);
queueOne.add(2);
const queueTwo = new Queue();
queueTwo.add('Hi');
queueTwo.add('There');
const q = weave(queueOne, queueTwo);

console.log(q);
q.remove(); 
q.remove();
q.remove();
q.remove();
q.remove();
q.remove();
q.remove();

The Stack

It follows FILO “First In Last Out” and is used as part of performance optimization.

class Stack{
	constructor(){
		this.data =[];
	}

	push(arg){
		this.data.shift(arg);
	}

	pop(){
		return this.data.pop();
	}

	peek(){
		return this.data[this.data.length -1 ;
	}
}

let q = new Stack();
q.push(1);
q.push(2);
q.push(3);
q.push(4);
q.push(5);
console.log(q);

console.log(q.peek());

console.log(q.pop());
console.log(q.pop());
console.log(q.pop());
console.log(q.pop());
console.log(q.pop());

Implement a Queue using a Stack

class Queue {
	constructor(){
		this.first = new Stack();
		this.second = new Stack();
	}
	
	add(arg){
		this.first.push(arg);
	}
	
	remove(){
		while(this.first.peek()){
			this.second.push(this.first.pop());
		}
		
		let record = this.second.pop();
		
		while(this.second.peek()){
			this.first.push(this.second.pop());
		}
		
		return record;
	}
	
	peek(){
		while(this.first.peek()){
			this.second.push(this.first.pop());
		}
		
		let record = this.second.peek();
		
		while(this.second.peek()){
			this.first.push(this.second.pop());
		}
		
		return record;
	}
}

Linked Lists

It is an ordered collection of data and maintains a linear structure but the elements are not stored at contiguous memory locations. Data +next location form a node and collection of these become the linked list

Create a Linked List Class which should be initialized with head as null. This should have the below methods

FunctionArgumentReturnDescription
Insert first(data)User should be able to insert a new node at the head and in case if other nodes are already linked they should be pointed by the new node.
size(integer)Should return the number of nodes in the list.
getFirst(Node)Should return the first node of the list
getLast(Node)Should return the last node of the linked list
clearShould clear the linked list
removeFirstShould remove only the first element.
removeLastShould remove only the last element
insertLast(data)Should insert a new node at the last
getAt(integer)(Node)returns the node at the provided index
removeAt(integer)removes the node at the provided index
insertAt(data,integer)insert a new node at the provided index. if index is out of bound add it at the end
foreach(function)Calls the provided function with every node of the chain
for…of LoopShould be compatible as the subject of a ‘for…of’ loop
class Node {
	constructor(data, next = null){
		this.data = data;
		this.next = next;
	}
}

//test
const n = new Node('There');
n.data // 'Hi'
n.next // null
const n2 = new Node('Hi', n);
n.next // returns n
class LinkedList {
	constructor(){
		this.head = null;
	}
	insertFirst(data){
		this.head = new Node(data,this.head);
	}

	size(){
		let counter =0;
		let node = this.head;
		
		while(node){
			counter++;
			node = node.next;
		}
		
		return counter;
	}

	getFirst(){
		return this.head;
	}

	getLast(){
		if(!this.head) return;
		
		let node = this.head;
		while(node)
		{
			if(node.next){
				node = node.next;
			}
			else{
				return node;	
			}
		}
		
		return null;
	}

	clear(){
		this.head = null;
	}

	removeFirst(){
		if(!this.head) return;
		this.head = this.head.next;
	}

	removeLast(){
		if(!this.head) return;
				
		if(!this.head.next){
			this.head = null;
			return;
		}
		
		let previous = this.head;
		let node = this.head.next;
		
		while(node.next){
			previous = node;
			node = node.next;
		}
		
		previous.next = null;
	}

	insertLast(data){
		const last = this.getLast();
		
		if(last){
			last.next = new Node(data);
		}else{
			this.head = new Node(data);
		}
		this.insertAt(data, this.size());
	}

	// insertLast(data){
		// if(!this.head) {
			// this.head = new Node(data);
		// }
			
		// let node = this.head;
		
		// while(node.next)
		// {
			// node = node.next;
		// }
		
		// node.next = new Node(data);
	// }

  	getAt(index){
		let counter = 0;
		let node = this.head;
		
		while(node){
			if(counter === index){
				return node;
			}
			node = node.next;
			counter++;
		}
		
		return null;
	}
	
	// getAt(index){
		// if(this.size() < index)
			// return null;
		
		// let counter = 0;
		// let node = this.head;
		
		// while(counter !== index){
			// node = node.next;
			// counter++;
		// }
		
		// return node;
	// }

	removeAt(index){
		
		if(!this.head) return;
		if(index === 0){
			this.head = this.head.next;
			return;
		}
		
		const previous = this.getAt(index-1);
		const node = this.getAt(index+1);
		
		if(previous){
			previous.next = node;
		}
		return;
	}

	insertAt(data,index){	
		if(index ===0){
			this.head = new Node(data,this.head);
			return;
		}
		
		const previous = this.getAt(index-1) || this.getLast();
		previous.next = new Node(data, previous.next);
		return;
	}

	forEach(fn) {
		let node = this.head;
		let counter = 0;
		while(node){
			fn(node, counter);
			node = node.next;
			counter++;
		}
	}
	
	*[Symbol.iterator](){
		let node = this.head;
		while(node){
			yield node;
			node = node.next;
		}
	}
}

Optimized code

class LinkedList {
	constructor(){
		this.head = null;
	}
		
	insertAt(data,index){	
		if(index ===0){
			this.head = new Node(data,this.head);
			return;
		}
		
		const previous = this.getAt(index-1) || this.getLast();
		previous.next = new Node(data, previous.next);
		return;
	}
	
	insertFirst(data){
		//this.head = new Node(data,this.head);
		this.insertAt(data,0);
	}
	
	// insertLast(data){
		// if(!this.head) {
			// this.head = new Node(data);
		// }
			
		// let node = this.head;
		
		// while(node.next)
		// {
			// node = node.next;
		// }
		
		// node.next = new Node(data);
	// }
	
	insertLast(data){
		// const last = this.getLast();
		
		// if(last){
			// last.next = new Node(data);
		// }else{
			// this.head = new Node(data);
		// }
		this.insertAt(data, this.size());
	}
	
	size(){
		let counter =0;
		let node = this.head;
		
		while(node){
			counter++;
			node = node.next;
		}
		
		return counter;
	}
	
  	getAt(index){
		let counter = 0;
		let node = this.head;
		
		while(node){
			if(counter === index){
				return node;
			}
			node = node.next;
			counter++;
		}
		
		return null;
	}
	
	// getAt(index){
		// if(this.size() < index)
			// return null;
		
		// let counter = 0;
		// let node = this.head;
		
		// while(counter !== index){
			// node = node.next;
			// counter++;
		// }
		
		// return node;
	// }
	
	getFirst(){
		//return this.head;
		return this.getAt(0);
	}
	
	getLast(){
		// if(!this.head) return;
		
		// let node = this.head;
		// while(node)
		// {
			// if(node.next){
				// node = node.next;
			// }
			// else{
				// return node;	
			// }
		// }
		
		// return null;
		
		return this.getAt(this.size() - 1);
	}
	
	clear(){
		this.head = null;
	}
	
	removeFirst(){
		// if(!this.head) return;
		// this.head = this.head.next;
		this.removeAt(0);
	}
	
	removeLast(){
		// if(!this.head) return;
				
		// if(!this.head.next){
			// this.head = null;
			// return;
		// }
		
		// let previous = this.head;
		// let node = this.head.next;
		
		// while(node.next){
			// previous = node;
			// node = node.next;
		// }
		
		// previous.next = null;
		this.removeAt(this.size() - 1);
	}

	removeAt(index){
		
		if(!this.head) return;
		if(index === 0){
			this.head = this.head.next;
			return;
		}
		
		const previous = this.getAt(index-1);
		const node = this.getAt(index+1);
		
		if(previous){
			previous.next = node;
		}
		return;
	}
	
	forEach(fn) {
		let node = this.head;
		let counter = 0;
		while(node){
			fn(node, counter);
			node = node.next;
			counter++;
		}
	}
	
	*[Symbol.iterator](){
		let node = this.head;
		while(node){
			yield node;
			node = node.next;
		}
	}

}

Binary Search Tree

A tree containing 2 node are called as binary tree. if the elements are arranged based on a condition then its called binary search tree. example could be if node.data = 10 and new insertion is 5 we could have a condition like if new insertion is less then data then insert left else right. this makes transversal easy for us.

  • implement node class to create a binary search tree. the constructor should initialize values data, left and right.
  • implement insert method which accepts an argument data then inserts it at a appropriate location in the tree
  • implement a contain method which accepts data as an argument and returns a node in the tree with the same value
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(data === this.data) return this;
		
		if(data<this.data && this.left){
			return this.left.contains(data);
		}
		else if(data>this.data && this.right){
			return this.right.contains(data);
		}
		
		return null;
	}
}

Given a node, validate the binary search tree, ensuring that every node’s left hand child is less than the parent node’s value, and that every node’s right hand child is greater than the parent

function validate(node, min = null, max = null) {
	let head = node;
	if(min !== null && head.data<min)
	{
		return false;
	}
	if(max !== null && head.data>max)
	{
		return false;
	}
	
	if(head.left && !validate(head.left,min,head.data)){
		return false;
	}
	if(head.right && !validate(head.right,head.left,max)){
		return false;
	}
	
	return true;

}

Leave a Reply

Your email address will not be published. Required fields are marked *