LINKED LISTS?

Gordon McMillan gmcm at hypernet.com
Sat May 13 15:31:26 CEST 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).

- Gordon




More information about the Python-list mailing list