Python lists/vectors/???

[Neel Krishnaswami]

Courageous <jkraska1 at san.rr.com> wrote:
> 
> Something I don't understand about python list[] structures: are
> they o(1) on index or o(n)? This is puzzling to me, because it's not
> obvious what performance to expect from them at first glance. You'd
> think there would be a python list type, for linked lists, and
> python array type, for vectors, but there's not.  What's up with
> that?

They are O(1) arrays. list.append()ing to them is technically O(n),
but a full resize is triggered only every hundred (or thousand for big
lists) insertions because the resize leaves some slop.


Neel