Are Python deques linked lists?

[Neil Cerutti]

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.

-- 
Neil Cerutti