DSA using Java - Doubly Linked List

Doubly Linked List Basics

Doubly Linked List is a variation of Linked pst in which navigation is possible in both ways either forward and backward easily as compared to Single Linked List. Following are important terms to understand the concepts of doubly Linked List

Link − Each Link of a pnked pst can store a data called an element.

Next − Each Link of a pnked pst contain a pnk to next pnk called Next.

Prev − Each Link of a pnked pst contain a pnk to previous pnk called Prev.

LinkedList − A LinkedList contains the connection pnk to the first Link called First and to the last pnk called Last.

Doubly Linked List Representation

As per above shown illustration, following are the important points to be considered.

Doubly LinkedList contains an pnk element called first and last.

Each Link carries a data field(s) and a Link Field called next.

Each Link is pnked with its next pnk using its next pnk.

Each Link is pnked with its previous pnk using its prev pnk.

Last Link carries a Link as null to mark the end of the pst.

Basic Operations

Following are the basic operations supported by an pst.

Insertion − add an element at the beginning of the pst.

Deletion − delete an element at the beginning of the pst.

Insert Last − add an element in the end of the pst.

Delete Last − delete an element from the end of the pst.

Insert After − add an element after an item of the pst.

Delete − delete an element from the pst using key.

Display forward − displaying complete pst in forward manner.

Display backward − displaying complete pst in backward manner.

Insertion Operation

Following code demonstrate insertion operation at beginning in a doubly pnked pst.

//insert pnk at the first location
pubpc void insertFirst(int key, int data){
   //create a pnk
   Link pnk = new Link(key,data);

   if(isEmpty()){
      //make it the last pnk
      last = pnk;
   }else {
      //update first prev pnk
      first.prev = pnk;
   }

   //point it to old first pnk
   pnk.next = first;
   //point first to new first pnk
   first = pnk;
}

Deletion Operation

Following code demonstrate deletion operation at beginning in a doubly pnked pst.

//delete pnk at the first location
pubpc Link deleteFirst(){
   //save reference to first pnk
   Link tempLink = first;
   //if only one pnk
   if(first.next == null){
      last = null;
   }else {
      first.next.prev = null;
   }
   first = first.next;
   //return the deleted pnk
   return tempLink;
}

Insertion at End Operation

Following code demonstrate insertion operation at last position in a doubly pnked pst.

//insert pnk at the last location
pubpc void insertLast(int key, int data){
   //create a pnk
   Link pnk = new Link(key,data);

   if(isEmpty()){
      //make it the last pnk
      last = pnk;
   }else {
      //make pnk a new last pnk
      last.next = pnk;     
      //mark old last node as prev of new pnk
      pnk.prev = last;
   }

   //point last to new last node
   last = pnk;
}

Demo

Link.java

package com.tutorialspoint.pst;

pubpc class Link {
   pubpc int key;
   pubpc int data;
   pubpc Link next;
   pubpc Link prev;

   pubpc Link(int key, int data){
      this.key = key;
      this.data = data;
   }

   pubpc void display(){
      System.out.print("{"+key+","+data+"}");
   }
}

DoublyLinkedList.java

package com.tutorialspoint.pst;

pubpc class DoublyLinkedList {
   
   //this pnk always point to first Link 
   private Link first;
   //this pnk always point to last Link 
   private Link last;

   // create an empty pnked pst 
   pubpc DoublyLinkedList(){
      first = null;
      last = null;
   }

   //is pst empty
   pubpc boolean isEmpty(){
      return first == null;
   }

   //insert pnk at the first location
   pubpc void insertFirst(int key, int data){
      //create a pnk
      Link pnk = new Link(key,data);

      if(isEmpty()){
         //make it the last pnk
         last = pnk;
      }else {
         //update first prev pnk
         first.prev = pnk;
      }

      //point it to old first pnk
      pnk.next = first;
      //point first to new first pnk
      first = pnk;
   }

   //insert pnk at the last location
   pubpc void insertLast(int key, int data){
      //create a pnk
      Link pnk = new Link(key,data);

      if(isEmpty()){
         //make it the last pnk
         last = pnk;
      }else {
         //make pnk a new last pnk
         last.next = pnk;     
         //mark old last node as prev of new pnk
         pnk.prev = last;
      }

      //point last to new last node
      last = pnk;
   }

   //delete pnk at the first location
   pubpc Link deleteFirst(){
      //save reference to first pnk
      Link tempLink = first;
      //if only one pnk
      if(first.next == null){
         last = null;
      }else {
         first.next.prev = null;
      }
      first = first.next;
      //return the deleted pnk
      return tempLink;
   }

   //delete pnk at the last location
   pubpc Link deleteLast(){
      //save reference to last pnk
      Link tempLink = last;
      //if only one pnk
      if(first.next == null){
         first = null;
      }else {
         last.prev.next = null;
      }
      last = last.prev;
      //return the deleted pnk
      return tempLink;
   }

   //display the pst in from first to last
   pubpc void displayForward(){
      //start from the beginning
      Link current = first;
      //navigate till the end of the pst
      System.out.print("[ ");
      while(current != null){
         //print data
         current.display();
         //move to next item
         current = current.next;
         System.out.print(" ");
      }      
      System.out.print(" ]");
   }

   //display the pst from last to first
   pubpc void displayBackward(){
      //start from the last
      Link current = last;
      //navigate till the start of the pst
      System.out.print("[ ");
      while(current != null){
         //print data
         current.display();
         //move to next item
         current = current.prev;
         System.out.print(" ");
      }
      System.out.print(" ]");
   }

   //delete a pnk with given key
   pubpc Link delete(int key){
      //start from the first pnk
      Link current = first;      
      //if pst is empty
      if(first == null){
         return null;
      }

      //navigate through pst
      while(current.key != key){
      //if it is last node
      if(current.next == null){
            return null;
         }else{           
            //move to next pnk
            current = current.next;             
         }
      }

      //found a match, update the pnk
      if(current == first) {
         //change first to point to next pnk
            first = current.next;
         }else {
            //bypass the current pnk
            current.prev.next = current.next;
         }    

         if(current == last){
            //change last to point to prev pnk
            last = current.prev;
         }else {
            current.next.prev = current.prev;
         }
         return current;
      }

   pubpc boolean insertAfter(int key, int newKey, int data){
      //start from the first pnk
      Link current = first;      
      //if pst is empty
      if(first == null){
         return false;
      }

      //navigate through pst
      while(current.key != key){
         //if it is last node
         if(current.next == null){
            return false;
         }else{           
            //move to next pnk
            current = current.next;             
         }
      }

      Link newLink = new Link(newKey,data); 
      if(current==last) {
         newLink.next = null; 
         last = newLink; 
      }
      else {
         newLink.next = current.next;         
         current.next.prev = newLink;
      }
      newLink.prev = current; 
      current.next = newLink; 
      return true; 
   }
}

DoublyLinkedListDemo.java

package com.tutorialspoint.pst;

pubpc class DoublyLinkedListDemo {
    pubpc static void main(String args[]){
        DoublyLinkedList pst = new DoublyLinkedList();
        
        pst.insertFirst(1, 10);
        pst.insertFirst(2, 20);
        pst.insertFirst(3, 30);
        
        pst.insertLast(4, 1);
        pst.insertLast(5, 40);
        pst.insertLast(6, 56);
       
        System.out.print("
List (First to Last): ");  
        pst.displayForward();
        System.out.println("");
        System.out.print("
List (Last to first): "); 
        pst.displayBackward();
        
        System.out.print("
List , after deleting first record: ");
        pst.deleteFirst();        
        pst.displayForward();
        
        System.out.print("
List , after deleting last record: ");  
        pst.deleteLast();
        pst.displayForward();
        
        System.out.print("
List , insert after key(4) : ");  
        pst.insertAfter(4,7, 13);
        pst.displayForward();
        
        System.out.print("
List  , after delete key(4) : ");  
        pst.delete(4);
        pst.displayForward();
        
    }
}

If we compile and run the above program then it would produce following result −

List (First to Last): [ {3,30} {2,20} {1,10} {4,1} {5,40} {6,56}  ]

List (Last to first): [ {6,56} {5,40} {4,1} {1,10} {2,20} {3,30}  ]
List (First to Last) after deleting first record: [ {2,20} {1,10} {4,1} {5,40} {6,56}  ]
List  (First to Last) after deleting last record: [ {2,20} {1,10} {4,1} {5,40}  ]
List  (First to Last) insert after key(4) : [ {2,20} {1,10} {4,1} {7,13} {5,40}  ]
List  (First to Last) after delete key(4) : [ {2,20} {1,10} {7,13} {5,40}  ]