algorithm - 从链表中间删除时是否需要隔离节点？

Question

我们只是让前一个节点指向下一个节点。

prev.next = next;
return current;

或隔离节点

prev.next = next;
current.next = null;
return current;    

As 仍然能够遍历剩余的列表，如果我们有已删除的节点，则带有 next 指针。那么在双向链表中呢？

Answer 1

理论上

最重要的是，列表不变量在删除后保持不变。那是

• 没有圆圈，
• 每个节点都指向下一个节点（除非该节点是最后一个），
• 在双向链表中，每个节点都是其前任的后继节点（除非该节点是第一个节点），
• 在双向链表中，每个节点都是其后继节点的前任（除非该节点是最后一个）。

current.next = null列表不变量没有说明不属于列表的节点，因此在删除期间是否设置并不重要。

参与

保持原样current.next可能会妨碍自动垃圾收集，因为可能存在对不再需要的对象的引用。但这取决于具体情况。

在没有自动垃圾收集的语言中，存在拥有另一个对象的概念。拥有另一个对象的对象负责管理该另一个对象的资源（例如，另一个对象占用的内存）。当拥有对象被删除时，拥有者必须删除拥有的对象。current.next = null在这种情况下，如果在删除前不设置current，其他不应该删除的对象也会被删除。

Answer 2

没有真正的理由“隔离”节点。一旦你将前一个节点的下一个指针设置为下一个节点，你就“隔离”了当前节点，因为它无法从你的列表头中找到。假设您没有自动垃圾收集，那么您需要将其删除。

使用双向链表时，您还需要更新 current.next 的前一个指针。一旦你替换了所有指向你旧的当前节点的节点指针，你就完成了从列表中拼接它，它将不再被找到。

在这个例子中，我们从单链表和双链表中删除了“b”节点。括号中的箭头是需要更新的箭头。

   [a] (->) [b] -> [c]    would become    [a] -> [c]

[a] <(->) [b] (<-)> [c]   would become   [a] <-> [c]