Linked Lists: Double-Ended Lists Example

Double-ended lists is similar to ordinary linked list, but it has one additional feature compared to ordinary linked list. It provides a reference to the last link as well as to the first link.

Supported Operations:

• insertFirst() – inserting link at front of the linked list
• insertLast() – inserting link at rear of the linked list
• deleteFirst() – deleting link at front of the linked list
• displayList() – display items in the linked list

Advantage of last link:

The reference to the last link enables you to insert link directly at the end of the list as well as the beginning. You can also insert link at the end of single-ended list by iterating through the entire list until you reach the end, but this approach is not efficient.

Note: Don’t confuse the double-ended list with doubly linked list

Application of Double-Ended Linked List

In Double-ended linked list you have access to the end of the list as well as beginning of the list. In situation like while implementing queue double-ended list would be useful in handling certain situations efficiently.

Double-Ended List Example

package com.sneppets.dsalgo;

class Link
{
	//data item
	public int intData;
	
	//next link in the list
	public Link next;
	
	public Link(int iData)
	{
		intData = iData;
	}
	
	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 front
	public void insertFirst(int iData)
	{
		//create a new link
		Link newLink = new Link(iData);	
		//check if list is empty and newLink <-- last
		if(isEmpty())
		{
			//set last to the new link
			last = newLink;
		}
		//new link --> old first
		newLink.next = first;
		//first --> new link
		first = newLink;
	}
	
	//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()
	{
		System.out.println("List from first to last :");
		//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(" ");
	}
	
}
/**
 * 
 * @author sneppets.com
 *
 */
public class DoubleEndedListExample {
	
	public static void main (String[] args)
	{
		DoubleEndedLinkedList doubleEndedLL = new DoubleEndedLinkedList();
		//insert at first
		doubleEndedLL.insertFirst(10);
		doubleEndedLL.insertFirst(20);
		doubleEndedLL.insertFirst(30);
		doubleEndedLL.insertFirst(40);
		//display list
		doubleEndedLL.displayList();
		//insert at last
		doubleEndedLL.insertLast(100);
		doubleEndedLL.insertLast(200);
		doubleEndedLL.insertLast(300);
		doubleEndedLL.insertLast(400);
		//display list
		doubleEndedLL.displayList();
		//delete first two list items
		doubleEndedLL.deleteFirst();
		doubleEndedLL.deleteFirst();
		//display list
		doubleEndedLL.displayList();
	
	}

}

Output

List from first to last :
40 30 20 10  
List from first to last :
40 30 20 10 100 200 300 400  
List from first to last :
20 10 100 200 300 400

Recommended Posts

• Simple Linked List 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