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}
toStringat line 79 of LinkedList.java - this is the hint for finding the problem.