python lists?

[Alex Martelli]

Dan Stromberg wrote:

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

They're closer to arrays.

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

less?  you mean more?

> on a traditional linked list.  In fact, my first impression is that a
> binary search of a linked list is likely to be worse than a linear
> search.  Maybe a doubly linked list would be kinda reasonable.  Or

Nope.

> maybe something that's not quite a list but a weird hybrid-list-array
> thing?

No hybridization involved.

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

Basically arrays (that can grow and shrink as needed).  It's important
to know because of big-O level performance considerations: e.g. somelist[n] 
is O(1), *NOT* O(n), but on the other hand appending something at the 
_start_ of an N-length list is O(N) [appending at the end is amortized 
O(1)].


Alex