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
- When to use linked list over an array for Stack or Queue ?
- Simple Linked List Example
- 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