Design a Queue in Java Using Linkedlist

Linked list-based implementation of queue

A Queue is an abstract data structure which follows the First In First Out FIFO principle. It means the element which came into the queue first will leave the queue first. This ordering is very helpful in a lot of solutions. Two things are important for a queue: front and rear or tail.

A new element is added into the queue at the rear or at the tail, which is called enqueue operation.

enqueue operation on linked list based queue

The front is the point from where an element of a queue is taken out. This operation is called dequeue operation.

Dequeue operation on queue implemented using linked list

Interface for a queue would be as shown below. This interface can be implemented in multiple ways. There are different ways in which an abstract data structure can be implemented using concrete data structures, for example, a queue can be implemented using arrays or linked lists. Limitation in array-based implementation is that we have to allocate array size beforehand which restricts the number of elements that can be accommodated. Another issue is to correctly tell if the queue is empty or full. We have to maintain an extra counter for that purpose.

package com.company;  /**  * Created by sangar on 8.10.18.  */ public interface Queue<E> {     public ListNode<E> peek();     public ListNode<E> remove();     public ListNode<E> enqueue(E data);     public boolean isEmpty();     public int size(); }        

Let's discuss how to implement a queue using linked lists.

Single linked list based implementation of queue

A linked list a collection of nodes where each node has two components, first component store the data for the node and second component points to the next node in the linked list. In the last node, the second component points to NULL, which signifies the end of the linked list.

singly linked list based implementation of queue

If we use a linked list, we solve the first problem of statically allocating memory beforehand for the queue. The linked list is a dynamic data structure, we can allocate memory at the runtime based on our requirements. Also, to find if a queue is empty, check if linked list empty, which is a simple operation to check if the head of linked list NULL.

The time complexity to remove an element out to the singly linked list based queue is O(1), remove the head and make the next node of the head new head. However, to add an element into the singly linked list, we have to go the end of the lists which has a time complexity of O(n).

This problem can be easily be solved by keeping a tail pointer, which points to the last node of the linked list. When we have to enqueue an element in the queue, we update the next of tail to point to the new node and make new node has the tail of the queue. The complexity of enqueue operation is also O(1).

The singly linked list seems to be working for the queue implementation, with dynamic size, dequeue and enqueue operation with O(1) complexity.

One more operation performed on queues to solve certain problems like LRU Cache, non repeated characters in a stream etc. This operation is to delete a random node in queue. Given a random node in the queue, remove that node from the queue.

This problem is tricky in a singly linked list. Brute force solution is to traverse the linked list, go till the previous node and the do the pointer rearrangement and then free the memory of the given node. This operation in the worst case requires O(n) operations. There is a trick method, which is to copy the data of the next node of the given node to the given node and then delete the next node. Caveat to this trick, which I have discussed in delete a node from linked list.

To delete a node from a linked list, two pointers are required: the previous node of the node and the next node of the node. All we do is to make the next pointer of the previous node point to the next node of the given node and free the given node.

Doubly linked list based implementation of queues

From the above discussion, it is easy to guess which type of linked list implementation will give us previous and next node of a given node without traversing the list. It is doubly linked list.

doubly linked list based implementation of queues

All the operations remain the same, with same time complexity. With the doubly linked list, delete operation also becomes O(1). So, whenever you have a use case where you may have to delete a random node from the queue, always go for the doubly linked list based implementation. The only overhead is that we have to store double the number of pointers than a singly linked list.

package com.company;  /**  * Created by sangar on 8.10.18.  */ public interface Queue<E> {     public ListNode<E> peek();     public ListNode<E> remove();     public ListNode<E> enqueue(E data);     public ListNode<E> deleteNode(ListNode<E> node);     public boolean isEmpty();     public int size(); }        

package com.company;  /**  * Created by sangar on 8.10.18.  */ public class QueueImplementation<E> implements Queue<E>{     ListNode<E> head;     ListNode<E> tail;     int size;      public QueueImplementation(){         head = null;         tail = null;         this.size = 0;     }      @Override     public ListNode<E> deleteNode(ListNode<E> node){         if(this.isEmpty()) {             return null;         }          if(this.head == node){             if(this.head.getNext() != null)                  this.head.getNext().setPrev(null);             this.head = this.head.getNext();             this.size--;             return node;         }          if(this.tail == node){             if(this.tail.getPrev() != null)                 this.tail.getPrev().setNext(null);             this.tail = this.tail.getPrev();             this.size--;             return node;         }         /*             We are deleting node in between. So following things happen             1. If node has prev, set node.prev.next = node.next.             2. If node has next, set node.next.prev = node.prev         */         if(node.getPrev() != null) node.getPrev().setNext(node.getNext());         if(node.getNext() != null) node.getNext().setPrev(node.getPrev());          this.size--;         return node;     }       @Override     public ListNode peek() {         if(this.isEmpty()) {             return null;         }         return this.head;     }      @Override     public ListNode remove() {         if(this.isEmpty()) {             return null;         }         /*             We are deleting node at head. So following things happen             1. Set temporary node point to head.             2. Move head to next of node.             3. Set prev of new head to NULL.             4. Free the temp node.           */         ListNode<E> tempNode = this.head;         this.head.setPrev(null);         this.head = this.head.getNext();          this.size--;         return tempNode;     }      @Override     public ListNode enqueue(E data) {         if(this.isEmpty()) {             this.head = new ListNode<E>(data);             this.tail = this.head;             this.size++;             return this.head;         }         ListNode<E> newNode = new ListNode<E>(data,null, this.tail);         this.tail.setNext(newNode);         this.tail = newNode;          this.size++;         return newNode;     }      @Override     public boolean isEmpty() {         return this.head == null;     }      @Override     public int size() {         return this.size;     } }        

Circular linked list base implementation of queue

Sometimes, the interviewer asks to you solve a trick question like this: Implement queue using only one pointer, either front or rear

The correct answer to it is to use a circular linked list, where the last pointer points back to the head or front pointer. In that case, we will use only the rear pointer.

Enqueue operation:
We create a new node, point the next of new node to the next of tail node, make it next of the tail node and new node becomes the tail node. This whole operation is in constant time, hence the complexity of this operation is O(1).

implementation of queue using only one pointer

          newNode.next=tail.next;     tail.next=newNode;    tail=newNode;        

Dequeue operation:

          node = tail.next //node to be removed    tail.next =  node.next // point to the next of front node.        

We learned different ways to implement a queue using linked lists. Based on the requirements and constraints of the problem we choose one of the give implementations. To understand more how queues are implemented in Java, please read Queue Implementations

Please share if there is something wrong or missing. If you are preparing for an interview and need personalized coaching to help you with preparation, please book a free session with us.

Design a Queue in Java Using Linkedlist

Source: https://www.algorithmsandme.com/queues-linked-list-based-implementation/

Share this post