python中使用D的双链表

Question

我在分析一个删除节点的双链表函数。但是我有点困惑。你知道吗

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

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

谢谢你！你知道吗

Answer 1

首先，如果这是整个函数，那么它是错误的，这可能是您理解它有困难的部分原因。你知道吗

要从双链接列表中删除节点，需要执行三项操作：

1. 使上一个节点指向下一个节点的前面，而不是p节点。你知道吗
2. 使下一个节点指向上一个节点，而不是当前节点。你知道吗
3. 删除当前节点。你知道吗

因为Python是垃圾收集的，¹步骤3会自动执行。²

步骤1由p.prev.next = p.next处理。你知道吗

但第二步不会发生在任何地方。p.next.prev仍然指向p，而不是p.prev。这意味着如果你向前走，列表p将不在其中，但是如果你向后走，它将成为。所以p实际上并没有被删除。你知道吗

同时，tmp = p.prev后跟p.prev = tmp没有任何用处。³而且，无论试图做什么，您几乎不需要像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。您可能正在使用的Python引用解释器CPython通过自动引用计数执行垃圾收集，并偶尔运行一个循环中断程序。这是否算作“真正的”垃圾收集是一个不错的圣战论据，但在这里并不重要。}

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

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