Question

Write a method that inserts a node in a sorted linked list. HINTS: Traverse the list and find a position for the element and insert it.

Answer 1

Node.java

public class Node {
   int data;
Node next;
Node(int data) {
   this.data = data;
   this.next = null;
}
}

SortedLinkedList.java

public class SortedLinkedList {
  
   Node head;

   //method to insert a value in the sorted linked list, such list remains sorted after the insertion.
   public void insert(int data) {
       //creating a new Node with passed argument
       Node newNode = new Node(data);
       System.out.println("Inserting: " + data);
       //checking for head
       //if the list is empty or
       //we need to change the head that is new Node is smaller than the head node.
       if(head == null || head.data >= newNode.data) {
           newNode.next = head;
           head = newNode;
       }
       else {
           //else
           Node currNode = head;
          
           //locate the appropriate position in the list, where we need to insert the
           //new node before actual insertion.
           while(currNode.next != null && currNode.next.data < newNode.data) {
               currNode = currNode.next;
           }
          
           //when position found, insert the node.
           newNode.next = currNode.next;
           currNode.next = newNode;
       }
   }
  
   //a helper method to print the list
   public void printList() {
       Node ptr = this.head;
      
       System.out.print("List: ");
       while(ptr != null) {
           System.out.print(ptr.data + " ");
           ptr = ptr.next;
       }
       System.out.println();
   }
  
   public static void main(String[] args) {
      
       SortedLinkedList list = new SortedLinkedList();
       list.insert(10);
       list.printList();
       list.insert(20);
       list.printList();
       list.insert(30);
       list.printList();
       list.insert(5);
       list.printList();
       list.insert(14);
       list.printList();
       list.insert(22);
       list.printList();
       list.insert(11);
       list.printList();
   }

}

IF THERE IS ANYTHING THAT YOU DO NOT UNDERSTAND, OR NEED MORE HELP THEN PLEASE MENTION IT IN THE COMMENTS SECTION.