Python lists/vectors/???

[Courageous]

Neel Krishnaswami wrote:
> 
> 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.

I noticed that (I have the code). That's the way I would have done
it, too. I was more concerned about people pushing/popping python
lists not realize that it was O(n).



C/