python lists?

[Martin v. Loewis]

strombrg at tesuji.nac.uci.edu (Dan Stromberg) writes:

> So are python lists real lists in the algorithmic sense, or something
> more?  

No. Python lists are real arrays, or real vectors, depending on your
terminology.

> I just saw a binary search of a python list using the bisect
> module, but it seems to me that should be something less than log2(n)
> on a traditional linked list.  

Notice that you qualify this as "linked" list here :-) The term "list"
in itself doesn't really universally describe an implementation
strategy.

> Just what are python lists?  And is it an implementation detail I'm
> supposed to ignore for most purposes?

I don't think there are any complexity guarantees in the language
definition, but all existing implementations of Python guarantee O(1)
access by index. Complexity of appending to a list varies by Python
version (it used to be O(n*n), worst case, but that is no longer
true). Complexity of deleting an item is O(n).

So, while you should not worry to much about this, it helps to know
that lists are implemented as contiguous fields of pointers
internally.

Regards,
Martin