DEV Community

Cover image for Writing a queue in JS (using a Linked List)
Pere Sola
Pere Sola

Posted on

1

Writing a queue in JS (using a Linked List)

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 };
Enter fullscreen mode Exit fullscreen mode

We export it so we can build the Queu in anothed file

Speedy emails, satisfied customers

Postmark Image

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

Top comments (1)

Collapse
 
scarvps profile image
ScaRvps

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.

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs