Notes

//QUEUE <FIFO>

function createQueue() {
const queue = [];

return {
enqueue(item) {
queue.unshift(item);
},
dequeue() {
return queue.pop();
},
peek() {
return queue[queue.length - 1];
},
get length() {
return queue.length;
},
isEmpty() {
return queue.length == 0;
}
};
}

//STACK <LIFO>

function createStack() {
const array = [];

return {
push(item) {
array.push(item);
},
pop() {
return array.pop();
},
peek() {
return array[array.length - 1];
},
get length() {
return array.length;
},
isEmpty() {
return array.length == 0;
}
};
}

//LINKED LIST

function createNode(value) {
return {
value,
next: null
};
}

function createLinkedList() {
return {
head: null,
tail: null,
length: 0,
push(value) {
const node = createNode(value);
if (this.head === null) {
this.head = node;
this.tail = node;
this.length++;
return node;
}
this.tail.next = node;
this.tail = node;
this.length++;
},
isEmpty() {
return this.length === 0;
},

pop() {
if (this.isEmpty()) {
return null;
}
const node = this.tail;

if (this.head === this.tail) {
this.head = null;
this.tail = null;
this.length--;
return node;
}

let current = this.head;
let penultimate;
while (current) {
if (current.next === this.tail) {
penultimate = current;
break;
}

current = current.next;
}

penultimate.next = null;
this.tail = penultimate;
this.length--;

return node;
},
get(index) {
if (index < 0 || index > this.length) {
return null;
}

if (index === 0) {
return this.head;
}

let current = this.head;
let i = 0;
while (i < index) {
i++;
current = current.next;
}

return current;
},
delete(index) {
if (index < 0 || index > this.length) {
return null;
}

if (index === 0) {
const deleted = this.head;

this.head = this.head.next;
this.length--;

return deleted;
}

let current = this.head;
let previous;
let i = 0;

while (i < index) {
i++;
previous = current;
current = current.next;
}

const deleted = current;
previous.next = current.next;
this.length--;

return deleted;
},
print() {
const values = [];
let current = this.head;

while (current) {
values.push(current.value);
current = current.next;
}

return values.join(" => ");
}
};
}

//GRAPH

function createNode(key) {
const neighbors = []

return {
key,
neighbors,
addNeighbor(node) {
neighbors.push(node)
}
}
}

function createGraph(directed = false) {
const nodes = [];
const edges = [];

return {
directed,
nodes,
edges,

addNode(key) {
nodes.push(createNode(key));
},

getNode(key) {
return nodes.find(node => node.key === key);
},
addEdge(node1Key, node2Key) {
const node1 = this.getNode(node1Key);
const node2 = this.getNode(node2Key);

node1.addNeighbor(node2);
edges.push(`${node1Key}${node2Key}`);

if (!directed) {
node2.addChild(node1);
}
},
print() {
return nodes
.map(({ children, key }) => {
let result = `${key}`;

if (children.length) {
result += ` => ${children.map(node => node.key).join(" ")}`;
}

return result;
})
.join("n");
}
};
}


//Breadth First Search for Graphs

function breadthFirstSearch(startingNodeKey, visitFn) {
const startingNode = this.getNode(startingNodeKey);

const visited = nodes.reduce((acc, node) => {
acc[node.key] = false;
return acc;
}, {});
const queue = createQueue();
queue.enqueue(startingNode);
while (!queue.isEmpty()) {
const currentNode = queue.dequeue();

if (!visitedHash[currentNode.key]) {
visitFn(currentNode);
visited[currentNode.key] = true;
}

currentNode.children.forEach(node => {
if (!visited[node.key]) {
queue.enqueue(node);
}
});
}
}

//Depth First Search for Graphs

function depthFirstSearch(startingNodeKey, visitFn) {
const startingNode = this.getNode(startingNodeKey)
const visitedHash = nodes.reduce((acc, cur) => {
acc[cur.key] = false
return acc
},
{}
)
function explore(node) {
if (visitedHash[node.key]) {
return
}

visitFn(node)
visited[node.key] = true

node.neighbors.forEach(child => {
explore(child)
})
}
}

//TREE

function createNode(key) {
const children = []

return {
key,
children,
addChild(childKey) {
const childNode = createNode(childKey)
children.push(childNode)
return childNode
}
}
}

function createTree(rootKey) {
const root = createNode(rootKey);

return {
root,
print() {
let result = "";

function traverse(node, visitFn, depth) {
visitFn(node, depth);

if (node.children.length) {
node.children.forEach(child => {
traverse(child, vistFn, depth + 1);
});
}
}
function addKeyToResult(node, depth) {
result += result.length === 0 ? node.key : `n${" ".repeat(depth * 2)}`;
}
return result;
}
};
}

//BINARY TREE


function createBinaryNode(key) {
return {
key,
left: null,
right: null,
addLeft(leftKey) {
const newLeft = createBinaryNode(leftKey)
this.left = newLeft
return newLeft
},
addRight(rightKey) {
const newRight = createBinaryNode(rightKey)
this.right = newRight
return newRight
}
}
}

const TRAVERSALS = {
IN_ORDER: (node, visitFn) => {
if (node !== null) {
TRAVERSALS.IN_ORDER(node.left, visitFn);
visitFn(node);
TRAVERSALS.IN_ORDER(node.right, visitFn);
}
},
PRE_ORDER: (node, visitFn) => {
if (node !== null) {
visitFn(node);
TRAVERSALS.PRE_ORDER(node.left, visitFn);
TRAVERSALS.PRE_ORDER(node.right, visitFn);
}
},
POST_ORDER: (node, visitFn) => {
if (node !== null) {
TRAVERSALS.POST_ORDER(node.left, visitFn);
TRAVERSALS.POST_ORDER(node.right, visitFn);
visitFn(node);
}
}
};



function createBinaryTree(rootKey) {
const root = createBinaryNode(rootKey)

return {
root,
print(orderType = 'IN_ORDER') {
let result = ''

const visitFn = node => {
result += result.length === 0 ? node.key : ` => ${node.key}`
}

TRAVERSALS[orderType](this.root, visitFn)

return result
}
}
}