在链接列表的某个索引处递归添加节点 [英] Recursively add a node at a certain index on Linked List

问题描述

我正在尝试以递归方式在指定的索引处添加列表节点.我的意思是说List类的addAtRec()在ListNode类中调用addAtRec()，该方法应该是递归的.

I'm trying to add a list node at a specified index recursively. By that I mean the List class addAtRec() calls addAtRec() in the ListNode class, that method is supposed to be recursive.

这就是我所做的:

列表:

public class List implements Cloneable {

private ListNode firstNode;
private ListNode lastNode;
private String name;
private int counter;

public List(){
    this("list");
}
public void addAtRec(Object obj, int k)
{
    if(firstNode != null)
        firstNode.addAtRec(obj, k, firstNode);
}
}

那当然只是相关部分...

That's of course only the relevant parts...

ListNode:

public class ListNode implements Cloneable {

Object data;
ListNode nextNode;
public ListNode(Object o){
    this(o,null);
}
public ListNode(Object o,ListNode node){
    data=o;
    nextNode=node;
}
public void addAtRec(Object obj, int k, ListNode current) throws ListIndexOutOfBoundsException {
    if(current.nextNode == null && k != 0)
        throw new ListIndexOutOfBoundsException(); //line 47
    if(k == 0)
    {
        ListNode l = new ListNode(obj);
        l.nextNode = current.nextNode;
        current.nextNode = l;
    }
    current = current.nextNode;
    addAtRec(obj, k, current); //line 55
    k--;
}

ListIndexOutOfBoundsException:

ListIndexOutOfBoundsException:

public class ListIndexOutOfBoundsException extends RuntimeException {

}

我的main()方法:

my main() method:

String s1 = "Objects";
    String s2 = "to";
    String s3 = "check";
    String s4 = "are";
    String s5 = "strings";
    List list = new List("My list");
    list.insertAtBack(s1);
    list.insertAtBack(s2);
    list.insertAtBack(s3);
    list.insertAtBack(s4);
    list.insertAtBack(s5);

    list.addAtRec(s3, 2);

和错误:

Exception in thread "main" ListIndexOutOfBoundsException
at ListNode.addAtRec(ListNode.java:47)
at ListNode.addAtRec(ListNode.java:55)
at ListNode.addAtRec(ListNode.java:55)
at ListNode.addAtRec(ListNode.java:55)
at ListNode.addAtRec(ListNode.java:55)
at List.addAtRec(List.java:158)

我做错了什么? 感谢您的时间和答复.

What did I do wrong? Thanks for your time and answers.

推荐答案

您的递归方法中有两个错误:

You have two errors in your recursive method:

1. 在调用addAtRec(obj, k, current);之前，应将k减小1，因此最好在此行之前调用k--.

1. Before calling addAtRec(obj, k, current); you should decrease k by 1, so it would be better to call k-- before this line.

一旦达到基本情况(当k == 0时)并执行了添加新节点的逻辑，则您的递归方法必须停止，可能使用简单的return;语句.在这种情况下，您不会停止它，因此每次都将调用它，直到到达列表的末尾.

Once you have reached the base case (when k == 0)and executed the logic to add the new node, your recursive method must stop, probably with a simple return; statement. In this case, you're not stopping it so you will call it every time until get to the end of your list.

根据这两个建议，您的代码应如下所示:

Based on these 2 advices, your code should look like:

public void addAtRec(Object obj, int k, ListNode current)
    throws ListIndexOutOfBoundsException {
    //always use braces even for single line block of code
    if(current.nextNode == null && k != 0) {
        throw new ListIndexOutOfBoundsException();
    }
    if(k == 0) {
        ListNode l = new ListNode(obj);
        l.nextNode = current.nextNode;
        current.nextNode = l;
        //stopping the recursion
        return;
    }
    current = current.nextNode;
    //decrease k by 1 before calling your method recursively
    k--;
    addAtRec(obj, k, current);
}

这不是主要问题的一部分，但是IMO您在列表中添加节点的方法应该属于List类，而不属于ListNode.请记住，保存节点并决定如何绑定它们的数据结构将是List，而不是节点本身.

This is not part of the main problem, but IMO your methods to add nodes in the list should belong to the List class and not to theListNode. Remember that the data structure that holds the nodes and decide how to tie them will be the List, not the nodes by themselves.

这篇关于在链接列表的某个索引处递归添加节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！