Search code examples
pythondictionarycollectionsordereddictionarylru

How does Python's OrderedDict remember elements inserted?

How does OrderedDict in Python remember all the order of the elements? What is the performance overhead? For problems like implementing LRU, I found this really powerful and very simple to implement, but what is the performance gain here? How does it remember the order of the keys that were first inserted?

Does it use a Dict() and Double Linked List for remembering the keys as shown in the below picture? I will really appreciate if you could convey your message in a simple language rather than sharing some kind of a research paper.

enter image description here

Solution

  • The best thing about this is that you can look at the source for OrderedDict to get a good understanding of it.

    It is actually implemented in pure python too! This means that you can copy it, redefine it and generally freakishly mutate it as much as you want until you understand it.

    It does use a Doubly Linked List, this is specified in the docstring of the source file. Getting a grip of how doubly linked lists work and by browsing the source, you'll get a good hang of how exactly it works:

    # An inherited dict maps keys to values.
# The inherited dict provides __getitem__, __len__, __contains__, and get.
# The remaining methods are order-aware.
# Big-O running times for all methods are the same as regular dictionaries.

# The internal self.__map dict maps keys to links in a doubly linked list.
# The circular doubly linked list starts and ends with a sentinel element.
# The sentinel element never gets deleted (this simplifies the algorithm).
# Each link is stored as a list of length three:  [PREV, NEXT, KEY].