Can double-linked lists be implemented in python?

[Peter Hansen]

Dave Kuhlman wrote:
> 
> Peter Hansen wrote:
> 
> > Robin Munn wrote:
> >>
> >> sdieselil <sdieselil at yahoo.com> wrote:
> >> > Hi
> >> >
> >> > How can I implement double-linked lists and other complex tree-like
> >> > structures in Python?
> >>
> >> Do you *need* doubly-linked lists? Is there something that Python's
> >> builtin list type can't do for you? Consider whether it's worth taking
> >> the time to code up a data structure, with all the attendant edge cases,
> >> when you've already got such nice useful builtin types...
> >
> > I can think of at least one example where one would *need* doubly-linked
> > lists... a homework assignment.  ;-)
> 
> But suppose that I *do* implement double linked lists.  I'll have two
> objects that point at each other, in other words circular references.

Uh, only if you've implemented some magic technique of deleting a range
of items from the list, and are not planning to maintain references to 
them from elsewhere.  And even then as Aahz points out, the GC will find
the cycles and remove them from memory (unless the Nodes have __del__ methods).

But why would you do that?  Normally you remove items one at a time from
a list...  or are you talking about in the case where you delete the 
reference to the entire list without first emptying the list?  It sounds
like you're fishing here... why not just build it and see how it works?
(I realize you weren't the OP...)

> In older versions of Python, circular references were not garbage collected.
> Is this still true in Python 2.2 and 2.3?  Do I need to use the gc module
> to *enable* garbage collection?  Or, is not *disabling* it good enough?  Do
> I still need to worry about this?  And, suppose you tell me that circular
> references are collected but I don't believe you.  How can I check?

Uh.... allocate a zillion linked lists, fill them with objects, and then
delete the references to them and watch the memory get reclaimed.  

This is _Python_: just try it!  There's no excuse for someone not 
experimenting with something like this in Python... it takes all of a few
minutes to try it out and see how it behaves.  In XP, you call that a
"spike" or spike solution, and it tells you just enough that you can 
carry on with design decisions based on the results.  Python is very
very very good for this sort of approach, to the point that if you 
don't believe me about the garbage collection, you have a very clear 
path ahead of you. :-)

-Peter