Are Python deques linked lists?

[Duncan Booth]

Peter Otten <__peter__ at web.de> wrote:


>> Only if you try to modify the list from both of them. 
> 
> One deletion is enough to trigger the assertion:

Yes, but the assertion isn't intended to be the complete code.

> 
> Or you just rule that delete(x) must occur "immediately" after x =
> next(). 

My original code went something like this:

    def delete(self, element):
        if self._cursor.next is element:
            self._cursor.next = self._cursor.next.next
        else:
            el = self._list
            while el.next:
                if el.next is element:
                    el.next = el.next.next
                    break
                el = el.next

i.e. do the most expected case fast and fall back to the slow method for 
other situations. I deleted the 'else' branch because the code I posted 
never takes that branch so I have no way to test whether I got it right or 
not.

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).