2

我们正在尝试编写一种方法来从 LUT 的链表实现中删除具有特定键的节点。

我写的代码总结：

public void delete (String k) {

    Node currNode = listHead;
    Node prevNode = listHead;

    Key key = new Key (k);

    while (!currNode.key.equals(k) && currNode != null){
        prevNode = currNode;
        currNode = currNode.next;
    }

    if (currNode == listHead) {
      listHead = listHead.next;
    } else {
      prevNode.next = currNode.next;
    }
}

我的朋友写了基本相同的东西，但没有使用以前的节点指针，而是写在他的最后一行：

currNode = currNode.next //detach point, override

这两个是等价的吗？我想我对 Java 内存管理感到困惑。
如果您已经在listHead其他地方创建了节点，并且您编写：

Node currNode = listHead;

currNode只是存储对存储位置的内存位置的引用listHead，对吗？因此，当您这样做时，在 while 循环中，您要做currNode = currNode.next的是转到引用的内存位置currNode并查看变量 next 并将对该内存位置的引用存储在currNode? 所以基本上更新currNode指向的地方。这意味着我朋友的代码是错误的，对吧？因为他的代码同样意味着：“currNode用”的内存位置更新当前的引用currNode.next。

有人介意帮我除雾吗？

4

3 回答 3

3

您的朋友不可能是对的，因为必须更改 a 的.next字段才能从列表Node中删除 a 。Node

正如我想象N的那样，要从列表中删除节点，您需要将节点的.next字段设置N-1为引用节点N+1。你朋友的方法不可能这样做，因为它不会改变任何节点的.next字段。

至于内存，一旦N-1的.next字段指的是N+1，则N列表不再保持活动状态。它是否有资格进行垃圾收集取决于程序中的其他任何内容是否引用了它。但现在这份名单已经洗白了。

于 2012-05-15T21:27:25.570 回答
2

您已经得到了查询的正确答案，但是您的代码中有一些错误无法放入评论中。

NullPointerException

您的while循环条件是向后的。它应该是

while (currNode != null && !currNode.key.equals(k)) { ... }

避免NullPointerException当您到达列表末尾或列表没有节点开始时。

未找到值

该方法不处理k列表中不包含的情况。您需要在 while 循环之后进行currNode检查。null

if (currNode != null) {
    if (currNode == listHead)
        listHead = listHead.next;
    else
        prevNode.next = currNode.next;
}
于 2012-05-15T21:50:17.817 回答
1

您的分析是正确的——您朋友的代码实际上不会从列表中删除该节点。

我认为使用调试器单步执行您的代码可能有助于消除迷雾。如果您还没有使用集成开发环境 (IDE)，我建议您使用 IntelliJ IDEA、Eclipse 或 Netbeans——它们都包含调试器。

于 2012-05-15T21:30:28.207 回答