Data Structure : Doubly Link List

The Doubly Linked List is a Java Singly Linked List with a reference present to refer to the previous node as well.
Doubly Linked List is use in scenarios where deletion is more frequent.

Below is the video that explains the insert mechanism in a double linked list.

Below is the structure of each node. Note unlike Singly Linked List, it has two nodes. Next and Prev

class Node {
 public int data;
 public Node next;
 public Node prev;
}

A 'start' node is used to always point to the first node. This makes sure the Linked List is not lost in memory.

static Node start;

Below code is for addition of nodes in a Doubly Linked List. The code adds the element to the end of the list. Some modification can be made to add a element in between by passing the index along with data.

 private static void add(int i) {
  System.out.println("Adding :" + i);
  // Create new node
  Node p = new Node();
  p.data = i;
  // Check if List is empty, If yes than point 'start' to the newly
  // created node
  if (start == null) {
   start = p;
  } else {
   // If the list is not empty, than traverse till the end of the list
   // and add the node
   Node s = start;
   while (s.next != null) {
    s = s.next;
   }
   s.next = p;
   p.prev = s;
  }

 }

Below code is for deletion of a node. The parameter passed is the value of int in each node. The values is matched against each node and than that node is deleted. It is important the the deleted node is made null so that it is available for garbage collection.

 private static void delete(int i) {
  System.out.println("Deleting element : " + i);
  //Create a reference node
  Node s = start;
  //Iterate till the element to be deleted is found
  while (s.data != i) {
   s = s.next;
  }
  //Attach the previous element's 'next' to 'next' of the to be deleted element
  s.prev.next = s.next;
  //Attach the 'next' elements 'prev' to 'prev' of the to be deleted element
  s.next.prev=s.prev;
  
  //Make deleted element available for garbage collection
  s.prev=null;
  s.next=null;
  
 }

Below is the complete code to test the Doubly Linked List

package com.doubly;


class Node {
 public int data;
 public Node next;
 public Node prev;
}

public class DoublyLinkedList {

 static Node start;

 public static void main(String[] args) {
  System.out.println("1.Adding elements");
  add(10);
  add(20);
  add(30);
  add(40);
  System.out.println("\n2.Display elements in Linked List");
  display();
  System.out.println("\n3.Delete element");
  delete(30);
  System.out.println("\n4.Display elements Linked List");
  display();

 }

 private static void add(int i) {
  System.out.println("Adding :" + i);
  // Create new node
  Node p = new Node();
  p.data = i;
  // Check if List is empty, If yes than point 'start' to the newly
  // created node
  if (start == null) {
   start = p;
  } else {
   // If the list is not empty, than traverse till the end of the list
   // and add the node
   Node s = start;
   while (s.next != null) {
    s = s.next;
   }
   s.next = p;
   p.prev = s;
  }

 }

 private static void display() {
  
  Node s = start;

  while (s != null) {

   System.out.println(s.data);
   s = s.next;
  }

 }

 private static void delete(int i) {
  System.out.println("Deleting element : " + i);
  //Create a reference node
  Node s = start;
  //Iterate till the element to be deleted is found
  while (s.data != i) {
   s = s.next;
  }
  //Attach the previous element's 'next' to 'next' of the to be deleted element
  s.prev.next = s.next;
  //Attach the 'next' elements 'prev' to 'prev' of the to be deleted element
  s.next.prev=s.prev;
  
  //Make deleted element available for garbage collection
  s.prev=null;
  s.next=null;
  
 }

}

Output

1.Adding elements
Adding :10
Adding :20
Adding :30
Adding :40

2.Display elements in Linked List
10
20
30
40

3.Delete element
Deleting element : 30

4.Display elements Linked List
10
20
40

The advantage of double linked list over singly linked list is at the time of deleting a node from between the list. In singly linked list since there is no reference to the prev node, 2 round of iteration is to be done. First to get to the node which is to be deleted and then to get to the node just febore the node to be deleted.

In doubly linked list, by using the prev reference, deletion can be done in just one iteration.



Application/Usage of Doubly Linked List

Doubly Linked List are used in Many Collection classes such as LinkedList, HashMap, TreeMap, HashTable etc.

A example of usage of DoublyLinkedList in HashMap is provided Java Custom Hash Map : Internal Working.