Doubly Linked list in Java

Doubly Linked List In Java

Doubly Linked List in Java is a mutated version of Linked List. Similar to a Linked List Doubly Linked List also stores data elements of homogeneous data type in a linear format. The difference in a Linked List and a Doubly Linked is that, instead of only one Link after the data in a normal Linked List, Doubly Linked List has three fields, Namely,

  • A Link to the Previous Node in the List
  • Data
  • A Link to the Next node in the List

Doubly Linked List has the advantage of being more efficient in performing various operations on it Since it can be travesed much more efficiently.

Structure of a Doubly Linked List

Structure of a Doubly Linked List

class Node { 
int data;
Node previous;
Node next;
public Node (int data) {
this.data = data;
}
}
Advantages of Doubly Linked List

Merits of Doubly Linked List

  • A Doubly Linked List can be traversed in any given Direction Since it has pointers to both the next and tha previous Node of the List.
  • It is easier to reverse a Doubly Linked List.
  • Both Deletion and Insertion and easier in a Doubly Linked List.
Disadvantages of Doubly Linked List

Demerits of Doubly Linked List

  • Every operation on a Doubly Linked List require an extra step to perform calculations on that extra address stored with each node.
  • Every Node requires a extra space in the memory to store that one extra address.
Doubly Linked List in JAVA

Operations on a Doubly Linked List

Following operations can be performed on a doubly linked list:-

  • Insertion
    • Insertion at beginning.
    • Insertion at end.
    • Insertion at specific position.
  • Deletion
    • Deletion from beginning.
    • Deletion from end.
    • Deletion from specific position.

Code for Implementing Doubly Linked List in JAVA

import java.util.*;

class PrepInsta {
//Represent the head and tail of the doubly linked list
  Node head, tail = null;

  public static void main (String[]args)
  {

    PrepInsta dll = new PrepInsta ();
//Input nodes to the list
    dll.addNode (10);
    dll.addNode (20);
    dll.addNode (30);
    dll.addNode (40);
    dll.addNode (50);

//Displays the nodes present in the list
    dll.printll ();
  }

//addNode() will add a node to the list
  public void addNode (int data)
  {
//Create a new node
    Node newNode = new Node (data);

//If list is empty
    if (head == null)
      {
	head = tail = newNode;
	head.previous = null;
	tail.next = null;
      }
    else
      {
	tail.next = newNode;
	newNode.previous = tail;
	tail = newNode;
	tail.next = null;
      }
  }

//printll() will print out the nodes of the list
  public void printll ()
  {
//Node current will point to head
    Node current = head;
    if (head == null)
      {
	System.out.println ("List is empty");
	return;
      }
    System.out.println ("Nodes of doubly linked list are: ");
    while (current != null)
      {
       //Prints each node by increasing order of the pointer.
       System.out.print (current.data + "-->");
       current = current.next;
      }
      if(current==null)
         System.out.println("END");
  }

//Represent a node of the doubly linked list

  class Node
  {
    int data;
    Node previous;
    Node next;

    public Node (int data)
    {
      this.data = data;
    }
  }
}
Nodes of doubly linked list are: 
10-->20-->30-->40-->50-->END
Quiz time

Fun Fact

Doubly Linked List in Real Life can be seen implemented in back and forward buttons in a browser navigation. Also the undo and redo buttons are a great example of application of Doubly Linked List.