Singly LinkedList implementation (insert/delete at first) in java


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



What is Single LinkedList in java?
A 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 (in other words, a link) to the next node in the sequence.
Below we are going to implement LinkedList without taking help of api’s provided by jdk.

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

Important methods used in below Single LinkedList program/example are as follows>
  insertFirst(int data)-  Inserts New Node at first of Singly LinkedList in java       
  deleteFirst() -Deletes first Node of Single LinkedList in java
  displayLinkedList() - displays Single LinkedList in java.
         

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

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

Here we see that newNode start pointing to old first and first start pointing to newNode in java.


Let’s see how we are going delete first node from Singly LinkedList in java:-
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 Singly LinkedList in java >
/**
*Exception to indicate that Singly 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 of Singly LinkedList.
*/
class Node {
   public int data; // data in Node.
   public Node next; // points to next Node in list.
   /**
   * Constructor
   */
   public Node(int data){
          this.data = data;
   }
   /**
   * Display Node's data
   */
   public void displayNode() {
          System.out.print( data + " ");
   }
}
/**
* Singly LinkedList class
*/
class LinkedList {
   private Node first; // ref to first link on list
   /**
   * Singly LinkedList constructor
   */
   public LinkedList(){
          first = null;
   }
   /**
   * Insert New Node at first position in Singly LinkedList
   */
   public void insertFirst(int data) {
          Node newNode = new Node(data); //Creation of New Node.
          newNode.next = first;   //newLink ---> old first
          first = newNode; //first ---> newNode
   }
   /**
   * Deletes first Node of Singly 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; // save reference to first Node in tempNode- so that we could return saved reference.
          first = first.next; // delete first Node (make first point to second node)
          return tempNode; // return tempNode (i.e. deleted Node)
   }
  
         
   /**
   * Display Singly LinkedList
   */
   public void displayLinkedList() {
          System.out.print("Displaying LinkedList [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();
         
   }
}
 
 
/** Copyright (c), AnkitMittal JavaMadeSoEasy.com */
/**
* Main class - To test Singly LinkedList .
*/
public class SinglyLinkedListInsertDeleteFirstExample {
   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.displayLinkedList(); // display LinkedList
                      
          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.displayLinkedList(); //Again display LinkedList
         
         
         
   }
}
/*OUTPUT
Displaying LinkedList [first--->last]: 39 14 59 21 11
Deleted Nodes: 39 14
Displaying LinkedList [first--->last]: 59 21 11
*/


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

So in this Data structures tutorial we learned what is Singly LinkedList in java with example, diagrams and program. We learned how to implement your own Single LinkedList in java. We learned how to insert and delete at first of Singly LinkedList in java. We also learned complexity of insert and delete operations at first of Singly LinkedList 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