Python Doubly Linked List Node Removal

Question

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.

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

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.

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.

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?

Jared Jared · Accepted Answer · 2015-05-03T02:31:05

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 Doubly Linked List Node Removal

1 Answers