Are Python deques linked lists?

[Neil Cerutti]

On 2007-12-10, Hrvoje Niksic <hniksic at xemacs.org> wrote:
> Neil Cerutti <horpner at yahoo.com> writes:
>
>> Anyhow, implementing linked lists in Python is not challenging, but
>> they don't work well with Python iterators, which aren't suitable
>> for a linked list's purposes--so you have to give up the happy-joy
>> for loop syntax in favor of Python's frowny-sad while loops.
>
> With the help of generators, it is trivial to turn a frowny loop into
> a happy one:
>
> class Node:
>     def __init__(self):
>         self.next = None
>         # attach data to the node as needed, and use "next" to refer
>         # to the next node.
>
>     def __iter__(self):
>         node = self
>         while 1:
>             yield node
>             node = node.next
>             if node is None:
>                 break
>
> def linkify(it):
>     """Turn a Python iterable into a linked list."""
>     head = prev = None
>     for elem in it:
>         node = Node()
>         node.data = elem
>         if prev is None:
>             head = node
>         else:
>             prev.next = node
>         prev = node
>     return head
>
> # iterate over a linked list using 'for':
>
>>>> linkedlist = linkify([1, 2, 3])
>>>> for n in linkedlist:
> ...   print n.data
> ...
> 1
> 2
> 3
>
> Correctly handling empty lists is left as an excercise for the
> reader.

It was providing the ability to mutate the list using an iterator
as a node reference that I alleged rendered linked lists a bit
awkward in Python syntax. The discussion yielded a couple of
solutions, though.

-- 
Neil Cerutti
And now the sequence of events in no particular order. --Dan Rather