LINKED LISTS?

[Gordon McMillan]

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