2

I am not 100% sure why I am getting a stack overflow error on running the traverse() method on my linked list implementation. If i comment out the traverse() method, the program runs fine.

I double checked by iterating through using the size variable and creating a counter variable inside the traverse method, but I still get a stack overflow error.

e.g.

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

Linked List class

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 interface

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

Main method

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());

    }
}

Below is the stack trace

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)

Thank you for the help. After discovering the recursive call to the toString() method, I rewrote my toString() method in the Node inner class to the following. I am wondering: are null checks in toString() a bad idea? Since it does contain an extra bit of work, making repeated calls to it a bit pricey.

@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();
    }

Log on console

Node{ data=30, nextNode=20}
Node{ data=20, prevNode=30, nextNode=10}
Node{ data=10, prevNode=20}
3
  • 2
    Please post the stack trace of your exception. Commented Mar 1, 2017 at 12:33
  • I just added the stack trace. Commented Mar 1, 2017 at 12:35
  • Note (since missing in any answer): the stack trace is repeatedly showing the call to toString at line 79 of LinkedList.java - this is the hint for finding the problem. Commented Mar 1, 2017 at 12:43

2 Answers 2

7

Your Node's toString() method tries to add both its neighbours to a string. That means it calls toString() on both its neighbours. Then both of those try and call toString() on both their neighbours, including the Node you started with. This is an infinite recursion.

To avoid it, don't include neighbouring nodes' string representations in your node's toString() method.

Sign up to request clarification or add additional context in comments.

4 Comments

I dont know why I didn't see this before. Thank you very much for pointing this out!
@khlewood I rewrote my toString() method. Was just wondering if you think null checks in toString() is a bad idea. I will post my code in the post above.
@J.Lee If that's the behaviour you want in your toString(), that looks like a reasonable way to do it. The null checks are necessary given the structure of your linked list.
@khlewood got it. Thank you so much for your helpful response.
5

The issue is with your Node's toString method, as it keeps printing the nodes back and forth, recursively:

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

whenever you call the prevNode to be concatenated in the String, its toStringwill be called. On it, the initial node will be asked to print again, because it will be the nextNode of your prevNode, which will have the code enter an infinite recursion, blowing up the Stack call limit.

1 Comment

Thank you for your response. Dont know why i didnt see this before ... Appreciate it!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.