Simple Queue Implementation Guide (Using the Linked List)

Implementing the queue using the linked list as the underlying data structure is much simpler than using arrays as the underlying data structure.

I will assume that you understand the fundamentals of the queue data structure.

In this post, we will be writing the queue using the linked list as the underlying data structure.

This tutorial exists not only to show users how to implement the queue using linked lists but to also demonstrate how important it is to master the fundamentals.

Having a solid grasp on the fundamentals not only gives you a greater arsenal of tools to work with. It also accelerates the speed at which you learn other topics, including more complex data structures.

If you don’t know what a linked list is, I strongly suggest that you come back after learning how the linked list works.

Queue Linked List Overview

If you know how to implement a linked list, then congratulations! You pretty much know how to implement the queue using linked lists. It is now just a matter of customizing the interface so that it behaves like a queue.

As you may already know, the queue has the following methods

  • enqueue() – add an item to the back of the queue.
  • dequeue() – remove the first item from the queue and return its value.
  • front() – return the value of the first item without removing it from the queue.

Because the queue is a FIFO (first in, first out) data structure, we add items to the end of the queue and remove items from the front of the queue.

Enqueue()

As I mentioned before, the queue is a FIFO data structure. Therefore, the queue linked list implementation’s enqueue method adds data to the end of the list. That way, the elements will be removed from the queue in the order that they were inserted.

This involves the following steps.

  1. Create a new node with the data to insert.
  2. Set the next node pointer of the new node to null. Because the tail is the last element in the queue, the next node pointer should point to null.
  3. Set the previous node pointer of the new node to the current tail. The current tail (in the next step) will be pushed down. In other words, it will become the second last element.
  4. Update tail pointer reference to point to the newly created node.

Dequeue()

In the dequeue operation, we will be removing the item at the front of the queue. In other words, the head of the linked list.

  1. Get the next node after the head.
  2. Set it as the new head.
  3. Set the previous pointer of the new head to null.
  4. Remove the previous head.

When working with C++, make sure to use the delete keyword to remove the previous head. Otherwise, this will cause a memory leak in your program, which is something that you never want, under any circumstance.

Front()

As the name suggests, this method simply enables users to retrieve the first element in the queue without actually removing it. The rest of the methods such as size() and isEmpty() is quite self-explanatory.

I want to finish off by stating that giving meaningful names to methods is an important part of writing good code. It is something that we all need to be mindful of, regardless of where we are in our walk as developers.

It is a small part of writing clean, readable code that adds value to your team. Spending the extra time in making your code as easy to extend and modify will pay dividends in the form of reduced time spent updating the code in the future.

Source Code

Assuming that you read through my previous tutorial on the linked list and queue implementation using arrays, this should be a cakewalk.

The queue using linked list is pretty much a linked list with the restriction that users can only interact with the first element in the list and add items to the end of the linked list.

Once again, all the source code can be found on my GitHub profile. The source code is available in the following languages.

Thank you for reading and happy coding!

Queue Interface

public interface Queue<T> {
    /**
     * Insert data into the Queue
     * */
    void enqueue(T data);

    /**
     * Remove and return the element at the front of the queue
     * */
    T dequeue();

    /**
     * Get the size of the Queue
     * */
    int size();

    /**
     * Get data at the front of the Queue
     * @return T data
     * */
    T front();

    /**
     * Check if queue is empty
     * */
    boolean isEmpty();

    /**
     * Print items in the queue
     * */
    void print();
}

 

LinkedListQueue.Java

/**
 * @Author Jay Lee
 * @see https://www.thecodingdelight.com
 * */
public class LinkedListQueue<T> implements Queue<T> {

    private int size;
    private Node<T> head;
    private Node<T> tail;

    @Override
    public void enqueue(T data) {
        if (this.isEmpty()) {
            this.head = new Node<T>(data, null);
        } else {
            // If tail is null, this is the second element
            if (this.tail == null) {
                this.tail = new Node<T>(data, null);
                this.head.setNextNode(this.tail);
            } else {
                // More than two elements present
                // If this is the case, set the current tail
                // to point to the newly inserted node
                // Afterwards, set the newly inserted node as the new tail.
                // We need a tail to make sure insertion to our queue can
                // be done in O(1) constant time.
                Node<T> previousTail = this.tail;
                Node<T> newTail = new Node<T>(data, null);
                previousTail.setNextNode(newTail);
                this.tail = newTail;
            }
        }
        this.size++;
    }

    @Override
    public T dequeue() {
        // Queue is a FIFO data structure.
        // We only provide users with access to interact
        // with the head node.
        // If the list is empty return null and do nothing
        Node<T> nodeToReturn = this.head;
        if (this.isEmpty()) {
            return null;
        } else {
            // Removing the second last element from the list
            if (this.tail == null) {
                this.head = null;
            } else {
                // Set new head to next node, regardless of whether
                // it is a null pointer
                this.head = this.head.getNextNode();
            }
            // Lastly, decrement size of the queue
            this.size--;
        }
        return nodeToReturn.getData();
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public T front() {
        return this.head.getData();
    }

    @Override
    public boolean isEmpty() {
        return this.head == null;
    }

    @Override
    public void print() {
        System.out.println(this.toString());
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("LinkedListQueue: {");
        Node<T> currentNode = this.head;

        while (currentNode != null) {
            sb.append(currentNode.getData());
            currentNode = currentNode.getNextNode();
            if (currentNode != null) {
                sb.append(" --> ");
            }
        }
        sb.append("}");
        return sb.toString();
    }
}

Jay

About the Author Jay

I am a programmer currently living in Seoul, South Korea. I created this blog as an outlet to express what I know / have been learning in text form for retaining knowledge and also to hopefully help the wider community. I am passionate about data structures and algorithms. The back-end and databases is where my heart is at.

follow me on:
6 Shares