gmcm at hypernet.com
Sat May 13 09:31:26 EDT 2000
Courageous <jkraska1 at san.rr.com> wrote:
>I don't get it. The code for python lists is, as plain as
>the nose on the end of my face, a resizeable vector
>implementation. Which is all well and good, but where
>are the linked lists for those of us who want insert,
>delete, and append to be O(1)?
In practice, linked lists are O(really big 1). That is, for most usage,
Python's supposedly O(n) lists will outperform them. Trust me on
this. I've optimized a *lot* of C / C++ code by replacing linked lists
with (overallocated) realloc-ing vectors. In most cases the speed up
is dramatic (even when a linked list appears the correct structure).
More information about the Python-list