Are Python deques linked lists?

[Neil Cerutti]

On 2007-12-10, Duncan Booth <duncan.booth at invalid.invalid> wrote:
> Neil Cerutti <horpner at yahoo.com> wrote:
>> Python's iterators are unsuitable for mutating the linked list
>> while iterating--the only major application of linked lists.
>> Wrapping in a generator won't allow you to use for loop
>> syntax, unless I'm missing something, which has often
>> happened.
>
> It is certainly possible to have a linked list implementation
> which supports mutation while iterating. Here's a simple
> example:
>
> import random
>
> class LinkedElement(object):
>     def __init__(self, value, next):
>         self.value = value
>         self.next = next
>
> class LinkedList(object):
>     def __init__(self, aList):
>         nxt = None
>         for el in reversed(aList):
>             nxt = LinkedElement(el, nxt)
>         self._cursor = self._list = LinkedElement(None, nxt)
>         
>
>     def delete(self, element):
>         assert self._cursor.next is element
>         self._cursor.next = self._cursor.next.next
>
>     def __iter__(self):
>         self._cursor = el = self._list
>         while el.next:
>             nxt = el.next
>             yield nxt
>             if nxt is el.next:
>                 self._cursor = el = nxt
>
> def test():
>     ll = LinkedList([random.randint(1,1000) for i in range(10)])
>
>     for el in ll:
>         if el.value%2==0:
>             ll.delete(el)
>
>     print [el.value for el in ll]
>
>
> if __name__=='__main__':
>     test()
>
> Support for deleting elements other than the current one, and
> insertBefore/insertAfter methods is left as an exercise.

Making an object its own iterator for files, but not for a
container. After the deletions, you can never iterate again.

-- 
Neil Cerutti