递归地将节点添加到特定索引处的链表

Question

我正在编写一个递归函数，它将通过递归迭代到索引然后添加项目来将项目添加到给定索引的列表中。该函数应接受 2 个参数（字符串值和整数索引）并检查索引是否有效。到目前为止，这是我所拥有的，它不检查有效性并且仅在仅传入字符串值时才有效。

测试台（主要）

public class TestBench {

public static void main(String[] args) {
    RecLinkedList list = new RecLinkedList();
    list.add("A");
    list.add("B");
    list.add("D");
    list.add("C", 2);
    list.add("E", 4);
    list.add("G", 6); //this should be invalid

    System.out.println( list );
    System.out.println( list.remove( 1 ).getValue() );
    System.out.println( list.remove("D").getValue() );
    System.out.println( list.remove("G").getValue() );
    System.out.println( list.size() );
    System.out.println( list );
}

链表Class

public class RecLinkedList {
private Node first;

public RecLinkedList(){
    first = null;
}
public boolean isEmpty() {
    return first == null;
}
public void add( String s){
    first = add( s, first);
}
private Node add( String s, Node list){
    if( list == null ){
        return new Node(s);
    }else{
        list.setNext( add( s, list.getNext() ) );
    return list;
    }
}
public String toString() {
    return helperString(first);
}
private String helperString(Node list) {
    if (list.getNext() != null) {
        return list.getValue() + "," + helperString(list.getNext());
    }
    else {
        return (String) list.getValue();   
    }
}

我需要帮助的是我是否需要制作另一个接受两个参数（字符串和整数值）的添加函数，或者我是否可以修改我拥有的？另外，至于检查索引是否有效，我不太确定如何检查。

Answer 1

最好编写另一个带有参数 String 和 int 的添加方法，因为与其他添加函数相比，它的行为不同。如果您查看 Java API for many 类，方法名称已重载。所以这是一个很好的做法。

要确定索引是否有效，您首先需要声明一个字段，该字段保存您的链表的当前大小。每次添加或删除元素时，此计数器都会更新。当您调用新的 add 方法时，您首先会检查要插入新元素的索引是小于零还是大于链表的大小。如果它低于零，那么这不是一个有效的索引。如果它大于列表的大小，那么这没有意义，因此您可以拒绝它或更可疑地将元素添加到列表的末尾。

Answer 2

关于有效索引，您可以添加一个计算现有节点的大小字段。

public class RecLinkedList {
    private int size = 0;

    //...
    private Node add( String s, Node list){
        if( list == null ){
            this.size += 1;
            return new Node(s);
        }else{
            list.setNext( add( s, list.getNext() ) );
            return list;
        }
    }
    //...
}

然后在使用方法 public void add(String value, int index) 添加新节点时，您可以检查索引是大于当前大小还是小于零。

要在正确的位置添加节点，只需计算您已经访问过的节点的数量，当到达正确的位置时添加节点。

递归地将节点添加到特定索引处的链表

Recursively Add Node to Linked List at Specific Index

java

recursion

linked-list

nodes