How does Python's OrderedDict remember elements inserted?

Question

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.

Rundlet

Answer 1

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].

Spurtle

Thank you, this is certainly very helpful. – Rundlet

Could you elaborate the last three lines which talks about sentinel element. – Rundlet

Sentinels are essentially dummy nodes used to mark the beggining and the end of linked lists for optimization purposes. There are plenty of resourses for them [1, 2, 3] and it is more of a theoretical aspect. The last simply indicates what the contents of each node shall be. – Spurtle