loading...
Cover image for Writing a queue in JS (using a Linked List)

Writing a queue in JS (using a Linked List)

petrussola profile image Pere Sola ・2 min read

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

Posted on by:

petrussola profile

Pere Sola

@petrussola

Account Manager @Stripe. Full stack software developer in my spare time. @LambdaSchool graduate

Discussion

pic
Editor guide
 

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.