3

[Python 3.8]

When removing a node in a linked list, can the next node simply be changed?

Here, we "delete" Node 1, simply by changing the pointer.

Coming from a C++ world, this makes me a little nervous. Will the memory for Node 1 be reclaimed automatically, since there are no references thereto? What exactly happens to Node 1?

Before

[Sentinel] -> [Node 0] -> [Node 1] -> [Node 2] -> [Node 3] -> None

After

[Sentinel] -> [Node 0] -┐ [Node 1] -┬-> [Node 2] -> [Node 3] -> None
                        └-----------┘

Is this legit?

Minimal, complete, verifiable example

def delete(self, val):
    n = self.sentinel
    while n.next != None:
        if n.next.data == val:
            n.next = n.next.next  # reassign pointer - no del, free, delete, or the like.
            return
        n = n.next
kmiklas
  • 13,085
  • 22
  • 67
  • 103
  • 4
    Yes, Python features a garbage collector that will eventually find that Node 1 is not used, and will release its memory. Nothing to be nervous about... unless you [disable the garbage collector](https://docs.python.org/3/library/gc.html#gc.disable). – Amadan Jan 30 '20 at 04:18
  • 2
    Also [this](https://stackoverflow.com/questions/18068499/will-python-automatically-garbage-collect-doubly-linked-list), [this](https://stackoverflow.com/questions/4484167/python-garbage-collector-documentation?noredirect=1&lq=1), and [this](https://stackoverflow.com/questions/1035489/python-garbage-collection) – metatoaster Jan 30 '20 at 04:20

1 Answers1

8

In CPython, the primary form of garbage collection is via reference counting. When an object's reference count falls to 0, the object is immediately and automatically reclaimed.

Other implementations of Python typically don't use reference counting, but garbage is still automatically reclaimed - eventually. You lose only the "immediately" part then.

Which is a good thing, because no matter how hard you look, you'll never find anything in Python that allows you to force memory to be freed. In particular, the del statement

    del object

does not "delete" an object. It merely removes the current binding of name object, reducing the number of references to the object object was bound to by 1. Which may or may not make that object garbage.

Tim Peters
  • 67,464
  • 13
  • 126
  • 132