> How does the OrderedDict work? It maintains a doubly-linked list of keys, appending new keys to the list as they’re inserted. A secondary dictionary maps keys to their corresponding list node, so deletion doesn’t have to traverse the entire linked list and therefore remains O(1).
Hmm... shouldn't that be `O(log n)` or something like that? Or do they really use cuckoo (or similar) hashing with O(1) hash access?