Python’s collections.OrderedDict (and the regular dict in python 3.7+) is a key-value data structure that allows for constant time search, add, and delete operations, AND it maintains the order in which items (key-value pairs) were inserted. How is this possible?

Python uses 2 internal data structures for its dict. It uses a hash table, which we already know has constant time add, search, and remove operations, however it also uses a doubly linked list to maintain the order the items were inserted.

When an item is inserted into the dict, its hash is also inserted into the doubly linked list, and a pointer to this node of the linked list is stored along with the key-value pair in the hash-table bucket! So here is what happens when you insert an item:

  • The hash of the key is calculated
  • A new node is created in the doubly linked list, and the hash is stored in the node
    • This only happens if this is the first item in the dict with this hash (i.e. the first item going into this specific bucket)
  • The key-value pair along with a pointer to the new doubly linked list node are stored in a bucket in the hash table, according to the hash of the key
H1, H2, etc are hash1, hash2, etc
v is just some value. Notice some buckets have multiple values (b/c hash collisions).

Hash Table:             Doubly Linked List:
+-----------+           +------+
| H1: v     |---------> |  H1  |
+-----------+           +------+
| H2: v     |---------> |  H2  | 
|     v     |           +------+
+-----------+     /---> |  H3  |
| H3: v     |----/      +------+
+-----------+           | .... |
|  ....     |           +------+
+-----------+           

Notice: Each bucket points to the corresponding node in the doubly linked list!

When you delete an item from the dict:

  • The hash of the key is calculated
  • The hash is used to find the corresponding bucket in the hash table
  • The key-value pair is removed from the bucket
  • If the bucket is empty, the corresponding node in the doubly linked list is removed
    • so whenever a bucket becomes empty (gets a size of 0), the corresponding node in the doubly linked list is removed, and whenever a bucket gets a size of 1, a new node is added to the doubly linked list

When you “iterate” through the items of the dict:

  • you just follow the hashes in the doubly linked list, to the corresponding buckets, and you iterate over the items in the buckets!

So, folks, there ya have it! A key-value data structure that maintains the order of insertion, and has constant time add, search, and delete operations! Pretty neat!

Python dicts use an additional data structure, a doubly linked list, to maintain insertion order. When an item is inserted into the dict, if a node hasn’t been created for the target bucket in the doubly linked list, a new node is created and this mapping (from bucket to node) is stored in the bucket. When all items of a bucket are deleted, its corresponding node in the doubly linked list is deleted.