java - 如何使用 Java 参数中的索引使用递归创建删除方法？

Question

我在如何启动此方法时遇到困难。我正在尝试在代码中使用递归创建删除方法。基本上我有一个公共(public)和私有(private)的删除方法。 remove(int) 方法是公共(public)的，应该删除列表中指定索引处的元素。我需要解决列表为空和/或删除的元素是列表中的第一个元素的情况。如果索引参数无效，则应抛出 IndexOutOfBoundsException。为了允许递归实现，此方法应该解决特殊情况并委托(delegate)给remove(int, int, Node)进行递归。

这是类(class):

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

这是代码:

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--;
}

以及私有(private)方法:

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

私有(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

返回void

使用两个索引

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);
  }
}

用法

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--;
}

使用一个索引

只需要一个索引:

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);
  }
}

用法

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--;
}

返回节点

更好的是返回 Node 而不是 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;
}

用法

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