secretgspot
11/20/2019 - 10:07 PM
Data Structures
// 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