Skip to content

Instantly share code, notes, and snippets.

@shchegol
Last active March 6, 2021 19:42
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save shchegol/3a51a5ad553b958371c4d6af432c7486 to your computer and use it in GitHub Desktop.
Save shchegol/3a51a5ad553b958371c4d6af432c7486 to your computer and use it in GitHub Desktop.
Stack
Queue
Singly linked list
https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures
class Queue {
constructor() {
this.oldestIndex = 1;
this.newestIndex = 1;
this.storage = {};
}
size() {
return this.newestIndex - this.oldestIndex;
}
enqueue(data) {
this.storage[this.newestIndex] = data;
this.newestIndex++;
}
dequeue() {
let deletedData;
if (this.oldestIndex !== this.newestIndex) {
deletedData = this.storage[this.oldestIndex];
delete this.storage[this.oldestIndex];
this.oldestIndex++;
return deletedData;
}
}
}
class SinglyList {
constructor() {
this.lenght = 0;
this.head = null;
this.errorMessage = {failure: 'Failure: non-existent node in this list.'};
}
add(value) {
let node = {
data: value,
next: null
}
let currentNode = this.head;
if(!currentNode) {
this.head = node;
this.lenght++;
return node;
}
// find last node
while (currentNode.next) {
currentNode = currentNode.next;
}
currentNode.next = node;
this.lenght++;
return node;
}
findNodeAt(position) {
let currentNode = this.head;
let count = 1;
if (this.lenght === 0 || position < 0 || position > this.lenght) {
throw new Error(this.errorMessage.failure);
}
while(count < position) {
currentNode = currentNode.next;
count++;
}
return currentNode;
}
remove(position) {
let currentNode = this.head;
let count = 0;
let beforeNodeToDelete = null;
let nodeToDelete = null;
let deletedNode = null;
if (position < 0 || position > this.lenght) {
throw new Error(this.errorMessage.falure);
}
// first node deleted
if (position === 1) {
this.head = currentNode.next;
deletedNode = currentNode;
currentNode = null;
this.lenght--;
return deletedNode;
}
// other nodes deleted
while(count < position) {
beforeNodeToDelete = currentNode;
nodeToDelete = currentNode.next;
currentNode = currentNode.next;
count++;
}
beforeNodeToDelete.next = nodeToDelete.next;
deletedNode = nodeToDelete;
nodeToDelete = null;
this.lenght--;
return deletedNode;
}
}
class Stack {
constructor() {
this.size = 0;
this.storage = {};
}
push(data) {
++this.size;
this.storage[this.size] = data;
}
pop() {
let deletedData;
if (this.size) {
deletedData = this.storage[this.size];
delete this.storage[this.size];
this.size--;
return deletedData;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment