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

标签 algorithm data-structures singly-linked-list doubly-linked-list

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

prev.next = next;
return current;

或者隔离节点

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

如果我们有删除的节点,则仍然可以遍历剩余的列表,并带有下一个指针。 在双向链表中怎么样?

最佳答案

理论上

最重要的是,列表不变量在删除后保持不变。也就是

  • 没有圈子,
  • 每个节点指向下一个节点(除非该节点是最后一个),
  • 在双向链表中,每个节点都是其前任节点的后继节点(除非该节点是第一个节点),
  • 在双向链表中,每个节点都是其后继节点的前导节点(除非该节点是最后一个节点)。

列表不变量不会说明不属于列表的节点,因此在删除过程中是否设置 current.next = null 并不重要。

实践中

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

在没有自动垃圾回收的语言中,存在拥有另一个对象的概念。 拥有另一个对象的对象负责管理另一个对象的资源(例如,另一个对象占用的内存)。当拥有对象被删除时,拥有必须删除拥有的对象。在这种情况下,如果在删除 current 之前没有设置 current.next = null,则其他不应删除的对象将被删除。

关于algorithm - 从链表中间删除时是否需要隔离节点?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19475319/

相关文章:

c++ - 如何处理成员函数中的递归?

ios - 自动完成算法

algorithm - 维特比算法中的这一行具体是做什么的?

algorithm - 给定 N 个事件中每一个事件的概率,如何确定 0 到 N 个事件发生的概率?

在手中找到街道和同类的算法

data-structures - 关于多维数组

java - Java中的Trie实现

ajax - 基于 DOM 的数据存储,最佳选择/性能?

c - 将文本文件读取到链表数组时出现段错误

c - 如何将目录名称正确存储到链表中?