Skip to content

Instantly share code, notes, and snippets.

@burdiuz
Last active November 28, 2021 07:23
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 burdiuz/98eaa06e18fc2c949cae5abf6a5ccef1 to your computer and use it in GitHub Desktop.
Save burdiuz/98eaa06e18fc2c949cae5abf6a5ccef1 to your computer and use it in GitHub Desktop.
Simple Queue implementation via bi-directional linked list
class QueueNode {
constructor(value, prev = null, next = null) {
this.value = value;
this.insert(prev, next);
}
insert(prev, next) {
this.prev = prev;
this.next = next;
if (next) {
next.prev = this;
}
if (prev) {
prev.next = this;
}
}
remove() {
if (this.next) {
this.next.prev = this.prev;
}
if (this.prev) {
this.prev.next = this.next;
}
}
}
const createQueueNode = (value, prev = null, next = null) =>
new QueueNode(value, prev, next);
class Queue {
constuctor() {
this.head = createQueueNode();
this.tail = createQueueNode(null, this.head);
}
enqueue(value) {
return createQueueNode(value, this.head, this.head.next);
}
enqueueNode(node) {
node.remove();
node.insert(this.head.next, this.head);
}
empty() {
return this.head.next === this.tail;
}
dequeue() {
const node = this.tail.prev;
if (node === this.head) {
return null;
}
node.remove();
return node.value;
}
forEach(callback) {
let index = 0;
let node = this.head.next;
while (node !== this.tail) {
callback(node.value, index, this);
node = node.next;
index++;
}
}
getHead() {
// if queue is empty, it will return tail value -- null
return this.head.next.value;
}
getTail() {
// if queue is empty, it will return head value -- null
return this.tail.prev.value;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment