Python双重链接列表节点删除

I created a basic doubly linked list class in Python, and it has three methods: append, remove, and show. I fully understand the append method, and I fully understand the show method. However, I am mildly confused about the way my remove method works.

我在Python中创建了一个基本的双向链表类,它有三个方法:append,remove和show。我完全理解append方法,并且我完全理解show方法。但是,我对删除方法的工作方式感到有些困惑。

These are my two classes - my Node class and my Doubly Linked List class:

这是我的两个类 - 我的Node类和我的Doubly Linked List类:

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)

So, when I use my remove method that is part of my DoubleList class, the element is removed from the list as expected. However, the Node instance is also gone, and I verified this by using this bit of code before and after removing two nodes.

因此,当我使用我的DoubleList类的一部分remove方法时,该元素将按预期从列表中删除。但是,Node实例也消失了,我在删除两个节点之前和之后使用这段代码验证了这一点。

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

Now, I assume I simply don't understand exactly what my remove method is doing.

现在,我假设我根本不明白我的删除方法正在做什么。

My understanding is this:

我的理解是这样的:

I thought that the node would still exist, as the remove method only reassigns the previous nodes next attribute and the following nodes previous attribute. However, the current node is not altered, and it still holds references to the nodes that were next to it in the list.

我认为节点仍然存在,因为remove方法只重新分配先前节点的下一个属性和以下节点的前一个属性。但是,当前节点不会更改,它仍然保留对列表中旁边的节点的引用。

Obviously, my understanding is wrong, and I want to know why.

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

Why does the instance of a Node I removed from my linked list disappear?

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

1 个解决方案

#1

While the node holds references to the next and previous, it does not have anything pointing to it and is garbage collected like any object in Python. You had to use gc just to check that it was gone for the very reason it had no referrers!

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