Are Python deques linked lists?

[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