Java递归删除链表中的元素

Question

在这个任务中，我需要迭代和递归地遍历一个大小为1,000,000的链表。我已经完成了迭代部分，但对于递归部分我感到困惑。我已经理解了概念，但我告诉我的老师我不能用递归方式完成它，因为我肯定会遇到堆栈溢出错误。他说我不应该遇到那个问题，但我完全被卡住了。如果有任何提示，那将是很好的，因为我不知道我做错了什么。

public static void main(String[] args) {

    System.out.println("Please enter how many random numbers you want to generate: ");
    Scanner prompt = new Scanner(System.in);
    int amount = prompt.nextInt();

    Random rnd = new Random();
    System.out.println("Creating list...");
    for (int i = 0; i < amount; i++) {
        randomList.add(rnd.nextInt(100));
    }
    System.out.println("Going through list...");
    iterateNumbers();

    long startTimeRec = System.nanoTime();
    recursiveNumbers(randomList);
    long elapsedTimeRec = System.nanoTime() - startTimeRec;
    double seconds = (double)elapsedTimeRec / 1000000000.0;
    System.out.println("Recursively, the function took " + seconds + " seconds.");

    prompt.close();

}
//create the linked list
public static LinkedList<Integer> randomList = new LinkedList<Integer>();

private static void iterateNumbers() {

    long startTime = System.nanoTime();
    for (int i = 0; i < randomList.size(); i++) {
        randomList.remove();
    }
    long elapsedTime = System.nanoTime() - startTime;
    double seconds = (double)elapsedTime / 1000000000.0;
    System.out.println("Iteratively, the function took " + seconds + " seconds.");
}

private static void recursiveNumbers(LinkedList<Integer> current) {     

    if (current.isEmpty() == true) {
        return;
    } else {
        current.removeFirst();
        recursiveNumbers(current);
    }
}

}

- Arkant0r

---

你用这段代码得到了什么？你具体的问题是什么？ - innoSPG

Answer 1

当你运行程序时，很容易理解。堆栈区域不足，导致出现错误。

您可以尝试增加堆栈空间。

使用以下参数运行程序:

-Xss1280m

这意味着创建1280MB的堆栈，您将看到以下结果:

---

- D0n9X1n

---

我该如何使用这些参数运行我的程序？是否可以在我的代码中添加语句，以便自动为运行程序的任何人分配更大的堆栈区域？ - Arkant0r

你可以先使用代码javac Main.java编译Java文件，然后使用代码java -Xss1280m Main运行它。我编写了一个shell脚本来运行程序，而不是直接运行它。这是我的脚本：java -Xss1280m Main，我只需使用sh run.sh运行它，它就能正常工作。如果你在Windows系统上，也可以编写.bat文件。 - D0n9X1n

我不确定是否有任何方法可以做到这一点。但是我目前看到的是一个带有配置文件的脚本。 - D0n9X1n

好的，非常感谢！我觉得现在我有可以处理的东西了！ - Arkant0r

@Arkant0r：我认为从Java源代码中指定堆栈大小是不可能的，因为这将会存在安全风险。 - Siyuan Ren

Answer 2

在迭代版本中，您应该传入要删除的索引。

randomList.remove(i);

在调用递归方法之前，您是否应该重新填充链接列表？

    for (int i = 0; i < amount; i++) {
    randomList.add(rnd.nextInt(100));
}

我不太确定Java中链表的实现方式。尝试查找了一下，是否有一个isEmpty()方法？或者你可以尝试：

if(current.size() < 1) 
    return;

- GermaineJason

---

你说得对，我忘记重新填充列表了！让我尝试一下，然后再回复你。 - Arkant0r

我重新填充了列表并在删除语句中传递了索引，但是当我创建一个包含1,000,000个整数的链表然后使用递归函数时，仍然会出现stackoverflowerror。 - Arkant0r