Home Original page

Are Python deques linked lists?

Hrvoje Niksic hniksic at xemacs.org
Mon Dec 10 09:03:31 EST 2007 
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.
More information about the Python-list mailing list