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"吗？

谢谢！

Answer 1

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

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

使前一个节点指向下一个节点，而不是 p 节点。
使下一个节点指向前一个节点，而不是当前节点。
删除当前节点。

因为 Python 是垃圾回收的，¹ 步骤 3 自动发生。²

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

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

与此同时，tmp = p.prev 后跟 p.prev = tmp 没有做任何有用的事情。³ 而且，不管它是什么 try 做，你几乎不需要像 Python 那样的 tmp；您可以仅使用 x, y = y, x 而不是 tmp = x; x = y; y = tmp.

来交换值

那么，您实际上想要的是：

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

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

_{2。您只需要删除对该对象的所有引用，它就会变成垃圾并自动清理。因此，您需要删除下一个和上一个节点对 p 的引用，您已经在这样做了。你需要让 p 消失，但你不需要 del p——它是一个局部变量；当您 return 退出该功能时，它就会消失。之后就看remove的调用者了；如果他们不保留对该节点的任何引用，则该节点是垃圾。}

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

python 中的双向链表使用 Del

Doubly Linked list in python Using Del

python

doubly-linked-list