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