Custom Sorted Singly LinkedList(Single LinkedList) - insert Nodes in between in java



In this Data structures tutorial we will learn what is Single LinkedList in java with example and program. We will learn how to implement your own Single LinkedList in java. We will learn how to insert Node in between Singly LinkedList in java. We will also learn complexity of inserting Node in between of Singly LinkedList in java.


What is Sorted Singly LinkedList in java?
Sorted Singly Linked List is a data structure in which all the nodes are arranged in sorted manner.
We will implement sorted Singly Linked List in ascending order of its data in java.
Below we are going to implement Sorted Singly LinkedList without taking help of api’s provided by jdk.
Complexity of insertion in Sorted Singly LinkedList is O(n).

Important methods used in below sorted Singly LinkedList program/example are as follows>
  insertNodeInSortedLinkedList(int data)-  Insert Node in Sorted Singly LinkedList (in between of other Nodes) in java.     


Logic explanation of how to insert Node in between sorted Singly LinkedList in java with diagram>


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


Here as soon as we detect the position at which node is to be inserted we make
>newNode’s next point to previous node’s next &
>previous node’s next point to newNode.

Full Program/SourceCode to insert Node in between sorted Singly LinkedList in java>
/**
*Exception to indicate that Sorted 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 + " ");
   }
}
/**
* Sorted Singly LinkedList class
*/
class LinkedList {
   private Node first; // ref to first link on list
   /**
   * LinkedList constructor
   */
   public LinkedList(){
          first = null;
   }
   /**
   *Insert Node in Sorted LinkedList (in between of other Nodes).
   *Note:- Sorted LinkedList is arranged in ascending order.
   */
   public void insertNodeInSortedLinkedList(int data){
         
          Node newNode=new Node(data);
         
          //Case1: when there is no element in LinkedList
          if(first==null){ //means LinkedList is empty, make first point to new Node.
                 first=newNode;  //first ---> newNode
                 System.out.println("Node with data="+newNode.data+" inserted at first.");
                 return;
          }
         
          //Case2: when newNode should be placed at first.
          if(first.data>=newNode.data){
                 newNode.next=first;
                 first=newNode; //first ---> newNode
                 System.out.println("Node with data="+newNode.data+" inserted at first Node, beacuse newNode is smallest of existing Nodes.");
                 return;
          }
         
          //Case3: when newNode should be at some position other than first.
          Node current=first;
          Node previous=null;
          while(current!=null){
                 if(current.data<newNode.data){
                       if(current.next==null){ //means current is last node, insert new node after current.
                              current.next=newNode;
                              System.out.println("Node with data="+newNode.data+" inserted successfully at last of LinkedList.");
                              return;
                       }
                       previous=current;
                       current=current.next; //move to next node.
                 }
                 else{
                       newNode.next=previous.next; //make new node's next point to previous node's next
                       previous.next=newNode; //make previous nodes' next point to new node.
                       System.out.println("Node with data="+newNode.data+" inserted successfully in middle of LinkedList.");
                       return;
                 }
          }
   }
  
  
  
   /**
   * Display Sorted 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 */
/**
* SortedSinglyLinkedListInsertNodeBetweenExample - Main class - To test Sorted Singly LinkedList.
*/
public class SortedSinglyLinkedListInsertNodeBetweenExample {
   public static void main(String[] args) {
          LinkedList linkedList = new LinkedList(); // creation of Linked List
         
          linkedList.displayLinkedList(); // display LinkedList
          linkedList.insertNodeInSortedLinkedList(92);
          linkedList.insertNodeInSortedLinkedList(20);
          linkedList.insertNodeInSortedLinkedList(19);
          linkedList.insertNodeInSortedLinkedList(29);
          linkedList.insertNodeInSortedLinkedList(99);
          linkedList.displayLinkedList(); //Again display LinkedList
                      
   }
}
/*OUTPUT
Displaying LinkedList [first--->last]:
Node with data=92 insereted at first.
Node with data=20 inserted at first Node, beacuse newNode is smallest of existing Nodes.
Node with data=19 inserted at first Node, beacuse newNode is smallest of existing Nodes.
Node with data=29 inserted successfully in middle of LinkedList.
Node with data=99 inserted successfully at last of LinkedList.
Displaying LinkedList [first--->last]: 19 20 29 92 99
*/

Complexity of insert Node in between sorted Singly LinkedList in java >
Best Case :    O(1), when there is no node in List and insertion is to be done at first.
or, node to be inserted is smallest of existing nodes in LinkedList(in case if
    we are arranging LinkedList in ascending order.)
Average Case :  O(n)
Worst Case : O(n)



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>
1) Stacks, Queues in Data Structures in java

2) Single LinkedList implementations in Data Structures in java:-

3) Doubly LinkedList implementations in Data Structures in java:-
4)Implement Stack, Queue using LinkedList

5) Some of the tricky and interesting Single LinkedList implementations in Data Structures in java



6) Binary tree tutorial in java >

>PreOrder traversal of Binary Tree in java

>InOrder traversal of Binary Tree in java

>PostOrder traversal of Binary Tree in java




eEdit
Must read for you :