Doubly Linked List Data Structures & Algorithms

In our previous article you have seen Double-ended Linked List. Doubly linked list is another variation of Linked Lists and don’t confuse with double-ended list.

An important problem that doubly linked list solves is it provides a way to traverse backward in the list, whereas with the ordinary linked lists it is difficult to traverse backward along the list. This limitation is overcome by doubly linked list.

Each link in doubly linked list has two references to other links instead of one link. The first reference is to the next link and the second reference is to the previous link.

Supported Operations

  • insertFirst() – insert at front of the list
  • insertLast() – insert at end of the list
  • insertAfter() – insert data after the specified key
  • deleteFirst() – delete first link
  • deleteLast() – delete last link
  • deleteKey() – delete link based on the key provided

Doubly Linked List Example

A doubly linked list need not be double-ended linked list (keep a reference to the last element in the list) necessarily. But in our example below we will include reference to the last element also.

package com.sneppets.dsalgo;


/**
 * Link
 */

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

class DoublyLinkedList
{
	//reference to first link
	private Link first;
	
	//reference to last link
	private Link last;
	
	public DoublyLinkedList()
	{
		//no items on the list yet
		first = null;
		last = null;
	}
	
	//return true if there are no links
	public boolean isEmpty()
	{
		return (first == null);
	}
	
	//insert at front of the list
	public void insertFirst(int iData)
	{	
		//create a new link
		Link newLink = new Link(iData);
		if(isEmpty())
		{
			//if list is empty last --> newLink
			last = newLink;
		}
		else
		{
			//old first --> newLink
			first.prev = newLink;
		}
		//newLink --> old first
		newLink.next = first;
		//insert new link at first
		first = newLink;
	}
	
	//insert at end of the list
	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;
			//newLink --> old last
			newLink.prev = last;
		}
		//insert new link at last
		last = newLink;
	}
	
	//insert iData after key
	public boolean insertAfter(int key, int iData)
	{
		//start from first/begining
		Link curLink = first;
		//until match is found
		while(curLink.intData != key)
		{	
			//move to next link
			curLink = curLink.next;
			if(curLink == null)
			{
				return false;
			}
		}
		//create a new link
		Link newLink = new Link(iData);
		//if last link
		if (curLink == last)
		{
			newLink.next = null;
			last = newLink;
		}
		else
		{
			newLink.next = curLink.next;
			curLink.next.prev = newLink;
		}
		newLink.prev = curLink;
		curLink.next = newLink;		
		return true;
	}
	
	//delete first link
	public Link deleteFirst()
	{
		//save reference to first link 
		Link temp = first;
		//check if only one item is there in the list
		if(first.next == null)
		{
			last = null;
		}
		else
		{
			//old next --> null
			first.next.prev = null;
		}
		//first --> old next
		first = first.next;
		return temp;
	}
	
	//delete last link
	public Link deleteLast()
	{
		//save reference to last link 
		Link temp = first;
		//check if only one item is there in the list
		if(first.next == null)
		{
			first = null;
		}
		else
		{
			//old previous --> null
			last.prev.next = null;
		}
		//last --> old prev
		last = last.prev;
		return temp;
	}	
	
	//delete based on the provided key
	public Link deleteKey(int key)
	{
		//start at the beginning
		Link curLink = first;
		//until match is found
		while(curLink.intData != key)
		{
			curLink = curLink.next;
			if(curLink == null)
			{
				return null;
			}
		}
		//match is found; is that first item in the list ?
		if(curLink == first)
		{
			first = curLink.next;
		}
		else
		{
			curLink.prev.next = curLink.next;
		}
		//match is found; is that last item in the list ?
		if(curLink == last)
		{
			last = curLink.prev;
		}
		else
		{
			curLink.next.prev = curLink.prev;
		}		
		return curLink;
	}
	
	//display items in the list starting from first to last
	public void displayForward()
	{
		System.out.println("displayForward(): List from first to last :");
		//start at the beginning
		Link curLink = first;
		//until you reach end of the list
		while(curLink != null)
		{
			//display link data
			curLink.displayLink();
			//move to next link
			curLink = curLink.next;
		}
		System.out.println(" ");
	}
	
	//display items in the list starting from last to first
	public void displayBackward()
	{
		System.out.println("displayBackward(): List from last to first :");
		//start from last
		Link curLink = last;
		//until you reach start of the list
		while(curLink != null)
		{
			//display link data
			curLink.displayLink();
			//move to previous link
			curLink = curLink.prev;
		}
		System.out.println(" ");
	}
	
}

public class DoublyLinkedListExample {
	
	public static void main (String[] args)
	{
		//create new doubly linked list
		DoublyLinkedList doublyLinkedList = new DoublyLinkedList();
		//insert at front
		doublyLinkedList.insertFirst(20);
		doublyLinkedList.insertFirst(50);
		doublyLinkedList.insertFirst(70);
		//insert at end
		doublyLinkedList.insertLast(10);
		doublyLinkedList.insertLast(30);
		doublyLinkedList.insertLast(60);
		//display list forward
		doublyLinkedList.displayForward();
		//display list backward
		doublyLinkedList.displayBackward();
		
		//delete one last item and one first item
		doublyLinkedList.deleteLast();
		doublyLinkedList.deleteFirst();
		doublyLinkedList.deleteKey(10);
		
		//display list forward
		doublyLinkedList.displayForward();
		
		//insert again "10" after "20"
		doublyLinkedList.insertAfter(20, 10);
		
		//display list forward
		doublyLinkedList.displayForward();
		
	}	

}

Output

displayForward(): List from first to last :
70 50 20 10 30 60  
displayBackward(): List from last to first :
60 30 10 20 50 70  
displayForward(): List from first to last :
50 20 30  
displayForward(): List from first to last :
50 20 10 30  

Drawback of doubly linked list

Every time you insert or delete a link you must deal with four links instead of two since each link has extra reference.

Recommended Posts

References

Leave a Reply

avatar
  Subscribe  
Notify of