DoublyLinkedList - insert and delete at first in java


In this Data structures tutorial we will learn what is Doubly LinkedList in java with example, diagrams and program. We will learn how to implement your own Doubly LinkedList in java. We will learn how to insert and delete at first of Doubly LinkedList in java. We will also learn complexity of insert and delete operations at first of Doubly LinkedList in java.



What is Doubly LinkedList in java?
A Doubly linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a reference to the next and previous node in the sequence.

What is complexity of insert and delete at first of Doubly LinkedList in java?
Complexity of insertion and deletion at first of Doubly LinkedList is O(1) in java.

Important methods used in below doubly LinkedList program/example are as follows>
  insertFirst(int data)-  Insert New Node at first of Doubly LinkedList in java.       
  deleteFirst() -Deletes first Node of Doubly LinkedList in java.
  displayFrwd() - displays doubly linkedList in forward direction in java.
  displayBckwrd() - displays doubly linkedList in forward direction in java.
         


Logic explanation to insert and delete at first of Doubly LinkedList with diagram in java >

Let’s see how we are going to insert node at first in Doubly LinkedList in java :-


Here we have made newNode’s next pointing to old first. & first point to new node.

Let’s see how we can delete first node from Doubly LinkedList.
Here we make first point to first.next and there is no live reference to node with data=11(i.e. deleted node), so this node becomes eligible for garbage collection by JVM as well.


Full Program/Example of insert and delete at first of doubly LinkedList in java >
/**
*Exception to indicate that Doubly LinkedList is empty.
*/
class LinkedListEmptyException extends RuntimeException{
     public LinkedListEmptyException(){
       super();
     }
  
   public LinkedListEmptyException(String message){
       super(message);
     }  
}
/**
*Node class, which holds data and contains next which points to next Node.
*/
class Node {
   public int data; // data in Node.
   public Node next; // points to next Node in list.
   public Node previous; // points to previous Node in list.
   /**
   * Constructor
   */
   public Node(int data){
          this.data = data;
   }
   /**
   * Display Node's data
   */
   public void displayNode() {
          System.out.print( data + " ");
   }
}
/**
* Doubly LinkedList class
*/
class LinkedList {
   private Node first; // ref to first link on LinkedList
   private Node last; // ref to last link on LinkedList
   /**
   * Doubly LinkedList constructor
   */
   public LinkedList(){
          first = null;
   }
  
   /**
   * Insert New Node at first position of Doubly LinkedList
   */
  
   public void insertFirst(int data){ // insert at front of list
          Node newNode = new Node(data); // creation of new node.
          if (first == null) // means LinkedList is empty.
                 last = newNode; //  newNode <--- last
          else
                 first.previous = newNode; // newNode <-- old first
          newNode.next = first; // newNode --> old first
          first = newNode; // first --> newNode
   }
   /**
   * Delete first node of Doubly linkedList.
   */
   public Node deleteFirst() {
               
          if(first==null){ //means LinkedList in empty, throw exception.             
                 throw new LinkedListEmptyException("LinkedList doesn't contain any Nodes.");
          }

          Node tempNode = first;
          if (first.next == null) // if only one item
                 last = null; // null <-- last
          else
                 first.next.previous = null; // null <-- old next
          first = first.next; // first --> old next
          return tempNode;
   }
  
   /*
   * Display Doubly LinkedList in forward direction
   */
   public void displayFrwd() {
          System.out.print("Displaying in forward direction [first--->last] : ");
          Node tempDisplay = first; // start at the beginning of linkedList
          while (tempDisplay != null){ // Executes until we don't find end of list.
                 tempDisplay.displayNode();
                 tempDisplay = tempDisplay.next; // move to next Node
          }
          System.out.println("");
   }
   /*
   * Display Doubly LinkedList in backward direction
   */
   public void displayBckwrd() {
          System.out.print("Displaying in backward direction [last-->first] : ");
          Node tempDisplay = last; // start at the end of linkedList
          while (tempDisplay != null) {// Executes until we don't find start of list.   
                 tempDisplay.displayNode();
                 tempDisplay = tempDisplay.previous; // move to previous Node
          }
          System.out.println("");
   }
  
}
 
 
/** Copyright (c), AnkitMittal www.JavaMadeSoEasy.com */
/**
* DoublyLinkedListInsertDeleteAtFirstExample - Main class - To test Doubly LinkedList.
*/
public class DoublyLinkedListInsertDeleteAtFirstExample {
   public static void main(String[] args) {
          LinkedList linkedList = new LinkedList(); // creation of Linked List
         
          linkedList.insertFirst(11);
          linkedList.insertFirst(21);
          linkedList.insertFirst(59);
          linkedList.insertFirst(14);
          linkedList.insertFirst(39);
          linkedList.displayFrwd(); // display DoublyLinkedList
          linkedList.displayBckwrd();
                      
          System.out.print("Deleted Nodes: ");
          Node deletedNode = linkedList.deleteFirst(); //delete Node
          deletedNode.displayNode();                                 //display deleted Node.
          deletedNode = linkedList.deleteFirst();      //delete Node.
          deletedNode.displayNode();                                 //display deleted Node.
         
          System.out.println();// sysout used to format output
         
          linkedList.displayFrwd(); // display DoublyLinkedList
          linkedList.displayBckwrd();
         
         
   }
}
/*OUTPUT
Displaying in forward direction [first--->last] : 39 14 59 21 11
Displaying in backward direction [last-->first] : 11 21 59 14 39
Deleted Nodes: 39 14
Displaying in forward direction [first--->last] : 59 21 11
Displaying in backward direction [last-->first] : 11 21 59
*/


Complexity of insert and delete at first in doubly LinkedList in java >
Complexity of insertion and deletion at first in doubly LinkedList is O(1).
As we have to insert at first> best case, average case and worst case are same in java.


Having any doubt? or you you liked the tutorial! Please comment in below section.
Please express your love by liking JavaMadeSoEasy.com (JMSE) on facebook, following on google+ or Twitter.



RELATED LINKS>

Singly LinkedList implementations in java:-



Doubly LinkedList implementations in java:-



Some of the tricky and interesting Singly LinkedList implementations in java





Implement Stack, Queue using LinkedList.

No comments:

Post a Comment