Ricardo Aráoz wrote: > Kent Johnson wrote: >> Use list when you want a sequence of items indexed by sequential integers. >> Lists >> - preserve order >> - are fast for indexed lookup >> - are relatively slow (O(n)) for adding, deleting and searching (though >> for small lists this should not be a consideration) > > Are you sure they take O(n) for adding? I would have thought it would > take O(1).
Perhaps I was a bit hasty. Lists are implemented as arrays of references. I believe they are - amortized O(1) for append - occasionally the list must be reallocated and copied - O(1) for delete from the end ? - O(n) for insert and delete not at the end - the values above the insert/delete must be copied - O(n) for search which is sequential search Kent _______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
