Are Python deques linked lists?

[Peter Otten]

Duncan Booth wrote:

> Peter Otten <__peter__ at web.de> wrote:

>> However, you will get into trouble if you try to run two simultaneous
>> iterations over the same LinkedList, so there is room for another 
>> exercise ;)

That was a bit vague; I saw the shared _cursor attribute but didn't dig
deeper because I understood that your

> point wasn't to give a bullet-proof implementation of a linked
> list, just to demonstrate that there is no bar to having one which lets
> you use a for loop and delete elements.

>> However, you will get into trouble if you try to run two simultaneous
>> iterations over the same LinkedList

> Only if you try to modify the list from both of them. 

One deletion is enough to trigger the assertion:

>>> from linkedlist import *
>>> items = LinkedList(range(10))
>>> a = iter(items)
>>> b = iter(items)
>>> a.next()
<linkedlist.LinkedElement object at 0xb7d3f12c>
>>> x = a.next()
>>> b.next()
<linkedlist.LinkedElement object at 0xb7d3f12c>
>>> items.delete(x)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "linkedlist.py", line 17, in delete
    assert self._cursor.next is element
AssertionError

> Non-modifying
> iterations don't interfere. Changing the code to handle modifications
> from simultaneous iterations is fairly straightforward but probably
> tedious to cover all possible cases: probably the simplest thing is to
> catch such cases and throw an exception.

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

Peter