How to create a remove method using recursion with an index in the parameter in Java?

Question

I'm having trouble on how to start this method. I am trying to create a remove method using recursions in my code. Basically I have a public and private remove method. The remove(int) method, which is public, should remove the element at the specified index in the list. I need to address the case in which the list is empty and/or the removed element is the first in the list. If the index parameter is invalid, an IndexOutOfBoundsException should be thrown. To allow for a recursive implementation, this method should address special cases and delegate to remove(int, int, Node) for recursion.

Here's the class:

public class SortedLinkedList<E extends Comparable<E>>
{
 private Node first;
 private int size;
 // ...
}

And here's the code:

public void remove(int index)
{
 if(index < 0 || index > size)
 {
 throw new IndexOutOfBoundsException();
 }
 remove(index++, 0, first);
 if (index == 0)
 {
 if(size == 1)
 {
 first = null;
 }
 else
 {
 first = first.next;
 }
 }
 size--;
}

And the private method:

private void remove(int index, int currentIndex, Node n)
{
 if(index == currentIndex)
 {
 remove(index, currentIndex, n.next);
 }
 remove(index, currentIndex, n.next.next);
}

With a private class:

private class Node
{
 private E data;
 private Node next;
 public Node(E data, Node next)
 {
 this.data = data;
 this.next = next;
 }
}

Answer 1

Returning void

Using two indexes

private void remove(int index, int current, Node n) {
 if (n == null || index <= 0 || (index == 1 && n.next == null) {
 throw new IndexOutOfBoundsException();
 }
 if (current == index - 1) {
 // Remove 'n.next'.
 n.next = n.next.next; 
 } else {
 remove(index, current + 1, n.next);
 }
}

Usage

public void remove(int index) {
 if (first == null || index < 0) {
 throw new IndexOutOfBoundsException();
 }
 if (index == 0) {
 // Remove 'first'.
 first = first.next;
 } else {
 remove(index, 0, first);
 }
 size--;
}

Using one index

Only one index is needed:

private void remove(int index, Node n) {
 if (n == null || index <= 0 || (index == 1 && n.next == null) {
 throw new IndexOutOfBoundsException();
 }
 if (index == 1) {
 // Remove 'n.next'.
 n.next = n.next.next; 
 } else {
 remove(index - 1, n.next);
 }
}

Usage

public void remove(int index) {
 if (first == null || index < 0) {
 throw new IndexOutOfBoundsException();
 }
 if (index == 0) {
 // Remove 'first'.
 first = first.next;
 } else {
 remove(index, first);
 }
 size--;
}

Returning Node

Even better is to return Node instead of void:

private Node remove(int index, Node n) {
 if (n == null || index < 0) {
 throw new IndexOutOfBoundsException();
 }
 if (index == 0) {
 // Remove 'n' and return the rest of the list.
 return n.next; 
 }
 // 'n' stays. Update the rest of the list and return it.
 n.next = remove(index - 1, n.next);
 return n;
}

Usage

public void remove(int index) {
 first = remove(index, first);
 size--;
}

• Adan Vivero: This would work, but I am required to use two indexes and I have the method as void.
• Kaue Silveira: I've added another two versions.