Sorted list as an alternative to dictionary for when youonly need keys?

[Terry Reedy]

"Daniel Eloff" <danieleloff at hotmail.com> wrote in message
news:001f01c46dd7$f0511b60$4b00a8c0 at RR2...
> Sad that sets are really just dicts. But why is only lookup O(log n) ?
> Insertion is just lookup + list.insert(). Similar for removing elements.
> The complexity of list.insert() depends on the underlying
> implementation, (vector or linked list?) but that still shouldn't make
> it O(n) ?

Python lists are arrays/vectors and insertion/deletion is O(n) for anything
close to an even distribution of insertion/deletion points.

For simple linked lists, the linear scan is O(n) (again, for anything close
to an even distribution of search termination points).

Terry J. Reedy