Safe doubly-linked list/tree implementation?

[Skip Montanaro]

    Lars> I'm trying to come up with an implementation of a doubly-linked
    Lars> tree (where the children have links to their parents) that doesn't
    Lars> leak memory due to reference cycles.  It's such a simple data
    Lars> structure that I feel a bit foolish asking, but...

Check the archives of the newsgroup looking for "weak references".  I
believe Christian Tismer or Marc-Andre Lemburg implemented in the past
couple of years.  (Or maybe in was Konrad Hinsen.  Those Europeans.  They
all look alike to me... ;-)

    Lars> The FAQ says that in the case of doubly-linked structures,
    Lars> reference cycles must be explicitly broken in order to avoid
    Lars> memory leakage.  I thought that I could use __del__ to do this,
    Lars> but __del__ only seems to be called when the reference count
    Lars> reaches zero.

Common practice is to add a destroy() method to each class that needs to
participate in a cycle.  When you're finished with the object, call
destroy() explicitly.

A post showed up in the digest within the last 24 hours by Martin von Loewis
about how classes participating in cycles could be refactored to not contain
cycles.  Looks like it hasn't made it to into deja.com's archives yet.  I
think it was part of the "GC & finalizers" thread.

-- 
Skip Montanaro (skip at mojam.com)
http://www.mojam.com/
http://www.musi-cal.com/