如何在我的自定義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實現中避免不必要的遞歸？

回答

相關問題