堆棧溢出錯誤迭代通過鏈表

Question

我不是100％確定爲什麼我在運行我的鏈表實現上的traverse（）方法時出現堆棧溢出錯誤。如果我註釋掉traverse（）方法，程序運行良好。

我通過遍歷使用size變量並在遍歷方法內部創建一個計數器變量來進行迭代檢查，但我仍然遇到堆棧溢出錯誤。

例如

@Override 
public void traverse() { 
    Node<T> data = this.head;  // In order traversal 
    int counter = 0; 
    while (counter < size) { 
     System.out.println(data.toString()); 
     data = data.getNextNode(); 
     counter++; 
    } 
} 

鏈表類

public class LinkedList<T extends Comparable<T>> implements List<T> { 

    private Node<T> head;   // First element of linked list 
    private Node<T> tail;   // Last element of linked list 
    private int size; 

    public LinkedList() { 
     this.size = 0; 
    } 

    /** 
    * TODO: Implement iterator and ForEach methods later on 
    * */ 
    @Override 
    public Iterator<T> iterator() { 
     return null; 
    } 

    @Override 
    public void forEach(Consumer<? super T> action) { 

    } 

    @Override 
    public Spliterator<T> spliterator() { 
     return null; 
    } 

    private class Node<T> { 
     private T data; 
     private Node<T> prevNode; 
     private Node<T> nextNode; 

     public Node(T data) { 
      this.data = data; 
     } 

     public Node(T data, Node<T> nextNode, Node<T> prevNode) { 
      this.data = data; 
      this.nextNode = nextNode; 
      this.prevNode = prevNode; 
     } 

     public T getData() { 
      return data; 
     } 

     public void setData(T data) { 
      this.data = data; 
     } 

     public Node<T> getPrevNode() { 
      return prevNode; 
     } 

     public void setPrevNode(Node<T> prevNode) { 
      this.prevNode = prevNode; 
     } 

     public Node<T> getNextNode() { 
      return nextNode; 
     } 

     public void setNextNode(Node<T> nextNode) { 
      this.nextNode = nextNode; 
     } 

     @Override 
     public String toString() { 
      return "Node{" + 
        "data=" + data + 
        ", prevNode=" + prevNode + 
        ", nextNode=" + nextNode + 
        '}'; 
     } 
    } 

    /** 
    * Add element to the start of the linked list 
    * */ 
    @Override 
    public void add(T data) { 
     // head is the first element. If inserted at the front of this list, this will constantly change 
     Node<T> node = new Node<>(data, this.head, null); 
     if (this.head != null) { 
      this.head.setPrevNode(node); 
     } 

     // Temporarily set new data as the head 
     this.head = node; 

     if (this.tail == null) { 
      this.tail = node;  // If tail is not set, make newly inserted node as tail; 
     } 
     incrementSize(); 
    } 

    @Override 
    public void remove(T data) { 
     // TODO 
     decrementSize(); 
    } 

    @Override 
    public void removeFirst() { 
     // TODO 
     decrementSize(); 
    } 

    @Override 
    public void traverse() { 
     Node<T> data = this.head;  // In order traversal 
     while (data != null) { 
      System.out.println(data.toString()); 
      data = data.getNextNode(); 
     } 
    } 

    @Override 
    public int size() { 
     return this.size; 
    } 

    /** 
    * =================================== 
    * Private methods here 
    * */ 
    private void decrementSize() { 
     this.size--; 
    } 

    private void incrementSize() { 
     this.size++; 
    } 

} 

List接口

public interface List<T> extends Iterable<T> { 
    void add(T data); 
    void remove(T data); 
    void removeFirst(); 
    void traverse(); 
    int size(); 
} 

主要方法

public class App { 
    public static void main(String[] args) { 
     List<Integer> linkedList = new LinkedList<>(); 
     linkedList.add(10); 
     linkedList.add(20); 
     linkedList.add(30); 

     linkedList.traverse(); // Error here 
     System.out.println(linkedList.size()); 

    } 
} 

下面是堆棧跟蹤

Exception in thread "main" java.lang.StackOverflowError 
at java.lang.AbstractStringBuilder.append(AbstractStringBuilder.java:449) 
at java.lang.StringBuilder.append(StringBuilder.java:136) 
at linkedlist.practice.LinkedList$Node.toString(LinkedList.java:79) 
at java.lang.String.valueOf(String.java:2994) 
at java.lang.StringBuilder.append(StringBuilder.java:131) 
at linkedlist.practice.LinkedList$Node.toString(LinkedList.java:79) 
at java.lang.String.valueOf(String.java:2994) 
at java.lang.StringBuilder.append(StringBuilder.java:131) 
at linkedlist.practice.LinkedList$Node.toString(LinkedList.java:79) 
at java.lang.String.valueOf(String.java:2994) 
at java.lang.StringBuilder.append(StringBuilder.java:131) 
at linkedlist.practice.LinkedList$Node.toString(LinkedList.java:79) 
at java.lang.String.valueOf(String.java:2994) 

謝謝你的幫助。在發現對toString（）方法的遞歸調用後，我將Node內部類中的toString（）方法重寫爲以下內容。 我想知道：在toString（）是空的檢查一個壞主意？由於它確實包含了一些額外的工作，因此反覆調用它有點昂貴。在控制檯上

@Override 
    public String toString() { 
     StringBuilder sb = new StringBuilder(); 
     sb.append("Node{ data="); 
     sb.append(data); 
     if (prevNode != null) { 
      sb.append(", prevNode=").append(prevNode.getData()); 
     } 
     if (nextNode != null) { 
      sb.append(", nextNode=").append(nextNode.getData()); 
     } 
     sb.append('}'); 
     return sb.toString(); 
    } 

登錄

Node{ data=30, nextNode=20} 
Node{ data=20, prevNode=30, nextNode=10} 
Node{ data=10, prevNode=20} 

Answer 1

你Node的toString()方法嘗試它的兩個鄰國添加到字符串。這意味着它的鄰居都會撥打toString()。然後這兩個人都嘗試並在他們的鄰居中撥打toString()，包括您開始使用的Node。這是一個無限遞歸。

爲了避免這種情況，請不要在節點的toString()方法中包含鄰居節點的字符串表示。

Answer 2

的問題是與您的節點的toString方法，因爲它使打印節點前後，遞歸：

@Override 
public String toString() { 
    return "Node{" + 
      "data=" + data + 
      ", prevNode=" + prevNode + 
      ", nextNode=" + nextNode + 
      '}'; 
} 

只要您撥打prevNode在字符串連接在一起，其toString將被調用。在它上面，初始節點將被要求再次打印，因爲它將是你的prevNode的nextNode，這將使代碼輸入一個無限遞歸，炸燬堆棧調用限制。