Queue using Double-Ended Linked List: Example

Stacks and Queues are ADTs (Abstract Data Types). In our previous article we have seen how to implement Stack using Linked List. In this this article you will learn how to implement Queue using Double-Ended Linked List.

What is ADT ?

ADT (Abstract Data Types) in data structures terminology we can say it is a way of looking at a data structure, focusing on what the data structure does instead of how it does. Stacks and Queues are examples of ADTs.

Queue using Double-Ended Linked List: Example

package com.sneppets.dsalgo;

/**
 * Link
 * 
 */
class Link
{
	//data
	public int intData;
	//next link in the list
	public Link next;
	//constructor
	public Link(int iData)
	{
		intData = iData;
	}
	//display link
	public void displayLink()
	{
		System.out.print(intData + " ");
	}
}

class DoubleEndedLinkedList
{
	//reference to first link
	private Link first;
	
	//reference to last link
	private Link last;
	
	public DoubleEndedLinkedList()
	{
		//no links yet
		first = null;		
		last = null;
	}
	
	//return true if there are no links
	public boolean isEmpty()
	{
		return (first == null);
	}

	//insert at last
	public void insertLast(int iData)
	{	
		//create a new link
		Link newLink = new Link(iData);
		if(isEmpty())
		{
			//if list is empty first --> newLink
			first = newLink;
		}
		else
		{
			//old last --> newLink
			last.next = newLink;
		}
		//insert new link at last
		last = newLink;
	}
	
	//delete first link
	public int deleteFirst()
	{
		//save reference to link data
		int temp = first.intData;
		//check if only one item is there in the list
		if(first.next == null)
		{
			last = null;
		}
		//delete first --> old next
		first = first.next;
		return temp;
	}
	
	public void displayList()
	{
		//start from beginning of the list
		Link current = first;
		//until end of list is reached
		while (current != null)
		{
			//print link details
			current.displayLink();
			//move to next link
			current = current.next;
		}
		System.out.println(" ");
	}
	
}

class LinkedListQueue
{
	private DoubleEndedLinkedList delList;
	
	public LinkedListQueue()
	{
		//create a double-ended list
		delList = new DoubleEndedLinkedList();
	}
	
	//return true if queue is empty
	public boolean isEmpty()
	{
		return (delList.isEmpty());
	}
	
	//insert at the rear of queue
	public void insert(int iData)
	{
		delList.insertLast(iData);
	}
	
	//remove from front of the queue
	public int remove()
	{
		System.out.println("Deleting an item from front of the queue..");
		return delList.deleteFirst();
	}
	
	//display queue
	public void displayDoubleEndedLinkedListQueue()
	{
		System.out.println("double-ended-list-queue from first to last :");
		delList.displayList();
	}
	
}

/**
 * 
 * @author sneppets.com
 *
 */
public class DoubleEndedLinkedListQueueExample {
	
	public static void main (String[] args)
	{
		//create queue
		LinkedListQueue llQueue = new LinkedListQueue();
		//insert
		llQueue.insert(10);
		llQueue.insert(20);
		llQueue.insert(30);
		//display queue
		llQueue.displayDoubleEndedLinkedListQueue();
		//insert
		llQueue.insert(40);
		//display queue
		llQueue.displayDoubleEndedLinkedListQueue();
		//remove
		llQueue.remove();
		llQueue.remove();
		//display queue
		llQueue.displayDoubleEndedLinkedListQueue();
		
	}

}

Output

double-ended-list-queue from first to last :
10 20 30  
double-ended-list-queue from first to last :
10 20 30 40  
Deleting an item from front of the queue..
Deleting an item from front of the queue..
double-ended-list-queue from first to last :
30 40  

Recommended Posts

• Simple Linked List Example
• Implement Stack using Linked List
• Array Vs Linked List Efficiency
• Double-Ended Lists Example
• Find and delete specified ‘Link’ from Linked List
• Priority Queue: Array Based Example
• Deque: Double-ended queue is a versatile data structure
• Queue No-count approach and Implementation
• Circular Queue using Array (Wrapping Around)
• Reverse a string or word using Stack
• Delimiter Matching using Stack

References

• Oracle API Documentation