[Tutor] calling a variable name

Kent Johnson kent37 at tds.net
Wed Oct 24 04:10:24 CEST 2007


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


More information about the Tutor mailing list