Are Python deques linked lists?

[Neil Cerutti]

On 2007-12-10, Neil Cerutti <horpner at yahoo.com> wrote:
> On 2007-12-09, Just Another Victim of the Ambient Morality
><ihatespam at hotmail.com> wrote:
>> 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