Gordon McMillan gmcm at
Sat May 13 09:31:26 EDT 2000

Courageous <jkraska1 at> 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).

- Gordon

More information about the Python-list mailing list