Data structures :: code
Stack:
A stack has storage { } and length
Stack { storage: {}, length: 0 }
Stack { storage: { '0': 'input' }, length: 1 }
Stack { storage: { '0': 'input', '1': 'input2' }, length: 2 }
Stack { storage: { '0': 'input' }, length: 1 }
function Stack () {
this.storage = {};
this.length = 0;
}
Stack.prototype.push = function (value) {
Data structures :: code 1
this.length++;
this.storage[this.length] = value;
return true;
};
Stack.prototype.pop = function () {
if (this.length) {
const res = this.storage[this.length];
delete this.storage[this.length];
this.length--;
return res;
}
return null;
};
Stack.prototype.size = function () {
return this.length;
};
//let example = new Stack()
//console.log(example)
//example.push('input')
Queue:
A queue has storage { }, a start, and end
Data structures :: code 2
Queue { storage: {}, start: 1, end: 1 }
Queue { storage: { '1': 'input' }, start: 1, end: 2 }
Queue { storage: { '1': 'input', '2': 'input2' }, start: 1, end: 3 }
Queue { storage: { '2': 'input2' }, start: 2, end: 3 }
function Queue () {
this.storage = {};
this.start = 1;
this.end = 1;
Queue.prototype.enqueue = function (value) {
this.storage[this.end] = value;
this.end++;
return true;
};
Queue.prototype.dequeue = function () {
if (this.size()) {
const res = this.storage[this.start];
delete this.storage[this.start];
this.start++;
return res;
}
return null;
};
Queue.prototype.size = function () {
return this.end - this.start;
};
Data structures :: code 3
//let example = new Queue()
//console.log(example)
//example: Queue { storage: {}, start: 1, end: 1 }
Linked List:
A linked list has a head and a tail.
LinkedList { head: null, tail: null }
LinkedList {
head: LinkedListNode { value: 'input', next: null },
tail: LinkedListNode { value: 'input', next: null }
LinkedList {
head: LinkedListNode {
value: 'input',
next: LinkedListNode { value: 'input2', next: null }
},
tail: LinkedListNode { value: 'input2', next: null }
}
LinkedList {
head: LinkedListNode { value: 'input2', next: null },
tail: LinkedListNode { value: 'input2', next: null }
}
Data structures :: code 4
false
function LinkedList () {
this.head = null;
this.tail = null;
function LinkedListNode (value) {
this.value = value;
this.next = null;
}
LinkedList.prototype.addToHead = function (value) {
const newNode = new LinkedListNode(value);
if (!this.head) this.head = this.tail = newNode;
else {
const prevHead = this.head;
this.head = newNode;
this.head.next = prevHead;
}
return true;
};
LinkedList.prototype.addToTail = function (value) {
const newNode = new LinkedListNode(value);
if (!this.head) this.head = this.tail = newNode;
else {
const prevTail = this.tail;
this.tail = prevTail.next = newNode;
}
return true;
};
LinkedList.prototype.removeHead = function () {
if (this.head) {
const prevHead = this.head;
if (prevHead.next) this.head = prevHead.next;
else this.head = this.tail = null;
return prevHead.value;
}
return null;
};
LinkedList.prototype.contains = function (value) {
let current = this.head;
while (current) {
if (current.value === value) return true;
current = current.next;
Data structures :: code 5
}
return false;
};
Double Linked List:
DoubleLinkedList { head: null, tail: null }
DoubleLinkedList {
head: LinkedListNode { value: 'input', next: null },
tail: LinkedListNode { value: 'input', next: null }
}
DoubleLinkedList {
head: <ref *1> LinkedListNode {
value: 'input',
next: LinkedListNode { value: 'input2', next: null, prev: [Circular *1] }
},
tail: <ref *2> LinkedListNode {
value: 'input2',
next: null,
prev: <ref *1> LinkedListNode {
value: 'input',
next: [Circular *2]
}
}
}
Data structures :: code 6
DoubleLinkedList {
head: LinkedListNode { value: 'input2', next: null, prev: null },
tail: LinkedListNode { value: 'input2', next: null, prev: null }
}
DoubleLinkedList { head: null, tail: null }
class DoubleLinkedList extends LinkedList {
// REMOVE-START
addToHead (value) {
const prevHead = this.head;
super.addToHead(value);
if (prevHead) prevHead.prev = this.head;
return true;
}
addToTail (value) {
const prevTail = this.tail;
super.addToTail(value);
if (prevTail) this.tail.prev = prevTail;
return true;
}
removeHead () {
const res = super.removeHead();
if (this.head && this.head.prev) this.head.prev = null;
return res;
}
removeTail () {
if (this.tail) {
const prevTail = this.tail;
if (prevTail.prev) {
this.tail = prevTail.prev;
this.tail.next = null;
} else this.tail = this.head = null;
return prevTail.value;
}
return null;
}
// REMOVE-END
}
Data structures :: code 7
Set:
Set {}
Set { input: true }
Set { input: true, input2: true }
true
Set { input2: true }
// let s = new Set(); -> Set {}
// s.add('potato') -> true
// s.contains('potato') -> true
// s.contains('banana') -> false
function Set () {}
Set.prototype.add = function (value) {
// {potato : true}
return this[value] = true
}
Set.prototype.contains = function (value) {
// does the value exist?
// if so, return true
Data structures :: code 8
// otherwise false
//Option 1
// if (this[value]) return true
// return false
//Option 2
return Boolean(this[value])
//Option 3
// return !!this[value]
// !undefined -> true
// !!undefined -> false
}
Set.prototype.remove = function (value) {
return delete this[value]
}
Tree:
a tree has a value, and children [ ]
Tree { value: undefined, children: [] }
Tree { value: 'input', children: [] }
Tree {
value: 'input',
children: [ Tree { value: 'input2', children: [] } ]
}
Data structures :: code 9
true
function Tree (value) {
// a tree has a value (or root) and a list of children (or branches)
// all branches should also be trees
// a tree with no branches is a leaf
this.value = value;
this.children = [];
}
Tree.prototype.addChild = function (node) {
this.children.push(node);
return true
}
Tree.prototype.containsRecursive = function (value) {
// verify the base case(s)
// verify that you can get to the base case in recursive calls
// either the value is in the root, or nowhere
// recursive case: value is in one of the children,
if (this.value === value) return true
for (let i = 0; i < this.children.length; i++) {
let child = this.children[i]
if (child.contains(value)) return true
}
return false
}
Tree.prototype.contains = function (value) {
const stack = [];
let current;
stack.push(this);
while (stack.length > 0) {
current = stack.pop();
if (current.value === value) return true;
else {
for (let i = 0; i < current.children.length; i++) {
stack.push(current.children[i]);
}
}
}
return false;
};
Data structures :: code 10
Hash Table:
A hash table has: size, storage, functions, and ‘used’ is to be used later for
resizing.
HashTable {
size: 10,
storage: { get: [Function: get], set: [Function: set] },
used: 0
}
HashTable {
size: 10,
storage: { get: [Function: get], set: [Function: set] },
used: 1
}
HashTable {
size: 10,
storage: { get: [Function: get], set: [Function: set] },
used: 2
}
input
Data structures :: code 11
HashTable {
size: 10,
storage: { get: [Function: get], set: [Function: set] },
used: 1
}
// const helpers = require('./hash-table-helpers');
// These are your helpers, they're used to generate
// the storage and get the hash respectively. For more
// information check the "hash-table-helpers.js" file.
//const Storage = helpers.Storage;
//const hash = helpers.hash;
function HashTable (size) {
this.size = size;
this.storage = Storage(size);
this.used = 0; // for self-resizing
HashTable.prototype.insert = function (key, value) {
const index = hash(key, this.size);
const head = this.storage.get(index);
let node = head;
while (node) {
if (node.key === key) {
node.value = value;
return true;
}
node = node.next;
}
const newNode = {key, value};
if (head) newNode.next = head;
this.storage.set(index, newNode);
this.used++;
this._checkSize();
return true;
};
HashTable.prototype.retrieve = function (key) {
const index = hash(key, this.size);
let node = this.storage.get(index);
while (node) {
if (node.key === key) return node.value;
node = node.next;
}
return undefined;
Data structures :: code 12
};
HashTable.prototype.remove = function (key) {
const index = hash(key, this.size);
let node = this.storage.get(index);
if (node) {
if (node.key === key) {
this.storage.set(index, node.next);
this.used--;
this._checkSize();
return true;
}
while (node.next) {
if (node.next.key === key) {
node.next = node.next.next;
this.used--;
this._checkSize();
return true;
}
node = node.next;
}
}
return false;
};
HashTable.prototype._checkSize = function () {
const ratio = this.used / this.size;
const min = 10;
if (ratio > 0.75) {
this._resize(this.size * 2);
return 'resizing up';
}
if (this.size > min && ratio < 0.25) {
this._resize(Math.floor(this.size / 2));
return 'resizing down';
}
return true;
};
HashTable.prototype._resize = function (newSize) {
const temp = {
size: newSize,
storage: Storage(newSize),
used: 0,
_checkSize: function () {return false;}
};
for (let i = 0; i < this.size; i++) {
let node = this.storage.get(i);
while (node) {
this.insert.call(temp, node.key, node.value);
node = node.next;
}
}
delete temp._checkSize;
Data structures :: code 13
Object.assign(this, temp);
return true;
};
module.exports = HashTable;
Data structures :: code 14
