Are Python deques linked lists?

[Neil Cerutti]

On 2007-12-11, Duncan Booth <duncan.booth at invalid.invalid> wrote:
> There are lots of ways to handle this. You could save a
> separate pointer for each iterator. In fact I would expect that
> to handle all the possible variations of inserting and deleting
> correctly you do need to keep all the pointers somewhere they
> can be updated. Or as has been suggested you move the delete
> method onto the iterator itself. Actually I suspect that while
> it adds some overhead to a loop where you are going to modify
> the list it probably results in the cleanest code overall: if
> you have the iterator you can safely insert or remove objects
> without too many worries (just some basic sanity checking).

If you put an instrumented iterator through, say, reversed or
sorted, you'd lose the ability to use it to modify the list--so
it's good for the method to live in the iterator, because you
won't have access to the method anymore, either. In the other
scheme, you could accidentally use an iterator to make
modifications that's ignorant of the necessary bookkeeping (I
suppose you could raise an exception if there's a central
registry of valid iterators, though I like making the method
completely invisible).

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?

-- 
Neil Cerutti