Singly LinkedList implementation (insert/delete at last) 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 Singly LinkedList in java. We will learn how to insert and delete at last of Singly LinkedList in java. We will also learn complexity of insert and delete operations at last of Singly LinkedList in java.



What is Singly 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.

What is complexity of insert and delete at last of Singly LinkedList in java?
Complexity of insertion and deletion at first of Singly LinkedList is O(n) in java.
(We could maintain pointer called last as well which points to last node in LinkedList, complexity of insertion and deletion  in that case will be O(1), we have maintained last pointer in Doubly LinkedList ).


Important methods used in below Singly LinkedList program/example are as follows>
  insertLast(int data)-  Insert New Node at last of Singly LinkedList in java.       
  deleteLast() -Deletes last Node of Singly LinkedList in java.
  displayLinkedList() - displays Singly LinkedList in java.       
         

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

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


Here we see that newNode start pointing to null and last node start pointing to newNode.



Let’s see how we are going delete node from last in Singly LinkedList in java:-
Here we see that first previous node’s next has started pointing to null and there is no live reference to current, so current has become eligible for garbage collection by JVM as well.


Full Program/example of insert and delete at last 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.
*/
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
   /**
   * LinkedList constructor
   */
   public LinkedList(){
          first = null;
   }
  
   /**
   * Inserts new Node at last of Singly LinkedList.
   */
   public void insertLast(int data){
          Node newNode = new Node(data); //Creation of New Node.
         
          if(first==null){ //means LinkedList is empty, make first point to new Node.
                 first=newNode;    //first ---> newNode
                 return;
          }
         
          Node tempNode = first; // save reference to first Node in tempNode- so that we could return saved reference.
          while(tempNode.next!=null){ //Executes until we don't find last Node of LinkedList.
                                                          //If next of some Node is pointing to null, that means it's a last Node.
                 tempNode=tempNode.next; //move to next Node.
          }
          tempNode.next=newNode; //make last's Node next point to new Node
   }
   /**
   * Deletes last Node from Singly LinkedList
   */
   public Node deleteLast(){
         
          //Case1: when there is no element in LinkedList
          if(first==null){ //means LinkedList in empty, throw exception.             
                 throw new LinkedListEmptyException("LinkedList doesn't contain any Nodes.");
          }
         
          //Case2: when there is only one element in LinkedList
          if(first.next==null){   //means LinkedList consists of only one element, delete that.
                 Node tempNode = first; // save reference to first Node in tempNode- so that we could return saved reference.
                 first=first.next; // delete firstNode (make first point to secondNode)
                 return tempNode; //return deleted Node.
          }
         
          //Case3: when there are atLeast two elements in LinkedList
          Node previous=null;
          Node current=first;
         
          while(current.next!=null){//Executes until we don't find last Node of LinkedList.
                                            //If next of some Node is pointing to null, that means it's a last Node.
                 previous=current;
                 current=current.next;   //move to next node.
          }
         
          previous.next=null;     //Now, previous is pointing to second last Node of LinkiedList,
                                                   //make it point to null [it byPasses current Node(last Node of LinkedList) which was in between]
          return current;
   }
  
   /**
   * Display 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 SinglyLinkedListInsertDeleteLastExample {
   public static void main(String[] args) {
          LinkedList linkedList = new LinkedList(); // creation of Linked List
         
          linkedList.insertLast(11);
          linkedList.insertLast(21);
          linkedList.insertLast(59);
          linkedList.insertLast(14);
          linkedList.insertLast(39);
          linkedList.displayLinkedList(); // display LinkedList
         
          System.out.print("Deleted Nodes: ");
          Node deletedNode = linkedList.deleteLast(); //delete Node
          deletedNode.displayNode();                                 //display deleted Node.
          deletedNode = linkedList.deleteLast();   //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]: 11 21 59 14 39
Deleted Nodes: 39 14
Displaying LinkedList [first--->last]: 11 21 59
*/


Complexity of insert and delete at last in Singly LinkedList in java >

Insertion at last in Singly LinkedList in java >
Best Case :    O(1), when there is no node in Singly LinkedList and insertion is to be done at first.
Average Case :  O(n)
Worst Case : O(n)

Deletion at last in Singly LinkedList in java >
Best Case :    O(1), when there is only one node in Singly LinkedList.
Average Case :  O(n)
Worst Case : O(n)

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 Singly LinkedList in java. We learned how to insert and delete at last of Singly LinkedList in java. We also learned complexity of insert and delete operations at last 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>

Stacks, Queues 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