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

On 2007-12-09, Just Another Victim of the Ambient Morality
<ih*******@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]

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]

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]

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

On 2007-12-09, Just Another Victim of the Ambient Morality
<ih*******@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]

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