> this is assuming you consider a hash table lookup to take constant time
That's exactly the part I was referring to. If deleting the key from an OrderedDict is O(1), then all these operations have to be O(1):
- dictionary deletion
- _map.pop (which is another dictionary deletion)
- linked list removal (obvious)
I'm not saying they aren't - just wanted to make sure that's the case. I didn't know whether to interpret the sentence from "what's new" as - "we use a map to know the elements, so the only operation on a linked list is unlink, which is O(1)", or "the whole lookup+delete is O(1)".