解码 LinkedList 实现

Question

为了理解实现、操作等，我从JDK复制了LinkedListclass，并以非泛型（仅限字符串）方式进行了修改。您可以找到实际代码 here。与问题相关的是
addLast()

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

节点内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+ "]";
    }
}

link最后一个()

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");
}

当我执行此 class 时出现计算器错误，

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

输出

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.WhosebugError
    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)

然后最后 3 行不断重复。 我无法弄清楚是什么导致了这种情况。

更新 - 基于收到的回复
所以，如果理解正确的话，

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

在这个阶段 "Node B" 仅创建了单面 link(prev)，其中调用了 toString()。只有在那之后 link(next) 被 linked。而这个 double link 是无限递归的原因，在下一次插入时。

也许这就是为什么toString() 方法没有在它的两个superclasses AbstractSequentialList、AbstractList 和AbstractCollection 中实现的原因。该实现提取一个 Iterator，它迭代以打印 colletcion。

那么，为什么它只在第 3 次插入时发生。两次插入不会导致此问题。

Answer 1

问题是您的 toString 方法，它在尝试打印 prev 和 next 节点时递归调用自身。

如果当前打印的Node的next不为空，则调用next.toString()，当打印那个Node的prev时, 原来的Node的toString()又被调用了，所以递归没完没了

可能的解决方案：

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

关于评论：

添加第一个节点后，列表如下所示：

prev             next
null <- Node1 -> null

first 和 last 都引用 Node1

在 toString 中没有无限递归的风险。

添加第二个节点后，列表如下所示：

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

first 指的是 Node1，last 指的是 Node2

如您所见，Node1 和 Node2 相互引用（Node1 是 Node2 的 prev，Node2 是 Node1 的 next）。因此，在第二次插入后尝试使用原始 toString() 方法打印其中一个节点将导致无限递归。

但是，由于您在执行 l.next = newNode; 行之前打印了新节点，所以您不会在第二次插入时得到无限递归，只有在第三次插入时才会得到。如果将System.out.println("\tCreatd new node as:" + newNode);移动到linkLast的末尾，第二次插入将导致无限递归。

解码 LinkedList 实现

Decoding LinkedList implementation

java

stack-overflow

linked-list