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]

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]

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.

 

[Arnaud Delobelle]

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

 

[John Machin]

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]

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.

 

[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

 

[Hrvoje Niksic]

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.

 

[Neil Cerutti]

[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. ;-)

 

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

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]

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.

 

[Ant]

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

lol!

 

[Peter Otten]

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]

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]

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]

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

 

[Raymond Hettinger]

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]

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.

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

One deletion is enough to trigger the assertion:
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]

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