Implement Queue in Java Using Linked List

Linked List Implementation of Queue in Java
References

Linked List Implementation of Queue in Java

Here, we implement a generic queue in Java using linked list. A queue is a container to which items are added and removed by following first-in-first-out strategy; therefore, an item added to the container first will be removed first. A queue usually has two ends, one for adding items and another for removing them, these ends are pointed by two pointers called front and rear. The front pointer points to the end where items are removed from, while the rear points to the end where items are added to the queue. In linked implementation of queue we will keep front and rear pointing at beginning and end of the queue.

A queue by definition supports two methods, one is enqueue (also called insert) for adding objects to the queue, and second, dequeue (also called delete) for removing an item from the queue. The following methods we plan to implement as part of our linked list implementation of queue in Java.

insert(): Adds an item to the queue

delete(): Remove an item from queue.

size(): Return the number of items the queue contains right now.

isEmpty(): Returns true if queue is empty, false otherwise.

Queue Interface

In order to make end user independent from implementation details of the queue implementation whether it is implemented using linked list or array, we define an interface Queue as follows. The following Queue interface can be assigned any object that implements this interface no matter the underlying implementation uses linked list or array based implementation of queue in Java. Create a text file Queue.java, insert the following code in that and save it.

/* Queue.java */
 
public interface Queue <Item>
{
  Item delete(); // removes an item from the front of the queue
  void insert(Item item); // adds an item to the rear end of the queue
  boolean isEmpty(); // returns true if queue is empty, false otherwise
  int size();  // returns the number of items in the queue right now
}

If you look at the above definition of Queue interface, you will see that the interface is passed a parameter Item enclosed in angular brackets. This feature facilitates the generic use of Queue data structure. It allows programmers to pass the object type the queue will store at run time. A special feature of Java called generics brings us this capability.

LinkedQueue Class Implementing Queue

Now create a file LinkedQueue.java and insert the following code for class LinkedQueue that implements Queue interface as follows:

/* LinkedQueue.java */
class LinkedQueue <Item> implements Queue <Item>
{
  private Node front, rear; //begin and end nodes
  private int size; // number of items
 
  //nested class to define node
  private class Node
  { 
    Item item;
    Node next;
  }
 
  //Zero argument constructor
  public LinkedQueue()
  {
    front = null;
	rear = null;
    size = 0;
  }
 
  public boolean isEmpty()
  {
    return (size == 0);
  }
 
  //Remove item from the beginning of the list.
  public Item delete()
  {
    Item item = front.item;
    front = front.next;
    if (isEmpty()) 
    {
      rear = null;
    }
    size--;
    return item;
  }
 
  //Add item to the end of the list.
  public void insert(Item item)
  {
    Node oldRear = rear;
    rear = new Node();
    rear.item = item;
    rear.next = null;
    if (isEmpty()) 
    {
      front = rear;
    }
    else 
    {
      oldRear.next = rear;
    }
    size++;
  }
 
  public int size()
  {
    return size;
  }
}

The above implementation of LinkedQueue class takes a type parameter Item which would be replaced with concrete type by the client code when the LinkedQueue object will be created as follows, for an example:

Queue <Integer> q = new LinkedQueue <Integer>();

The above code completes the queue implementation using linked list but we definitely will be further interested in implementing an iterator for the newly created LinkedQueue type, so that we can iterate through the items currently stored in the data structure. Following section implements an iterator for LinkedQueue class and a driver to run LinkedQueue class code.

Iterating through Queue Items - Queue Iterator

By definition of queue data structure you would use it as a container where items are added to one end and removed from another end. But, if you like to make the Queue a usual collection where you can iterate through the queue items, you should implement Iterable and Iterator interfaces as part of your LinkedQueue implementation.

Java provides a special syntax of for loop (also called for-each loop) to process arrays and iterable collections. Any iterable collection has to implement an iterator() method that returns an Iterator object. And the class implements Iterator has to implement two methods: hasNext() (returns true if there are more items to process, false otherwise) and next() (returns an item from the collection).

To make our Queue data structure iterable, we first extends the Queue<Item> interface by Iterable<Item>. Interface Iterable is already defined as part of java.lang.Iterable. As soon as we extend Queue<Item> interface by Iterable<Item> we have to add a new method iterator() to class LinkedQueue that will return an object of type Iterator<Item>

Generally, an iterator is an object of a class that implements hasNext(), and next() as they are declared in Iterator interface. The Iterator interface also declares a remove() method but we will not specify anything in its body.

The interface Iterator<Item> we will implement by an inner class LinkedQueueIterator to LinkedQueue. To complete the code first modify the existing signature of interface Queue in Queue.java as follows, no change required in interface's body.

public interface Queue <Item> extends Iterable <Item>

Thereafter modifying Queue interface, we need to modify LinkedQueue class as follows:

/* LinkedQueue.java */
import java.lang.Iterable;
import java.util.*;
 
class LinkedQueue <Item> implements Queue <Item>
{
  private Node front, rear; //begin and end nodes
  private int size; // number of items
 
  //nested class to define node
  private class Node
  { 
    Item item;
    Node next;
  }
 
  //Zero argument constructor
  public LinkedQueue()
  {
    front = null;
	rear = null;
    size = 0;
  }
 
  public boolean isEmpty()
  {
    return (size == 0);
  }
 
  //Remove item from the beginning of the list.
  public Item delete()
  {
    Item item = front.item;
    front = front.next;
    if (isEmpty()) 
    {
      rear = null;
    }
    size--;
    return item;
  }
 
  //Add item to the end of the list.
  public void insert(Item item)
  {
    Node oldRear = rear;
    rear = new Node();
    rear.item = item;
    rear.next = null;
    if (isEmpty()) 
    {
      front = rear;
    }
    else 
    {
      oldRear.next = rear;
    }
    size++;
  }
 
  public int size()
  {
    return size;
  }
 
  //Iterator for traversing queue items
  public Iterator<Item> iterator()
  {
    return new LinkedQueueIterator();
  }
 
  //inner class to implement iterator interface
  private class LinkedQueueIterator implements Iterator <Item>
  {
    private int i = size;
    private Node first = front; //the first node
 
    public boolean hasNext()
    {
      return (i > 0);
    }
 
    public Item next()
    {
      Item item = first.item;
      first = first.next;
      i--;
      return item;
    }
 
    public void remove()
    {
      // not needed
    }
  }
}

To test the above implementation, define a driver class as follows:

/* LinkedQueueDemo.java */
 
public class LinkedQueueDemo
{
  public static void main (String a[])
  {
    Queue <Integer> q = new LinkedQueue<Integer>();
    q.insert(20);
    q.insert(30);
    q.insert(40);
    q.insert(50);
    q.insert(60);
    q.insert(70);
 
    System.out.println("Delete an item from queue: " + q.delete());    
    System.out.println("Size of the queue: " + q.size());
 
    // iterate through queue
    System.out.println("Queue contains following items till this moment:");
    for (Integer i : q)
      System.out.println(i);  
  }
}
 
OUTPUT
======
D:\JavaPrograms>javac LinkedQueueDemo.java
 
D:\JavaPrograms>java LinkedQueueDemo
Delete an item from queue: 20
Size of the queue: 5
Queue contains following items till this moment:
30
40
50
60
70

If you observe the output generated by LinkedQueueDemo class, you will find that queue items are processed in first-in-first-out fashion.

Last Word

In this tutorial we talked of implementation of queue in Java using linked list. We implemented generic queue in Java using linked list to create a queue of any user defined type. In linked list implementation of queue memory is used efficiently and no resize operations are required as they are required in array implementation of queue. Hope you have enjoyed reading this tutorial. Please do write us if you have any suggestion/comment or come across any error on this page. Thanks for reading!

References

Share this page on WhatsApp