How OrderedDict keeps order in Python

Question

I am curious how the OrderedDict from the collection library stores key / steam? I looked on the Internet and did not find the answer.

Answer 1

From the source code, it appears as dictwith a doubly linked list of keys for ordering, as well as another dictthat maps the keys to their position in the list.

• The insert only adds to the end of the list.
• Deletion uses a second dict to remove an item from the list.
• Iteration is performed on a linked list.