python at rcn.com
Fri Mar 20 18:08:48 CET 2009
> The doubly-linked list part is what's sick and perverted.
The doubly-linked list part is what gives it big-oh running
times the same as regular sets. If the underlying sequence
is stored as a list, then deletion goes from O(1) to O(n).
If the insertion times are recorded in a dictionary, then
the insertion order has to be sorted prior to iteration
which makes iteration go from O(n) to O(n log n).
More information about the Python-list