LINKED LISTS?

[Gareth McCaughan]

"Courageous" wrote:

> Okay, I downloaded the python source, as I had to know how
> lists were implemented in python. Does nobody care that
> pushing onto a so-called python "stack" is actually O(n)?
> Am I the only person who cares about O(1) versus 0(n)?

If what you want is a stack, then pushing and popping on
a stack implemented with Python lists is O(1) amortised time.
(The top element is the *last* one, not the first.)

Linked lists are hardly ever faster than resizing vectors.
For applications where you really need Lisp-style conses,
build them out of 2-element lists or tuples and make your
own printing functions.

-- 
Gareth McCaughan  Gareth.McCaughan at pobox.com
sig under construction