Prerequisite:
If you have not covered the following topics, please study below topics before starting this tutorial.
Linked list and Queue:
Queue works on the concept of FIFO(First In First Out). It means the item which is added at first to the Queue is processed first. It means item addition(ENQUEUE operation) will be at tail/rear/back end of the linked list and item processing(DEQUEUE operation) takes place at the head/front end.
In Linked list item can be added to any place using the head pointer which points to the first item in the linked list.
By combining both the definitions we conclude that enQueue operation will be at the head pointer end in the linked list and deQueue operation will be at the end position of the linked list. In this case the head pointer in the linked list will behave like the front/head pointer of the Queue.
Strategy section will explain how to implement the Queue using linked list.
Strategy
As mentioned above we will use head pointer of the linked list as the front/head pointer of the Queue.
And for the back/tail/rear pointer of the queue we are not going to use any variable. Null pointer of the last inserted node will be utilized as back/tail/rear pointer for the Queue operation.
Below are the details of implementation of Queue using linked list.
1. LinkedListNode - This class will only define structure of linked list node.
2. QueueUsingLinkedList - This class will implement all necessary logic to operate Queue using Linked ListNode as storage unit. Below are the basic operations/variables to implement the Queue.
a. head pointer - This is the variable which always points to the first node of the linked list.
b. enQueue(item)-This operation adds a element to the end of the linked list.
c. deQueue()-This operation fetches and removes an item from the linked list pointed by head pointer.
d. peek()-This operation fetches an item from the linked list pointed by head pointer.
d. getSize()-This operation will return the number of elements in the linked list.
e. size - This variable will be used to track size of the Queue.
f. printLinkedList() - This is the optional method to see the content of the Queue.
Below is the class diagram for the implementation of the Queue using linked list mentioned above:
Here we are going to write algorithms for all the operations of the linked list mentioned in the above diagram.
enQueue( item )- This operation adds an element at the end position in the linked list. To add an element at the end of the linked list, one has to traverse from front end to back end. So time complexity of enQueue() operation is O(n).
Below is the implementation of enQueue(item) operation.
enQueue(item)
{
1. tempHead=head
2. newNode=new LinkedListNode(item)
3. while(tempHead!=null && tempHead.next!=null)
4. tempHead=temHead.next
5. if(tempHead=null)
6. head=newNode
7. else
8. tempHead.next=newNode
9. size++
}
Below is the the implementation of deQueue() operation.
deQueue():item
{
1. if head == null
2. Error("No item present to be popped");
3. item=head.data
4. head=head.next
5. size--
6. return item
}
peek( )- This operation fetches the first added element from the linked list pointed by the head pointer. Since head pointer is known and accessed in O(1) time, the time complexity of this operation is O(1).
Below is the the implementation of peek() operation.
peek():item
{
1. if head == null
2. Error("No item present to be popped");
3. item=head.data
4. return item
}
getSize() = This operation returns the size of linked list using size variable. Below is the implementation of getSize() operation.
getSize():Integer
{
return size;
}
printLinkedList()- This operation prints all the elements of the linked list by traversing the linked list using head pointer. Since entire linked list is traversed here, time complexity of this operation is O(n)
printLinkedList()
{
1. if head == null
2. Error("No item present in the linked List");
3. tempHead=head
4. while(tempHead!=null)
5. print(tempHead.data)
6. tempHead=temHead.next
}
Below is the java code implementation of the above discussed algorithms
public class QueueLinkedListTest {
/**
* @param args
* @throws Exception
*/
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
QueueUsingLinkedList<Integer> linkedList=new QueueUsingLinkedList<Integer>();
linkedList.enQueue(1);
linkedList.enQueue(2);
linkedList.enQueue(5);
linkedList.enQueue(6);
linkedList.enQueue(11);
linkedList.printLinkedList();
System.out.println("Size of the Queue is: "+linkedList.getSize());
System.out.println("Peek item is: "+linkedList.peek());
System.out.println("Dequeued item is: "+linkedList.deQueue());
System.out.println("Dequeued item is: "+linkedList.deQueue());
System.out.println("QueueUsingLinkedList after deleting two elements");
linkedList.printLinkedList();
System.out.println("Peek item is: "+linkedList.peek());
System.out.println("Size of the Queue is: "+linkedList.getSize());
}
}
class LinkedListNode<T>
{
public T data;
public LinkedListNode next;
public LinkedListNode(T item)
{
data=item;
next=null;
}
}
class QueueUsingLinkedList<T>
{
private LinkedListNode head;
private int size=0;
public void enQueue(T item)
{
LinkedListNode newNode=new LinkedListNode(item);
LinkedListNode tempHead=head;
while(tempHead!=null&&tempHead.next!=null)
{
tempHead=tempHead.next;
}
if(tempHead==null)
{
head=newNode;
}
else
{
tempHead.next=newNode;
}
size++;
}
public T deQueue() throws Exception
{
if(head==null)
{
throw new Exception("Linked List is empty");
}
T item=(T) head.data;
head=head.next;
size--;
return item;
}
public T peek() throws Exception
{
if(head==null)
{
throw new Exception("Linked List is empty");
}
T item=(T) head.data;
return item;
}
public int getSize()
{
return size;
}
public void printLinkedList() throws Exception
{
if(head==null)
{
throw new Exception("Linked List is empty");
}
LinkedListNode tempHead=head;
System.out.println("============QueueUsingLinkedList printing - starts===========");
while(tempHead!=null)
{
System.out.print(tempHead.data+"\t");
tempHead=tempHead.next;
}
System.out.println("");
System.out.println("============QueueUsingLinkedList printing - ends===========");
}
}
