I recently wrote a post on how to build a Queue using an Array. I love when people comment to my posts, because I always learn things. Someone said that in order to make dequeuing O(1), I could use a Linked List. Thanks for your input, I thought it would be fun to do so and write here about it. As usual, if something is wrong or I say nonsese, let me know!
First we implement the Linked List:
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
// add node to the linked list
add(element) {
// creates node
const newNode = new Node(element);
// if list is empty, set node to be the head
if (this.size === 0) {
this.head = newNode;
} else {
// otherwise, loop until we find last node, and we set next to be the new node
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
// increase size
this.size++;
}
// remove node that contains a certain elements
removeElement(element) {
// set current to head
let current = this.head;
// if current.data === element, set next as head and return
if (current.data === element) {
this.head = current.next;
console.log(`${element} removed`);
this.size--;
return;
// otherwise
} else {
// loop the linked list until the end (while current.next is not null)
while (current.next) {
// if we find a node with the data we are looking for
if (current.next.data === element) {
// if it is, set the next node of current as the next of the one we want to remove (current.next.next)
current.next = current.next.next;
console.log(`${element} removed`);
// decrease size of the linked list
this.size--;
return;
} else {
// otherwise, set current to be current.next so we can continue the loop
current = current.next;
}
}
// print "not found" and return
console.log(`${element} not found`);
return;
}
}
removeHead() {
// store head's next in a temp variable
const temp = this.head.next;
// we set the tem as head, so the old head is gone
this.head = temp;
// reduce size as the LL is one element less
this.size--;
}
// Helper Methods
// isEmpty
isEmpty() {
return this.size === 0;
}
// size_Of_List
getSize() {
return this.size;
}
// PrintList
print() {
// set current node
let current = this.head;
// iterate over ll
while (current) {
// console.log every node's data
console.log(current.data);
// set next node to be the current
current = current.next;
}
console.log('-------------');
}
}
module.exports = { Node, LinkedList };
We export it so we can build the Queu in anothed file
Top comments (1)
I would recommend adding a tail as well. That way you donβt need loop to add. Right now, add is O(n). With tail, it will be O(1). Hope this helps.