如何在自定义LinkedList实现中避免不必要的递归

Question

我试图在列表的末尾插入一个新节点，但它一直在递归。

我做错了什么？

public class Main {
    public static void main(String[] args) {
        run();
    }
    private static void run() {
        LinkedList list = new LinkedList();
        list.add("abc");
        list.add("def");
        list.add("ghi");
        list.add("jkl");
    }
}

add方法首先检查列表是否为空。

如果是，它将创建一个头部节点。

否则，它会尝试找到列表的末尾，并在那里插入新节点。

public class LinkedList<T> {
    Element head;
    Element terminator = new Element("TERMINATOR", true);
    public void add(T e) {
        Element node = new Element(e);
        if(head==null){
            head = node;
            head.setNext(terminator);
        }
        else {
            Element end = getEnd2();
            end.setNext(node);
        }
    }
    public Element getEnd2() {
        Element tmp;
        while((tmp = head.getNext())!=null){
            System.out.println("tmp:" + tmp.getValue());
        }
        return tmp;
    }
    public Element getEnd(){
        Element node = head;
        while(node!=null){
            System.out.println("node:" + node.getValue());
            node = head.getNext();
        }
        return node;
    }
    public Element getHead(){
        return head;
    }
}
public class Element<T>{
    T value;
    Element<T> next;
    boolean terminator;
    Element(T value){
        this.value = value;
    }
    Element(T value, boolean terminator){
        this.value = value;
        this.terminator = terminator;
    }
    public void setNext(Element<T> next) {
        this.next = next;
    }
    public Element getNext(){
        return next;
    }
    public T getValue(){
        return value;
    }
    public boolean isTerminator() {
        return terminator;
    }
    public void setTerminator(boolean terminator) {
        this.terminator = terminator;
    }
}

Answer 1

您的循环是无限的：

public Element getEnd(){
    Element node = head;
    while(node!=null){
        System.out.println("node:" + node.getValue());
        node = head.getNext(); // head.getNext() always returns the same value
    }
    return node;
}

如果您将其更改为node = node.getNext()，那么您的方法将只返回null。

如果您想要最后一个非空节点，请将其更改为：

public Element getEnd(){
    Element node = head;
    while(node.getNext()!=null){
        System.out.println("node:" + node.getValue());
        node = node.getNext();
    }
    return node;
}

getEnd2()也有同样的无限循环问题，但如果不使其与getEnd()完全相同，就无法解决它，因为您不能在同一语句中对node执行赋值和进行null检查（因为您只想在验证未将null赋值给node后进行赋值）。

Answer 2

它不是递归的，而是在行上的中缀循环：

while((tmp = head.getNext())!=null)

条件永远不会改变，所以如果head.getNext() != null，它将永远循环。