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

[Neil Cerutti]

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

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(o bject):
def __init__(self, value, next):
self.value = value
self.next = next

class LinkedList(obje ct):
def __init__(self, aList):
nxt = None
for el in reversed(aList) :
nxt = LinkedElement(e l, nxt)
self._cursor = self._list = LinkedElement(N one, nxt)
def delete(self, element):
assert self._cursor.ne xt is element
self._cursor.ne xt = self._cursor.ne xt.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__=='__ma in__':
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 <sjmac...@lexic on.netwrote:

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

<ihates...@hotm ail.comwrote:

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**********@i nvalid.invalidw rote:

>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__=='__ma in__':
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**********@i nvalid.invalidw rote:

>>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__=='__ma in__':
test()

Support for deleting elements other than the current one, and
insertBefor e/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__=='__ma in__':
test()

Support for deleting elements other than the current one, and
insertBefor e/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_iterato r) is itself, so nothing
prevents you from saving a reference to it before iterating:

iter = iter(a_linked_l ist)
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__=='__ma in__':
test()

Support for deleting elements other than the current one, and
insertBefo re/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_iterato r) is itself, so nothing
prevents you from saving a reference to it before iterating:

iter = iter(a_linked_l ist)
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(rang e(10))
a = iter(items)
b = iter(items)
a.next()

<linkedlist.Lin kedElement object at 0xb7d3f12c>

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

<linkedlist.Lin kedElement 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.ne xt 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 "immediatel y" 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 "immediatel y" after x =
next().

My original code went something like this:

def delete(self, element):
if self._cursor.ne xt is element:
self._cursor.ne xt = self._cursor.ne xt.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**********@i nvalid.invalidw rote:

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