Are Python deques linked lists?

[Hrvoje Niksic]

Duncan Booth <duncan.booth at invalid.invalid> writes:

>> I do have one last question about a doubly-linked list. Would you
>> have to perform any tricks (del statements) to get the garbage
>> collector to collect every node, or will it just work?
>
> It should just work.

Fortunately that's trivial to verify:

class Node(object):
    def __init__(self, prev):
        self.prev = prev
        if prev is not None:
            prev.next = self
        self.next = None

Now, simply create several nodes in a loop:

while 1:
     head = Node(None)
     node = Node(head)
     node = Node(node)

If the Python process grows without bounds, the GC failed to do its
job.

GC in recent Python releases handles cyclic references flawlessly, at
least in the types shipped.  For comparison, the equivalent Perl code
leaks like a hose.