java - 遍历链表时出现堆栈溢出错误

Question

我不能 100% 确定为什么在链表实现上运行 traverse() 方法时出现堆栈溢出错误。如果我注释掉 traverse() 方法，程序就可以正常运行。

我通过迭代使用大小变量并在遍历方法内创建计数器变量进行了双重检查，但仍然收到堆栈溢出错误。

例如

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

}

列表界面

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() 方法中包含相邻节点的字符串表示形式。