# 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

Big ‘O’ Notation

### 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 =[];
}

{
this.data.unshift(arg);
}

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

}

const q = new Queue();
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 = [];
}

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())
{
}
if(sourceTwo.peek())
{
}
}

return queueThree;
}```

test cases:

```const queueOne = new Queue();
const queueTwo = new Queue();
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();
}

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;
}
}```

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

```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(){
}
insertFirst(data){
}

size(){
let counter =0;

while(node){
counter++;
node = node.next;
}

return counter;
}

getFirst(){
}

getLast(){

while(node)
{
if(node.next){
node = node.next;
}
else{
return node;
}
}

return null;
}

clear(){
}

removeFirst(){
}

removeLast(){

return;
}

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.insertAt(data, this.size());
}

// insertLast(data){
// }

// while(node.next)
// {
// node = node.next;
// }

// node.next = new Node(data);
// }

getAt(index){
let counter = 0;

while(node){
if(counter === index){
return node;
}
node = node.next;
counter++;
}

return null;
}

// getAt(index){
// if(this.size() < index)
// return null;

// let counter = 0;

// while(counter !== index){
// node = node.next;
// counter++;
// }

// return node;
// }

removeAt(index){

if(index === 0){
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){
return;
}

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

forEach(fn) {
let counter = 0;
while(node){
fn(node, counter);
node = node.next;
counter++;
}
}

*[Symbol.iterator](){
while(node){
yield node;
node = node.next;
}
}
}```

Optimized code

```class LinkedList {
constructor(){
}

insertAt(data,index){
if(index ===0){
return;
}

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

insertFirst(data){
this.insertAt(data,0);
}

// insertLast(data){
// }

// 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.insertAt(data, this.size());
}

size(){
let counter =0;

while(node){
counter++;
node = node.next;
}

return counter;
}

getAt(index){
let counter = 0;

while(node){
if(counter === index){
return node;
}
node = node.next;
counter++;
}

return null;
}

// getAt(index){
// if(this.size() < index)
// return null;

// let counter = 0;

// while(counter !== index){
// node = node.next;
// counter++;
// }

// return node;
// }

getFirst(){
return this.getAt(0);
}

getLast(){

// while(node)
// {
// if(node.next){
// node = node.next;
// }
// else{
// return node;
// }
// }

// return null;

return this.getAt(this.size() - 1);
}

clear(){
}

removeFirst(){
this.removeAt(0);
}

removeLast(){

// return;
// }

// while(node.next){
// previous = node;
// node = node.next;
// }

// previous.next = null;
this.removeAt(this.size() - 1);
}

removeAt(index){

if(index === 0){
return;
}

const previous = this.getAt(index-1);
const node = this.getAt(index+1);

if(previous){
previous.next = node;
}
return;
}

forEach(fn) {
let counter = 0;
while(node){
fn(node, counter);
node = node.next;
counter++;
}
}

*[Symbol.iterator](){
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) {
{
return false;
}
{
return false;
}