Question

Write the methods that insert and remove an element at the kth position in Java using recursion (NOT iteration) (Hint for the remove method: we have to recursive position -1 times, and each time we do the recursion, we have to create a method to move the head to the right)

public void insertRecursive(int position, int data)
{
   //enter code here
}

public int removeAtRecursive(int position)
{
   //enter code here
}

Here is the given class for the Node:

public class Node {
  private int data;
  private Node next;

  public Node(int data)
  {
    this.data = data;
    this.next = null;
  }
  public void setNext(Node next)
  {
    this.next = next;
  }
  public Node getNext()
  {
    return next;
  }

  public void setData(int data)
  {
    this.data = data;
  }

  public int getData()
  {
    return data;
  }
}

Answer 1

//Java program

class Node {
   private int data;
   private Node next;

   public Node(int data)
   {
   this.data = data;
   this.next = null;
   }
   public void setNext(Node next)
   {
   this.next = next;
   }
   public Node getNext()
   {
   return next;
   }

   public void setData(int data)
   {
   this.data = data;
   }

   public int getData()
   {
   return data;
   }
}

class List{
   private Node head;
     
   public List(){
       head=null;
   }
   public void insertRecursive(int position, int data)
   {
   Node node = new Node(data);
  
   head = insert(head,position-1,node);
   }

   private Node insert(Node head2, int position, Node node) {
       if(head2==null)return node;
       if(position==1) {
           node.setNext(head2);
           return node;
       }
       head2.setNext(insert(head2.getNext(),position-1,node));
       return head2;
   }
   public void removeAtRecursive(int position)
   {
   head = remove(head,position);
   }
   private Node remove(Node start, int position) {
       if (position < 1) return start;
          
           // If linked list is empty
           if (start == null)
           return null;
          
           // Base case (start needs to be deleted)
           if (position == 1)
           {
           Node res = start.getNext();
           return res;
           }
          
           start.setNext(remove(start.getNext(), position-1));
           return start;
      
   }
}