know it Flashcards
what is the advantage of linked lists over arrays
you can add things to the beginning in constant time
queue.dequeue from scratch (singly linked list implementation)
dequeue(){
if(!this.first) return null;
var temp = this.first;
if(this.first === this.last) {
this.last = null;
}
this.first = this.first.next;
this.size--;
return temp.value;
}
SLL class
class SinglyLinkedList{
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}SLL.insert
insert(index, value) {
//if index is less than zero or greater than length, return false
if (index \< 0 || index \> list.length) {
return false;
}
//if index is same as length, push new node
if (index === list.length) {
list.push(value);
}
//if index is 0, unshift
if (index === 0 ) {
list.unshift(value);
}
//otherwise use get method but with \*index - 1\*, set next property to newly created node, and connect new node to old next node
else {
var newNode = new Node(value);
var previous = this.get(index - 1);
var next = this.get(index);
previous.next = newNode;
newNode.next = next;
this.length++;
}
return true;
//increment length, return true or false
}SLL.push
push(val) {
var node = new Node(val);
if (this.head === null) {
this.head = node;
//is this the same as setting it to node?
this.tail = this.head;
} else {
this.tail.next = node;
//didnt add this on first draft
this.tail = node;
}
this.length++;
//don't forget to return!
return this;
}what is the extractMax method of a binary heap
replace the max with the min, and then bubble everything back into the correct order
queue.enqueue from scratch
enqueue(val){
var newNode = new Node(val);
if(!this.first){
this.first = newNode;
this.last = newNode;
} else {
this.last.next = newNode;
this.last = newNode;
}
return ++this.size;
}stack.pop
pop() {
if (this.size === 0) {
return null;
} else {
var toPop = this.first;
if (this.first = this.last) {
this.last = null;
}
this.first = this.first.next;
this.size--
return toPop.val;
}
}time complexity for arrays
- access
- insertion
- removal
- built in sort method
access isn O(1) just like for objects
adding or removing something to the beginning of an array means you have to re-index every single element though, so that;s O(n),
try to add and remove things from the end, not the beginning
built in sort method is nlogN time but doesnt take any space
can you implement a priority queue from scratch?
class PriorityQueue {
constructor() {
this.elements = [];
}
enqueue(val, priority) {
let newNode = new Node(val, priority)
this.elements.push(newNode)
this.bubbleUp();
}
bubbleUp() {
let index = this.elements.length - 1;
const element = this.elements[index];
while(index \> 0) {
let parentIndex = Math.floor((index -1)/2)
let parent = this.elements[parentIndex];
if (element.priority \<= parent.priority) break;
this.elements[parentIndex] = element;
this.elements[index] = parent;
index = parentIndex;
}
}
dequeue() {
const max = this.elements[0];
const last = this.elements.pop();
if (this.elements.length \> 0) {
this.elements[0] = last;
this.bubbleDown;
}
return max;
}
bubbleDown() {
let index = 0;
const length = this.elements.length;
const element = this.elements[0];
while(true) {
let leftChildIndex = 2 \* index + 1;
let rightChildIndex = 2 \* index + 2;
let leftChild, rightChild;
let swapIndex = null;
//make sure that the children exist
if (leftChildIndex \< length) {
leftChild = this.elements[leftChildIndex]
if (leftChild.priority \> element.priority) {
swapIndex = leftChildIndex
}
}
if (rightChildIndex \< length) {
rightChild = this.elements[rightChildIndex];
if (rightChild.priority \> element.priority && rightChild.priority \> leftChild.priority) {
swapIndex = rightChildIndex;
}
}
if (swapIndex === null) break;
this.elements[index] = this.elements[swapIndex];
this.elements[swapIndex] = element;
index = swapIndex;
}
}
}
class Node {
constructor(val, priority) {
this.val = val;
this.priority = priority;
}
}
let ER = new PriorityQueue();
ER.enqueue(“cold”, 1)
ER.enqueue(“gunshot”, 5)
ER.enqueue(“high fever”, 2)
what is big O for insertion, deletion, and access for hash table
O(1)! amazing!
DLL.pop
//pop removes the last item and returns it
pop() {
if (this.length === 0) {
return undefined;
}
var storedTail = this.tail;
if (this.length === 1) {
this.head = null;
this.tail = null;
} else {
var newTail = this.tail.prev
this.tail.prev = null;
this.tail = newTail;
this.tail.next = null;
}
this.length--;
return storedTail;
}linked list Node (S or D)
class Node {
constructor(val) {
this.val = val;
this.next = null
}
}when storing a heap as an array, what is the parent of a child?
floor(n-1)/2)
DLL class
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}mergeSort
function mergeSort(array) {
//break up the arrays into halves until you have arrays that are size zero or 1
//once you have smaller sorted arrays, merge those arrays
//once an array has been merged, return the merged array
// Recrusive Merge Sort
if(arr.length \<= 1) return arr; let mid = Math.floor(arr.length/2); let left = mergeSort(arr.slice(0,mid)); let right = mergeSort(arr.slice(mid)); return merge(left, sright);
}
popping a singly linked list
there’s no pointer, so you have to reset the tail by going through the whole thing
DLL.insert
//creates new node and adds it at that position.
insert(index, val) {
//can be optimized for beginning/end, also can use unshift/push
if (index \< 0 || index \>= this.length) {
return undefined;
}
if (index === 0) {
this.unshift(val);
}
if (index === this.length) {
this.push(val);
}
else {
if (index \<= this.length/2) {
var current = this.head
var count = 0;
while (count != index) {
count++;
current = current.next;
}
} else {
//from the tail
var count = this.length - 1;
var current = this.tail
while (count != index) {
count --
current = current.prev;
}
}
addNode(current, val)
}
function addNode(current, val) {
var savedNext = current.next
var newNode = new Node(val)
current.next = newNode;
newNode.next = savedNext;
savedNext.prev= newNode;
newNode.prev = current;
}
this.length++;
return true;
}
big O for searching a heap
O(n) - remember, no implied order between siblings
how do you find shortest distsance in a graph
BFS
what are binary heaps for
they are useful for priority queues and for graph traversal algorithms
graph breadth first traversal code
breadthFirstTraversal(start) {
const queue = [start];
const result = [];
const visited = {};
let currentVertex;
while (queue.length) {
currentVertex = queue.shift();
result.push(currentVertex);
this.adjacencyList[currentVertex].forEach(nieghbor => {
if(!visited[neighbor]) {
visited[neighbor] = true;
queue.push(neighbor);
}
});
}
return;
}
DLL.push
push(val) {
//create new node
var newNode = new Node (val);
//set old tail.next to new node
if (this.length === 0) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next =newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
//set new node.prev to old tail
//change the tail
//increase length
this.length++;
return this;
}what even is a heap
a heap is a special kind of binary tree, where the parent nodes are always either larger or smaller than the children (max and min), and left children are filled first - there is no guarantee of ordering between siblings
how to implement a stack using a linked list
use a doubly linked list so that removal is constant time, or singly linked but remove from the front
queue node and class from scratch
class Node {
constructor(value){
this.value = value;
this.next = null;
}
}
class Queue {
constructor(){
this.first = null;
this.last = null;
this.size = 0;
}
}
recursion - dont forget
has to have a base case
has to return
DLL.shift
//removes a node fom the beginning
shift() {
if (this.length === 0) {
return undefined;
}
var storedHead = this.head;
if (this.length === 1) {
this.head = null;
this.tail = null;
}
this.head = storedHead.next;
this.head.prev = null;
storedHead.next = null;
this.length–;
return storedHead
}
linlked list implementation of a stack class
class Stack {
constructor() {
this.first = null;
this.last = null;
this.size = 0;
}disadvantage of singly linked lists over arays
no random access like you have in an array
when storing a heap as an array, what are the children?
The left child ofa parent is at 2n+1, the right child is 2n+ 2
easy DepthFirst for graphs
