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]

Re: Are Python deques linked lists?

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.

[Neil Cerutti]

Re: Are Python deques linked lists?

On 2007-12-09, Just Another Victim of the Ambient Morality
<ihatespam@hotm ail.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]

Re: Are Python deques linked lists?

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.

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

--
Arnaud

[John Machin]

Re: Are Python deques linked lists?

On Dec 10, 7:37 pm, Arnaud Delobelle <arno...@google mail.comwrote:

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.

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

Re: Are Python deques linked lists?

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

On 2007-12-09, Just Another Victim of the Ambient Morality
><ihatespam@hot mail.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]

Re: Are Python deques linked lists?

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]

Re: Are Python deques linked lists?

On 2007-12-10, Peter Otten <__peter__@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]

Re: Are Python deques linked lists?

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]

Re: Are Python deques linked lists?

Neil Cerutti <horpner@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.

[Neil Cerutti]

Re: Are Python deques linked lists?

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

Neil Cerutti <horpner@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]

Re: Are Python deques linked lists?

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]

Re: Are Python deques linked lists?

Neil Cerutti wrote:

On 2007-12-10, Duncan Booth <duncan.booth@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]

Re: Are Python deques linked lists?

Peter Otten <__peter__@web. dewrote:

Neil Cerutti wrote:
>

>On 2007-12-10, Duncan Booth <duncan.booth@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]

Re: Are Python deques linked lists?

On 2007-12-10, Peter Otten <__peter__@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