Add a void method addInOrder to the LinkedList class which takes an integer val as a parameter. It should find the correct location in the already-sorted (lowest to highest) list for val, then make a new node with val as its data, correctly connecting it into the list. It should complete without exceptions, regardless of where val needs to be located in the list or how many items are in the list already.

 

Note: You may feel free to add any helper methods you would like to the class or use any existing class methods. You are also permitted to call any of the methods from the starter code if they would be helpful to your solution.

 

 

public class LinkedList{

 

   public class Node{ //inner class

       int data;

       Node next;

       Node prev;

 

       public Node(int data){

           this.data = data;

       }

   }

   

   public Node head;

   public Node tail;

 

   public LinkedList(){

       head = null;

       tail = null;

   }

   

   // YOUR CODE HERE

 

   public void addHead( int data ){

       Node n = new Node( data );

       if(head == null){ //empty list

           tail = n;

       }

       else{

           head.prev = n;

       }

       n.next = head;

       

       head = n;

   }

 

   public void addTail( int data ){

       Node n = new Node( data );

       if(tail == null){ //empty list

           head = n;

       }

       else{

           tail.next = n;

       }

       n.prev = tail;

       tail = n;

   }

   

   public Node getHead() {

       return head;

   }

   

   public Node getTail() {

       return tail;

   }

   

   public String toString() {

       String res = "";

       

       Node curr = head;

       

       if (curr != null) {

           res += curr.data;

           curr = curr.next;

       }

       

       while (curr != null) {

           res += ", " + curr.data;

           curr = curr.next;

       }

 

       return res;

   }

}