python - python中使用Del的双向链表

Question

我正在分析一个删除节点的双向链表函数。但是我有点困惑。

def remove( self, p ) :
        tmp = p.prev
        p.prev.next = p.next
        p.prev = tmp

为什么会有 tmp = p.prev 和 p.prev = tmp。这些额外行的目的是什么？最后，为什么没有用“del”删除节点？代码末尾不应该是“del p”吗？

谢谢！

标签： pythondoubly-linked-list

Answer 1

首先，如果这是整个函数，那就错了，这可能是您无法理解它的部分原因。

要从双向链表中删除一个节点，你需要做三件事：

1. 使前一个节点指向下一个节点，而不是该p节点。
2. 使下一个节点指向前一个节点，而不是当前节点。
3. 删除当前节点。

因为 Python 是垃圾收集的，所以¹步骤 3 会自动发生。²

步骤 1 由 处理p.prev.next = p.next。

但是第 2 步不会在任何地方发生。p.next.prev仍然指向p，而不是p.prev。这意味着，如果您将列表向前移动，p则不会成为其中的一部分 - 但如果您向后移动，它将成为. 所以p实际上并没有被删除。

同时，tmp = p.prev其次p.prev = tmp并没有做任何有用的事情。³而且，无论它试图做什么，在 Python 中你几乎不需要tmp这样；x, y = y, x你可以用 just而不是交换值tmp = x; x = y; y = tmp。

---

所以，你真正想要的是：

def remove(self, p):
    p.prev.next = p.next
    p.next.prev = p.prev

---

_{1. CPython，您可能正在使用的 Python 引用解释器，通过自动引用计数进行垃圾收集，并带有偶尔运行的循环中断器。这是否算作“真正的”垃圾收集是一个很好的圣战论点，但这并不重要。}

_{2. 你只需要删除对象的所有引用，它就会变成垃圾并被自动清理。因此，您需要从下一个和上一个节点中删除对 的引用p，您已经在这样做了。你需要放手p，但你不需要del p——它是一个局部变量；当您从函数返回时，它会消失。之后，由 ; 的调用者决定remove。如果他们不保留对节点的任何引用，则该节点是垃圾。}

_{3.如果我们临时分配一个不同的值并希望在函数结束时恢复它，它可以做一些有用的事情。p.prev但这并没有发生在这里，而且我认为编写此代码的人没有这样的意图。我认为他们试图进行某种交换。}