OrderedDict already uses a linked list alongside a dictionary and meets all of your timing expectations, but has a higher memory usage, as linked lists generally do.

Since so many Python objects use dictionaries under the hood, it would probably not be worth it to completely change the dict structure and the memory usage of Python as a whole to only benefit this uncommon case. See Objects/dictnotes.txt for the highest priority use cases of dicts.

Per the OrderedDict docs, ordering is only secondary for dicts, but it's the focus for OrderedDicts. Just like you wouldn't send a list to do the job of a deque or vice versa, I don't think you should send an dict to do the job of an OrderedDict or vice versa.