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...

[John Machin]

On Dec 10, 9:43 am, "Just Another Victim of the Ambient Morality"
<[e-mail]:

I'm looking for a linked list implementation. Something iterable with
constant time insertion anywhere in the list.

It's on the shelf between the jar of phlogiston and the perpetual
motion machine.

[Neil Cerutti]

On 2007-12-09, Just Another Victim of the Ambient Morality
<ih*******@hotmail.comwrote:

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?

The deque is implemented as a list of arrays. See 5.12.1 Recipes
for the trick of using rotate to delete an item from within the
deque. The docs don't spell out the efficiency (in terms of O
notation) of the rotate method, though. You'll have check the
source, or perhaps Raymond is reading and could explain.

--
Neil Cerutti

[Arnaud Delobelle]

On Dec 9, 10:54 pm, John Machin <[e-mail]:

On Dec 10, 9:43 am, "Just Another Victim of the Ambient Morality"

<[e-mail]:

I'm looking for a linked list implementation. Something iterable with
constant time insertion anywhere in the list.

It's on the shelf between the jar of phlogiston and the perpetual
motion machine.

I recommend a quick glance at any article on linked list.
Here's one: http://en.wikipedia.org/wiki/Linked_list

--
Arnaud

[John Machin]

On Dec 10, 7:37 pm, Arnaud Delobelle <[e-mail]:

On Dec 9, 10:54 pm, John Machin <[e-mail]:

On Dec 10, 9:43 am, "Just Another Victim of the Ambient Morality"

<[e-mail]:

I'm looking for a linked list implementation. Something iterable with
constant time insertion anywhere in the list.

It's on the shelf between the jar of phlogiston and the perpetual
motion machine.

I recommend a quick glance at any article on linked list.
Here's one:http://en.wikipedia.org/wiki/Linked_list

A rather silly way of describing it ... of course once you have done a
search to find where to insert a new element, it takes a trivial
constant time to insert the new element into the linked list.

[Neil Cerutti]

On 2007-12-10, Neil Cerutti <ho*****@yahoo.comwrote:

On 2007-12-09, Just Another Victim of the Ambient Morality
<ih*******@hotmail.comwrote:

>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?

The deque is implemented as a list of arrays. See 5.12.1
Recipes for the trick of using rotate to delete an item from
within the deque. The docs don't spell out the efficiency (in
terms of O notation) of the rotate method, though. You'll have
check the source, or perhaps Raymond is reading and could
explain.

I take that back. As pretty much indicated in the docs, rotate is
implemented as a series of pushes and pops. It doesn't renumber
the nodes--I assumed renumbering might be technically possible
and cheap. Even if rotating were O(1), I suppose removal of an
item would still be o(n/k), with k being the size of the
subarrays, making deletion remain O(n) at the end of the day.

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.

--
Neil Cerutti

[Peter Otten]

Neil Cerutti wrote:

[linked lists] 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.

You can always move the while-loop into a generator and use for-loops
happily ever after.

Peter

[Neil Cerutti]

On 2007-12-10, Peter Otten <__*******@web.dewrote:

Neil Cerutti wrote:

>[linked lists] 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.

You can always move the while-loop into a generator and use
for-loops happily ever after.

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.

# x is a linked list object, containing random numbers.
# delete even numbers
x_iter = x.begin()
while x_iter != x.end():
if x_iter.value % 2 == 0:
x_iter = x.delete(x_iter) # or x_iter.delete() as an iter mutating op?
else:
x_iter.advance()

Of course, a linked lists type would be obliged to provide a
filter method instead.

C++ "solved" this difficulty by making all containers equally
awkward to work with. ;-)

--
Neil Cerutti

[Zentrader]

Instead of linking records together via some key, I first try out a
dictionary of lists. The list for each dictionary key would be the
same as a list with a single, forward link. If you have relatively few
records per key, it works well.

[Duncan Booth]

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

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.

[Neil Cerutti]

On 2007-12-10, Duncan Booth <du**********@invalid.invalidwrote:

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

>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.

Making an object its own iterator for files, but not for a
container. After the deletions, you can never iterate again.

--
Neil Cerutti

[Ant]

On Dec 9, 10:54 pm, John Machin <[e-mail]:

On Dec 10, 9:43 am, "Just Another Victim of the Ambient Morality"

<[e-mail]:

I'm looking for a linked list implementation. Something iterable with
constant time insertion anywhere in the list.

It's on the shelf between the jar of phlogiston and the perpetual
motion machine.

lol!

--
Ant.

[Peter Otten]

Neil Cerutti wrote:

On 2007-12-10, Duncan Booth <du**********@invalid.invalidwrote:

>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.

Making an object its own iterator [works] for files, but not for a
container. After the deletions, you can never iterate again.

Look at the test code again -- there is a second iteration after the
deletions (the list comprehension).

However, you will get into trouble if you try to run two simultaneous
iterations over the same LinkedList, so there is room for another
exercise ;)

Peter

[Duncan Booth]

Peter Otten <__*******@web.dewrote:

Neil Cerutti wrote:

>On 2007-12-10, Duncan Booth <du**********@invalid.invalidwrote:

>>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.

Making an object its own iterator [works] for files, but not for a
container. After the deletions, you can never iterate again.

It isn't its own iterator. The iterator is a separate generator object.

>
Look at the test code again -- there is a second iteration after the
deletions (the list comprehension).

However, you will get into trouble if you try to run two simultaneous
iterations over the same LinkedList, so there is room for another
exercise ;)

Only if you try to modify the list from both of them. Non-modifying
iterations don't interfere. Changing the code to handle modifications from
simultaneous iterations is fairly straightforward but probably tedious to
cover all possible cases: probably the simplest thing is to catch such
cases and throw an exception.

But my point wasn't to give a bullet-proof implementation of a linked list,
just to demonstrate that there is no bar to having one which lets you use a
for loop and delete elements.

[Neil Cerutti]

On 2007-12-10, Peter Otten <__*******@web.dewrote:

Neil Cerutti wrote:

>>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.

Making an object its own iterator [works] for files, but not
for a container. After the deletions, you can never iterate
again.

Look at the test code again -- there is a second iteration
after the deletions (the list comprehension).

Thanks for the correction. I didn't think that through.

However, you will get into trouble if you try to run two
simultaneous iterations over the same LinkedList, so there is
room for another exercise ;)

I just remembered that iter(an_iterator) is itself, so nothing
prevents you from saving a reference to it before iterating:

iter = iter(a_linked_list)
for it in iter:
if it.value % 2 == 0:
iter.delete()

It looks a little weird, but perhaps it's still better than a
while loop.

--
Neil Cerutti
The pastor will preach his farewell message, after which the choir will sing,
"Break Forth Into Joy." --Church Bulletin Blooper

[Neil Cerutti]

On 2007-12-10, Neil Cerutti <ho*****@yahoo.comwrote:

On 2007-12-10, Peter Otten <__*******@web.dewrote:

>Neil Cerutti wrote:

>>>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.

Making an object its own iterator [works] for files, but not
for a container. After the deletions, you can never iterate
again.

Look at the test code again -- there is a second iteration
after the deletions (the list comprehension).

Thanks for the correction. I didn't think that through.

>However, you will get into trouble if you try to run two
simultaneous iterations over the same LinkedList, so there is
room for another exercise ;)

I just remembered that iter(an_iterator) is itself, so nothing
prevents you from saving a reference to it before iterating:

iter = iter(a_linked_list)
for it in iter:
if it.value % 2 == 0:
iter.delete()

It looks a little weird, but perhaps it's still better than a
while loop.

Ugh! Assuming you don't shadow built-ins. ;-)

--
Neil Cerutti

[Raymond Hettinger]

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?

The deque is implemented as a list of arrays. See 5.12.1 Recipes
for the trick of using rotate to delete an item from within the
deque. The docs don't spell out the efficiency (in terms of O
notation) of the rotate method, though. You'll have check the
source, or perhaps Raymond is reading and could explain.

Deques have O(1) append/pop behaviors at either. Mid-sequence
insertions, deletions, and rotations are O(n), although the constant
factor is low.

Raymond

[Peter Otten]

Duncan Booth wrote:

Peter Otten <__*******@web.dewrote:

>However, you will get into trouble if you try to run two simultaneous
iterations over the same LinkedList, so there is room for another
exercise ;)

That was a bit vague; I saw the shared _cursor attribute but didn't dig
deeper because I understood that your

point wasn't to give a bullet-proof implementation of a linked
list, just to demonstrate that there is no bar to having one which lets
you use a for loop and delete elements.

>However, you will get into trouble if you try to run two simultaneous
iterations over the same LinkedList

Only if you try to modify the list from both of them.

One deletion is enough to trigger the assertion:

>>from linkedlist import *
items = LinkedList(range(10))
a = iter(items)
b = iter(items)
a.next()

<linkedlist.LinkedElement object at 0xb7d3f12c>

>>x = a.next()
b.next()

<linkedlist.LinkedElement object at 0xb7d3f12c>

>>items.delete(x)

Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "linkedlist.py", line 17, in delete
assert self._cursor.next is element
AssertionError

Non-modifying
iterations don't interfere. Changing the code to handle modifications
from simultaneous iterations is fairly straightforward but probably
tedious to cover all possible cases: probably the simplest thing is to
catch such cases and throw an exception.

Or you just rule that delete(x) must occur "immediately" after x = next().

Peter

[Duncan Booth]

Peter Otten <__*******@web.dewrote:

>Only if you try to modify the list from both of them.

One deletion is enough to trigger the assertion:

Yes, but the assertion isn't intended to be the complete code.

>
Or you just rule that delete(x) must occur "immediately" after x =
next().

My original code went something like this:

def delete(self, element):
if self._cursor.next is element:
self._cursor.next = self._cursor.next.next
else:
el = self._list
while el.next:
if el.next is element:
el.next = el.next.next
break
el = el.next

i.e. do the most expected case fast and fall back to the slow method for
other situations. I deleted the 'else' branch because the code I posted
never takes that branch so I have no way to test whether I got it right or
not.

There are lots of ways to handle this. You could save a separate pointer
for each iterator. In fact I would expect that to handle all the possible
variations of inserting and deleting correctly you do need to keep all the
pointers somewhere they can be updated. Or as has been suggested you move
the delete method onto the iterator itself. Actually I suspect that while
it adds some overhead to a loop where you are going to modify the list it
probably results in the cleanest code overall: if you have the iterator you
can safely insert or remove objects without too many worries (just some
basic sanity checking).

[Neil Cerutti]

On 2007-12-11, Duncan Booth <du**********@invalid.invalidwrote:

There are lots of ways to handle this. You could save a
separate pointer for each iterator. In fact I would expect that
to handle all the possible variations of inserting and deleting
correctly you do need to keep all the pointers somewhere they
can be updated. Or as has been suggested you move the delete
method onto the iterator itself. Actually I suspect that while
it adds some overhead to a loop where you are going to modify
the list it probably results in the cleanest code overall: if
you have the iterator you can safely insert or remove objects
without too many worries (just some basic sanity checking).

If you put an instrumented iterator through, say, reversed or
sorted, you'd lose the ability to use it to modify the list--so
it's good for the method to live in the iterator, because you
won't have access to the method anymore, either. In the other
scheme, you could accidentally use an iterator to make
modifications that's ignorant of the necessary bookkeeping (I
suppose you could raise an exception if there's a central
registry of valid iterators, though I like making the method
completely invisible).

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?

--
Neil Cerutti

[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**********@invalid.invalidwrote:

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**********@invalid.invalidwrites:

>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.