Proposed implementation for an Ordered Dictionary

Raymond Hettinger python at
Fri Feb 27 00:41:39 CET 2009

[Paul Rubin]
> What about using a second dictionary (indexed by the incrementing
> counter) instead of a list to record the insertion order?  Then you
> have O(1) deletion, and traversal takes an O(n log n) sorting
> operation.

My first attempt used exactly that approach and it works fine
though it does complicate the code quite a bit and slows down
all of the common operations by a constant factor.


More information about the Python-list mailing list