Decoding LinkedList implementation

Question

Just to understand the implementation, operation etc., I copied LinkedList class from JDK and modified in non-generic(String only) way. You can find the actual code here. Relevant to the question, here's
addLast()

public void addLast(String e){
    System.out.println("Invoked:addLast()");
    linkLast(e);
}

Node inner class

private static class Node {
     String item;
     Node next;
     Node prev;
     Node(Node prev, String element, Node next) {
         this.item = element;
         this.next = next;
         this.prev = prev;
    }
    @Override   public String toString() {
        return "Node [item=" + item + ", next=" + next + ", prev=" + prev+ "]";
    }
}

linkLast()

void linkLast(String e) {
    System.out.println("Invoked:linkLast(" + e + ")");
    final Node l = last;
    final Node newNode = new Node(l, e, null);
    System.out.println("\tCreatd new node as:" + newNode);
    last = newNode;
    System.out.println("\tSetting this node as last");
    if (l == null){
        // Applicable for 1st node. Last & First point to newNode
        first = newNode;
        System.out.println("\tLast was null, setting this node as first.");
    }          
    else{
        // Set newNode as next of previous Last.
        System.out.println("\tLast was not null, seting this node as next node of previous Last.");
        l.next = newNode;
    }
    size++;
    //System.out.println("Size of list:" + size);
    modCount++;
    System.out.println("\tMod Count:" + modCount + "\n");
}

I get a stackoverflow error, when I execute this class as,

public static void main(String args[]){
    LinkedListDemo obj = new LinkedListDemo();
    obj.add("B");
    obj.addFirst("A");
    obj.addLast("C");
}

Output

Invoked:add(B)
Invoked:linkLast(B)
    Creatd new node as:Node [item=B, next=null, prev=null]
    Setting this node as last   Last was null, setting this node as first.
    Mod Count:1
Invoked:addFirst()
Invoked:linkFirst(A)
    Creatd new node asNode [item=A, next=Node [item=B, next=null, prev=null], prev=null]
    Seting this node as first
    First was not null, seting this node as next node of previous First.
    Mod Count:2
Invoked:addLast()
Invoked:linkLast(C)
Exception in thread "main" java.lang.StackOverflowError
    at java.lang.String.getChars(String.java:826)
    at java.lang.AbstractStringBuilder.append(AbstractStringBuilder.java:416)at java.lang.StringBuilder.append(StringBuilder.java:132)
    at java.lang.StringBuilder.<init>(StringBuilder.java:110)
    at collections.LinkedListDemo$Node.toString(LinkedListDemo.java:570)
    at java.lang.String.valueOf(String.java:2847)
    at java.lang.StringBuilder.append(StringBuilder.java:128)
    at collections.LinkedListDemo$Node.toString(LinkedListDemo.java:570)

And then last 3 lines keep repeating. I am not able to figure out what is causing such a scenario.

UPDATE - based on replies received
So, if the understanding is correct,

Invoked:add(A)
Invoked:linkLast(A)
    Creatd new node as:Node [item=A, next=null, prev=null]
    Setting this node as last
    Last was null, setting this node as first.
    Mod Count:1
Invoked:add(B)
Invoked:linkLast(B)
    Creatd new node as:Node [item=B, next=null, prev=Node [item=A, next=null, prev=null]]
    Setting this node as last
    Last was not null, seting this node as next node of previous Last.
    Mod Count:2

At, this stage "Node B" has been created with one sided link(prev) only, where toString() is invoked. Only, after that other side link(next) is linked. And this double link is the cause of infinite-recursion, at the time of next insertion.

Maybe this is the reason why toString() method is not implemented in neither of it's two superclasses AbstractSequentialList, AbstractList but in AbstractCollection. The implementation extracts an Iterator, which iterates to print the colletcion.

So, why does it happen only on the 3rd insertion. Two insertions do not cause this problem.

Answer 1

The problem is your toString method, which calls itself recursively when it attempts to print the prev and next Nodes.

If next of the current printed Node is not null, next.toString() will be called, and when the prev of that Node is printed, toString() of the original Node is called again, so there is no end to the recursion.

Possible solution :

@Override
public String toString() 
{
    return "Node [item=" + item + ", next=" + (next==null?"null":next.item) + ", prev=" + (prev==null?"null":prev.item) + "]";
}

Regarding the comments :

After adding the first Node, the list looks like this :

prev             next
null <- Node1 -> null

first and last both refer to Node1

There's no risk of infinite recursion in toString.

After adding the second Node, the list looks like this :

null <- Node1 -> <- Node2 -> null

first refers to Node1 and last refers to Node2

As you can see, Node1 and Node2 refer to each other (Node1 is Node2's prev and Node2 is Node1's next). Therefore, trying to print one of those nodes with your original toString() method after the second insertion will lead to infinite recursion.

However, since you print the new node before the line l.next = newNode; is executed, you don't get an infinite recursion in the second insertion, only in the third. If you move System.out.println("\tCreatd new node as:" + newNode); to the end of linkLast, the second insertion will cause the infinite recursion.