Queue Implementation using Linked List in Java

---

< Previous Next >

DS and Algorithms in Java

---

In this article, we will discuss the implementation of Queue using Linked List. In the previous article, we have seen the array implementation which can not be used for the large-scale applications where the queues are implemented. One of the alternatives of array implementation is linked list implementation of a queue.

The EnQueue operation is implemented by inserting an element at the end of the list. The DeQueue operation is implemented by deleting an element from the beginning of the list.

In a linked queue, each node of the queue consists of two parts i.e. data part and the link part. Each element of the queue points to its immediate next element in the memory.

In the linked queue, there are two pointers maintained in the memory i.e. front pointer and rear pointer. The front pointer contains the address of the starting element of the queue while the rear pointer contains the address of the last element of the queue.

Insertion and deletions are performed at the rear and front end respectively. If the front and rear both are NULL, it indicates that the queue is empty.

The linked representation of the queue is shown in the following figure.

Queue Implementation using Linked List

Let's first create a Linked List node:

/**
 * Class demonstrates the declaration for a linked list.
 * @author Ramesh Fadatare
 *
 */
public class ListNode{
    public ListNode next;
    public int data;

    // Creates an empty node.
    public ListNode(){
         next = null;
         data = Integer.MIN_VALUE;
    }

    // Creates a node storing the specified data.
    public ListNode (int data){
        next = null;
        this.data = data;
    }

    // Returns the node that follows this one.
    public ListNode getNext(){
         return next;
    }

    // Sets the node that follows this one.
    public void setNext (ListNode node){
         next = node;
    }

    // Returns the data stored in this node.
    public int getData(){
          return data;
    }

    // Sets the data stored in this node.
    public void setdata (int elem){
         data = elem;
    }
 
    // Sets the data stored in this node.
    public String toString (){
        return Integer.toString(data);
    } 
}

This program demonstrates the Queue Implementation using Linked List.

/**
 * Queue Implementation using Linked List
 * @author Ramesh Fadatare
 *
 */
public class LinkedQueue{
    private int length;
    private ListNode front, rear;
 
    //  Creates an empty queue.
    public LinkedQueue(){
         length = 0;
         front = rear = null;
    }

    //  Adds the specified data to the rear of the queue.
    public void enQueue (int data){
         ListNode node = new ListNode(data);
         if (isEmpty())
              front = node;
         else
              rear.setNext (node);
         rear = node;
         length++;
    }

    //  Removes the data at the front of the queue and returns a
    //  reference to it. Throws an Exception if the
    //  queue is empty.

    public int deQueue() throws Exception{
        if (isEmpty())
              throw new Exception ("queue");
        int result = front.getData();
        front = front.getNext();
        length--;
        if (isEmpty())
             rear = null;
        return result;
    }

    //  Returns a reference to the data at the front of the queue.
    //  The data is not removed from the queue.  Throws an
    //  Exception if the queue is empty.  
    public int first() throws Exception{
        if (isEmpty())
            throw new Exception(); 

        return front.getData();
    }

    //  Returns true if this queue is empty and false otherwise. 
    public boolean isEmpty(){
         return (length == 0);
    }

    //  Returns the number of elements in this queue.
    public int size(){
        return length;
    }

    //  Returns a string representation of this queue. 
    public String toString(){
        String result = "";
        ListNode current = front;
        while (current != null){
            result = result + current.toString() + "\n";
            current = current.getNext();
        }
        return result;
    }
 
    public static void main(String[] args) throws Exception {
        LinkedQueue arrayQueue = new LinkedQueue();
        arrayQueue.enQueue(10);
        arrayQueue.enQueue(20);
        arrayQueue.enQueue(30);
        arrayQueue.enQueue(40);
        arrayQueue.enQueue(50);
        arrayQueue.enQueue(60);
        arrayQueue.enQueue(70);
        arrayQueue.enQueue(80);
        arrayQueue.enQueue(90);
        arrayQueue.deQueue();
        System.out.println(arrayQueue.toString());
    }
}

Output:

20
30
40
50
60
70
80
90

Performance

Let n be the number of elements in the queue, then

• Space Complexity (for n enQueue operations) O(n)
• Time Complexity of enQueue() O(1) (Average)
• Time Complexity of deQueue() O(1)
• Time Complexity of isEmpty() O(1)
• Time Complexity of deleteQueue() O(1)

---

< Previous Next >

DS and Algorithms in Java

---