LINKED LISTS?

[Neel Krishnaswami]

Fredrik Lundh <effbot at telia.com> wrote:
> Robin Becker <robin at jessikat.demon.co.uk> wrote:
> > which is clearly not O(1); arguing that making accesses O(1) is 'the
> > right thing to do' will get short shrift from the complexity experts who
> > will want to know about the overall usage.
> 
> iirc, the ABC interpreter (written by Guido) used "theoretically
> ideal" implementations for all built-in datatypes.  the fact that
> he went for simplicity in Python might tell us something...

I thought the ABC interpreter used AVL trees for nigh-everything.
They have O(log N) performance for most operations, which is ok is you
know that your users are newbies (who tend to assume that every built
in operation takes a small amount of time), but does make real
performance kind of sluggish.


Neel