Question

In Java im trying to use a recursive wrapper method for inserting a node in a linkedlist in order but Im having trouble figuring out how to sort these nodes. Any help would be greatly appreciated.

private Node insert(int key, Node head) {

       if(!find(key)) {
           /**
           if(key > head.data && head.link == null) {
               Node curr = new Node(key);
               head.link = curr;
               return curr = head;
           }

           if(key > head.data) {
               return insert(key, head.link);
           }
           if(key < head.data) {
               Node temp = head;
               head = new Node(key);
               return head.link = temp;
           }
           **/
           Node curr = new Node(key);

           curr.link = head;

           head = curr;
       }

       return insert(key, head.link);
   }

Answer 1

Dear Student,

As you want to store or insert the key values in linked list in sorted order. Hence I am considering this to be sorted in ascending order.

Since you have just shared only insert function not complete program of Linked List. So, I have created the same scenario but inside find method I am returning false always (considering that value is not present in linked list, even though we can insert the same value again and again). So, I am not re-writing the complete logic of find method because here the main focus is our insert method which should store the keys into the linked list in sorted order . If you need complete program with proper find method, please let me know in comments section and share the complete code snippet which you have created.

Screensbot of insert method is as below:-

Screenshot of complete program is mentioned below which I have made. Your complete program may be different from my program as I have just created this Linked List program to reproduce the issue which you were getting while inserting values in sorted order into the linked list.

Note:- You just need to replace your insert method to the method I have shared above.

Complete prgram in textual format is mentioned below. Insert method is shown in bold:-

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

public class LinkedList {

   private Node insert(int key, Node head) {
       //Insert only if key is not present
       if(!find(key)) {
           /*
           * Create Node class object only when you will get either value of head as null that
           * means that you are going to create first object of the list class or the node whose
           * key value is greater than the key value which we want to insert
           */
           if (head == null || head.data >= key) {
               //Create node class object
               Node node=new Node(key);
               //Set node link as head
               node.link = head;
              
               //return the newly inserted node
               return node;
           }
       }
       /* Otherwise recursive call insert function with the next node as head*/
       head.link= insert(key,head.link);
       return head;
   }
  
   public static void main(String[] args) {
       Node head=null;
       LinkedList linkedList=new LinkedList();
      
       /*Inserting the value 10 inside linked list as first node
       Since this is first node which will going to insert,
       Hence I am assigning the head value to the first node*/
       head=linkedList.insert(10, head);
      
       //Inserting 20 to the linked list and reassigning the head value
       head=linkedList.insert(20, head);
      
       //Inserting 7 to the linked list and reassigning the head value
       head=linkedList.insert(7, head);
      
       //Inserting 15 to the linked list and reassigning the head value
       head=linkedList.insert(15, head);
      
       //Inserting 14 to the linked list and reassigning the head value
       head=linkedList.insert(14, head);

       //Traversing the linked list
       System.out.println("Our Linked List in sorted order is as below:-");
       while(head!=null) {
           System.out.println(head.data);
           head=head.link;
       }
   }

   private boolean find(int key) {
       return false;
   }

}

Output of the above program is below. In the below screenshot we can see that the value we are getting in sorted order but in above program you can see that the order in which i am inserting the values are 10, 20, 7, 15, 14:-

Note:-

1. Most of the code contains the comments for your ready refrence.

2. Still, I am repeating that your complete code may be differed from my code. So you just need to replace the insert method code which I have shared above in bold.

Still, if you need any help. Please feel free to reach me through comments section. I will try to reply as early as possible.

Thanks!!