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

我想插入一个新的节点在列表的末尾，但它不断递归。如何在我的自定义LinkedList实现中避免不必要的递归？

我在做什么错？

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

}

来源

2014-10-16 Wallis McAllistair

你是什么意思继续递归？代码的结果是什么？期望的结果是什么？ – 2014-10-16 15:43:33

你的循环是无限的：

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和同一语句中进行空检查（因为您只是在确认您没有将空值分配给node后才进行分配）。

来源

2014-10-16 15:44:12 Eran

它不递归，它是infitie循环就行了：

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

的情况不会改变，因此，如果head.getNext() != null，这将永远循环下去。

来源

2014-10-16 15:44:24 clcto

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

回答

相关问题