[Tutor] calling a variable name
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.
>> - 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
- 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
More information about the Tutor