Queue Implementation in Java Using Linked List

In this post we’ll see an implementation of Queue in Java using Linked list. Queue can also be implemented using array but that has one drawback; queue size is fixed in that case, which needs some extra work to fill the space created by removing the element from the front.

Refer Queue Implementation in Java Using Array to see how to implement Queue using array in Java.

Queue data structure

A queue is a First In First Out (FIFO) data structure where the first item inserted is the first to be removed. In a queue items are inserted at the rear and removed from the front of the queue.

Following image shows an implementation of Queue as linked list with front and rear references.

Operations in a Queue

Mainly following three operations are implemented for a Queue-

insert- To insert an item at the rear of the queue.
remove- To remove an item from the front of the queue.
peek- Read value from the front of the queue without removing it.

Java program for Queue using linked list

For representing nodes of the linked list a separate class (private class Node in the program) is used which apart from the data also holds a reference to itself.

There are also two references front and rear of type Node which are used to point to the first node of the Linked list (front of the queue) and the last node of the Linked list (rear of the queue).

For insert operation new nodes are inserted at the end of the Linked list and the rear points to the new node.

For remove operation first node in the Linked list is removed and the front starts referencing to the next node.

public class LinkedListQueue {
 Node front;
 Node rear;
 public LinkedListQueue(){
  front = null;
  rear = null;
 }
 // Class for node
 private class Node{
  //data
  int i;
  Node next;
  Node(int i){
   this.i = i;
  }
  public void displayData(){
   System.out.println("i= " + i);
  }
 }
 /** Linked list operations, keeping them separate from 
  * Queue operations
  * */
 public void insertLast(int i){
  Node newNode = new Node(i);
  if(isEmpty()){
   front = newNode;
  }else{
   // previous last point to new node
   rear.next = newNode;
  }
  rear = newNode;
 }
 
 public int removeFirst(){  

  int temp = front.i;
  // If no node left after deleting node
  if(front.next == null){
   rear = null;
  }
  // front starts pointing to next element
  front = front.next;
  return temp;
 }
 
 // Method to traverse and display all nodes
 public void displayList(){
  // Start from first node
  Node current = front;
  // loop till last node
  while(current != null){
   current.displayData();
   current = current.next;
  }
 }
 
 public int nodeData(){
  return front.i;
 }
 
 public boolean isEmpty(){
  return front == null;
 }
 /** Queue operations */
 public void insert(int item){
  insertLast(item);
 }
 
 public int remove(){
  if(isEmpty()){
   throw new RuntimeException("Queue is empty..");
  }
  return removeFirst();
 }
 
 public int peek(){
  if(isEmpty()){
   throw new RuntimeException("Queue is empty..");
  }
  return nodeData();
 }
 
 public static void main(String[] args) {
  LinkedListQueue queue = new LinkedListQueue();
  queue.insert(3);
  queue.insert(6);
  System.out.println("-- Displaying Queue data--");
  queue.displayList();
  System.out.println("Item peeked- " + queue.peek());
  System.out.println("-- Removing Queue elements--");
  System.out.println("Item removed- " + queue.remove());
  System.out.println("Item removed- " + queue.remove());
 }
}

Output

-- Displaying Queue data--
i= 3
i= 6
Item peeked- 3
-- Removing Queue elements--
Item removed- 3
Item removed- 6

That's all for this topic Queue Implementation in Java Using Linked List. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Tech Tutorials

Wednesday, March 30, 2022