> > 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 -- http://mail.python.org/mailman/listinfo/python-list