data-structure.js

// https://blog.logrocket.com/know-your-javascript-data-structures/


/*
* STACK
* LIFO - Last in, First out
* - Need to accept a value
* - Add that value to top of our Stack
* - Track the length of our stack to track stack's index
*/
class Stack {
	constructor() {
		// create our stack, which is an empty object
		this._storage = {};
		this._length = 0; // our length
	}

	// this method will push value onto the top of the stack
	push(value) {
		// add value to the top of our stack
		this._storage[this._length] = value;
		// value was added, increase length
		this._length++;
	}

	// this method is responsible for popping off last value
	pop() {
		// get last value so we can return it
		const lastVal = this._storage[--this._length];
		// now remove item which is the length -1
		delete this._storage[--this._length];
		// decrement the length
		this._length--;
		// return last value
		return lastVal;
	}

	// this will peek at the last value added to the stack
	peek() {
		const lastVal = this._storage[--this._length];
		return lastVal;
	}
}

let stacki = new Stack();
stacki.push('Hello'); // Stack { _storage: { 0: 'Hello' }, _length: 1 }
stacki.pop(); // Hello
stacki; // Stack { _storage: { 0: 'Hello' }, _length: -2 }
stacki.peek(); // undefined || Hello



/*
* QUEUE
* FIFO - First in, First out
* 
* 
* 
*/
class Queue {
  constructor() {
    // similar to above we have an object for our data structure
    // and we also have a variable to keep track of the length
    this.queue = {}
    this.length = 0
    // this is a new variable which tracks the head
    this.head = 0
  }

  enqueue(value) {
		// add key to length + head to our object with value param
		this.queue[this.length + this.head] = value;
		this.length++;
  }

  dequeue() {
		// get a refecense to our first val so we can return it
		const firstVal = this.queue[this.head];
		// now delete this from our queue
		delete this.queue[this.head];
		// decrement our length
		this.length--;
		// increment our head to next node
		this.head++;
		// return firstVal?
		return firstVal;
  }

  peek() {
		// simply return the value at our head
		return this.queue[this.head];
  }
}

let queueki = new Queue();
queueki; // Queue { queue: {}, length: 0, head: 0 }
queueki.enqueue('First');
queueki; // Queue { queue: { 0: 'First' }, length: 1, head: 0 }
queueki.enqueue('Second');
queueki; // Queue { queue: { 0: 'First', 1: 'Second' }, length: 2, head: 0 }
queueki.dequeue(); // First
queueki; // Queue { queue: { 1: 'Second' }, length: 1, head: 1 }
queueki.dequeue(); // Second




/*
* LINKED LIST
* FIFO - First in, First out
*  [5| ]->[10| ]->[37| ]->Null
*   ^ Head
* Each node in a linked list has a data value and a next value.
* Below, 5 is the data value, and the next value points to the next node, i.e., the node that has the value 10.
*/
// const myLinkedList = {
//     head: {
//         value: 5
//         next: {
//             value: 10           
//             next: {
//                 value: 37
//                 next: null
//             }
//         }
//     }
// };
class LinkedList {
  constructor(value) {
    this.head = {value, next: null}
    this.tail = this.head
  }

	// insert will add to the end of our linked list
	insert(value) {
		/* create the node */
		const node = {value, next: null}
		/* set the next property of the tail = to the new node */
		this.tail.next = node;
		/* the new node is now the tail */
		this.tail = node;
	}

	removeNode(val) {
		/* begin at the head */
		let currentNode = this.head
		/* we need to hold reference to the previous node */
		let previousNode
		/* while we have a node i.e. not passed the tail */
		while(currentNode) {
			/* if we find our value then break out */
			if(currentNode.value === val) {
					break;
			}
			/* with no value found currentNode we set this to previousNode */
			previousNode = currentNode
			/* we get the next node and assign it to currentNode  */
			currentNode = currentNode.next
		}
		/* we return undefined as we have found no node with that value  */
		if (currentNode=== null) {
			return false;
		}

		// if the node is the head then we set our head to the next value
		// of the head node
		if (currentNode === this.head) {
			this.head = this.head.next;
			return;
		}
		/* so we remove our node by setting the node before it to the node in front of it */  
		previousNode.next = currentNode.next
	}

	removeTail() {
		let currentNode = this.head;
		let previousNode;
		while (currentNode) {
			/* the tail is the only node without a `next` value, so if no next value is present, then this must be our tail */
			if (!currentNode.next) {
				break;
			}
			// get a reference to our previous node
			previousNode = currentNode;
			// move onto the next node
			currentNode = currentNode.next;
		}
		// to remove the tail, we set the previousNode.next to null
		previousNode.next = null;
	}
}

const linki = new LinkedList()
linki; // LinkedList { head: { value: undefined, next: null }, tail: { value: undefined, next: null } }
linki.insert("Bill");
linki; // LinkedList { head: { value: undefined, next: { tail: { value: 'Bill', next: null } }
linki.insert("Jill");
linki; // LinkedList { head: { value: undefined, next: { value: 'Bill', next: [Object] } }, tail: { value: 'Jill', next: null } }
linki.removeNode(undefined);
linki; // LinkedList { head: { value: 'Bill', next: { value: 'Jill', next: null } }, tail: { value: 'Jill', next: null } }





/*
* HASH TABLE
* A hash table is a data structure that implements an associative array,
* which means it maps keys to values. A JavaScript object is a hash table, 
* as it stores key-value pairs.
* hashThis('i want to hash this') => 7
*/
class HashTable {
  constructor(size) {
    // define the size of our hash table, which will be used in our hashing function
    this.size = size;
    this.storage = [];
  }

	insert(key, value) {
		// will give us an index in the array
		const index = this.myHashingFunction(key, this.size);
		// handle collision - hash function returns the same
		// index for a different key - in complicated hash functions it is very unlkely
		// that a collision would occur
		if (!this.storage[index]) {
			this.storage[index] = [];
		}
		// push our new key value pair
		this.storage[index].push([key, value]);
	}

	get(key) {
		const index = this.myHashingFunction(key, this.size);
		let arrayAtIndex = this.storage[index];
		if (arrayAtIndex) {
			for (let i = 0; i < arrayAtIndex.length; i++) {
				const pair = arrayAtIndex[i];
				if (pair[0] === key) {
					// return the value
					return pair[1];
				}
			}
		}
	}

	remove(key) {
			// first we get the index of our key
			// remember, the hashing function will always return the same index for the same
			// key
			const index = this.myHashingFunction(key, this.size);
			// remember we could have more than one array at an index (unlikely)
			let arrayAtIndex = this.storage[index];
			if (arrayAtIndex) {
				// let's loop over all the arrays at that index
				for (let i = 0; i < arrayAtIndex.length; i++) {
					// get the pair (a, 1)
					let pair = arrayAtIndex[i];
					// check if the key matches the key param
					if (pair[0] === key) {
						// delete the arrayatindex
						delete arrayAtIndex[i];
						// job done, so break out of the loop
						break;
					}
				}
			}
	}

  // this is how we will hash our keys
  myHashingFunction(str, n) {
    let sum = 0;
    for (let i = 0; i < str.length; i++) {
      sum += str.charCodeAt(i) * 3;
    }
    return sum % n;
  }
}

const hashi = new HashTable(5);
hashi; // HashTable { size: 5, storage: [] }
hashi.insert("a", 1);
hashi.insert("b", 2);
hashi; // HashTable { size: 5, storage: [ <1 empty item>, [ [Array] ], <2 empty items>, [ [Array] ] ] }
hashi.remove("a");
hashi; // HashTable { size: 5, storage:  [ <1 empty item>, [ <1 empty item> ], <2 empty items>, [ [Array] ] ] }
hashi.get("b"); // 2





/*
* BINARY SEARCH TREE
* - Root: This is the very top node of a tree structure and does not have a parent 
* - Parent: It is a child of a node but also the parent of a node
* - Child: This node is the child of a node and does not necessarily have a child
* 
* In a binary search tree, each node either has zero, one, or two children.
* The child on the left is called the left child, and the child on the right 
* is the right child. In a binary search tree, the child on the left must be 
* smaller than the child on the right.
*/
class Tree {
   constructor(value) {
     this.root = null
   }

	add(value) {
			// if we do not have a root, then we create one
			if (this.root === null) {
				this.root = new Node(value);
				return;
			}
			let current = this.root;
			// keep looping
			while (true) {
				// go left if our current value is greater
				// than the value passed in
				if (current.value > value) {
					// if there is a left child then run the
					// loop again
					if (current.left) {
						current = current.left;
					} else {
						current.left = new Node(value);
						return;
					}
				}
				// the value is smaller, so we go right
				else {
					// go right
					// if there is a left child then run the
					// loop again
					if (current.right) {
						current = current.right;
					} else {
						current.right = new Node(value);
						return;
					}
				}
			}
	}

	contains(value) {
		// get the root
		let current = this.root;
		// while we have a node
		while (current) {
			// check if our current node has the value
			if (value === current.value) {
				return true; // leave the function
			}
			// we decide on the next current node by comparing our value
			// against current.value - if its less go left else right
			current = value < current.value ? current.left : current.right;
		}
		return false;
	}
}

class Node {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

const treeti = new Tree();
treeti; // Tree { root: null }
treeti.add(2);
treeti; // Tree { root: Node { value: 2, left: null, right: null } }
treeti.add(5);
treeti.add(3);
treeti; // Tree { root:  Node { value: 2, left: null, right: Node { value: 5, left: [Object], right: null } } }
treeti.contains(5); // true
treeti.contains(4); // false