提问者:小点点

Python双链表节点移除


我在Python中创建了一个基本的双向链表类,它有三个方法:append、删除和show。我完全理解append方法,也完全理解show方法。然而,我对我的删除方法的工作方式有点困惑。

这是我的两个类-我的节点类和我的双链表类:

class ListNode:
    def __init__(self, data, prev, next):
        self.data = data
        self.prev = prev
        self.next = next

class DoubleList(object):
    head = None
    tail = None

    def append(self, data):
        new_node = ListNode(data, None, None)
        if self.head is None:
            self.head = self.tail = new_node
        else:
            new_node.prev = self.tail
            new_node.next = None
            self.tail.next = new_node
            self.tail = new_node

    def remove(self, node_value):
        current_node = self.head
        while current_node is not None:
            if current_node.data == node_value:
                if current_node.prev is not None:                   
                    current_node.prev.next = current_node.next
                    current_node.next.prev = current_node.prev
                else:
                    self.head = current_node.next
                    current_node.next.prev = None
            current_node = current_node.next
    def show(self):

        print("Show list data:")
        current_node = self.head
        while current_node is not None:
            print(current_node.prev.data if hasattr(current_node.prev, "data") else None,)
            print(current_node.data)
            print(current_node.next.data if hasattr(current_node.next, "data") else None)
            current_node = current_node.next
        print("*"*50)

因此,当我使用DoubleList类中的删除方法时,该元素会按预期从列表中删除。然而,Node实例也不见了,我通过在删除两个节点之前和之后使用这段代码验证了这一点。

import gc
for obj in gc.get_objects():
    if isinstance(obj, ListNode):
        print(obj.data)

现在,我假设我只是不明白我的删除方法到底在做什么。

我的理解是这样的:

我认为该节点仍然存在,因为删除方法只重新分配了前一个节点的next属性和后一个节点的前一个属性。但是,当前节点没有被更改,它仍然保留对列表中旁边节点的引用。

显然,我的理解是错误的,我想知道为什么。

为什么我从链表中删除的节点实例会消失?


共1个答案

匿名用户

当节点持有下一个和上一个的引用时,它没有任何指向它的东西,并且像Python中的任何对象一样被垃圾收集。您必须使用gc来检查它是否因为没有引用者而消失了!