Are Python deques linked lists?

[Just Another Victim of the Ambient Morality]

I'm looking for a linked list implementation. Something iterable with
constant time insertion anywhere in the list. I was wondering if deque() is
the class to use or if there's something else. Is there?
Thank you...

[Duncan Booth]

Neil Cerutti <ho*****@yahoo. comwrote:

If you put an instrumented iterator through, say, reversed or
sorted, you'd lose the ability to use it to modify the list

I think that is kind of irrelevant. reversed doesn't take an iterator, it
requires a sequence and returns an iterator. sorted will take an iterator
but it always returns a new list.

I do have one last question about a doubly-linked list. Would you
have to perform any tricks (del statements) to get the garbage
collector to collect every node, or will it just work?

It should just work.

[Neil Cerutti]

On 2007-12-11, Duncan Booth <du**********@i nvalid.invalidw rote:

Neil Cerutti <ho*****@yahoo. comwrote:

>If you put an instrumented iterator through, say, reversed or
sorted, you'd lose the ability to use it to modify the list

I think that is kind of irrelevant. reversed doesn't take an
iterator, it requires a sequence and returns an iterator.
sorted will take an iterator but it always returns a new list.

Thank you! Strangely enough I didn't know either of those things.
I've been using sorted as if it were a generator, and I guess
I've never used reversed on an iterator before.

>I do have one last question about a doubly-linked list. Would you
have to perform any tricks (del statements) to get the garbage
collector to collect every node, or will it just work?

It should just work.

Cool.

--
Neil Cerutti
I am free of all prejudices. I hate everyone equally. --W. C. Fields

[Hrvoje Niksic]

Neil Cerutti <ho*****@yahoo. comwrites:

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.

[Hrvoje Niksic]

Duncan Booth <du**********@i nvalid.invalidw rites:

>I do have one last question about a doubly-linked list. Would you
have to perform any tricks (del statements) to get the garbage
collector to collect every node, or will it just work?

It should just work.

Fortunately that's trivial to verify:

class Node(object):
def __init__(self, prev):
self.prev = prev
if prev is not None:
prev.next = self
self.next = None

Now, simply create several nodes in a loop:

while 1:
head = Node(None)
node = Node(head)
node = Node(node)

If the Python process grows without bounds, the GC failed to do its
job.

GC in recent Python releases handles cyclic references flawlessly, at
least in the types shipped. For comparison, the equivalent Perl code
leaks like a hose.