LINKED LISTS?

[Fredrik Lundh]

"Courageous" <jkraska1 at san.rr.com> wrote:
> Okay, I downloaded the python source, as I had to know how
> lists were implemented in python.

http://www.python.org/doc/FAQ.html#6.16

> Am I the only person who cares about O(1) versus 0(n)?

probably not -- the implementors obviously thought that
constant *access* time was more important.

and having a simple implementation doesn't hurt, of course.

> 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)?

here's one:
http://starship.python.net/crew/lemburg/mxStack.html

there are probably others out there.  check the vaults:
http://www.vex.net/parnassus/apyllo.py

</F>