On 2007-12-10, Neil Cerutti <[EMAIL PROTECTED]> wrote: > On 2007-12-09, Just Another Victim of the Ambient Morality ><[EMAIL PROTECTED]> 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 -- http://mail.python.org/mailman/listinfo/python-list
