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.