LINKED LISTS?

[Courageous]

Gordon McMillan wrote:
> 
> 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.

Which is to say O(1)+k, where k is large. The larger problem
is when a user of a data structure has an O(n) operation, and
they know that n is large, don't you think? There's more than
one implementation of a list around, and there are indeed
versions that are O(1)+k, where k is pretty small. It depends
on what you want to support (backward iteration for example?
no). I suspect that one of the reasons lists were left out
is a certain problem I forsee with iterators and list mutatation...

C/