Are Python deques linked lists?

[Duncan Booth]

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.