How is an ordereddict implemented in python?

You must be aware of the key-value pair kind of data structure in Python, namely Dict, commonly known as a dictionary in Python. But what is an OrderedDict?

This is very much similar to the regular dictionary but helps preserve the order in which the elements are inserted into it. Basically, the order of elements is remembered in an OrderedDict. This means, when iterating over an OrderedDict, the elements are returned in the same order in which the keys (of the key-value pair) were inserted into the data structure.

Under the hood, OrderedDict is implemented with the help of the doubly-linked list data structure. This is so that the order of the OrderedDict is retained.

Basic difference between Dict and OrderedDict

Let's take a code example to understand the basic difference between a dictionary and an OrderedDict,

print("A dictionary: ") 
my_dict = {} 
my_dict['a'] = 1
my_dict['b'] = 2
my_dict['c'] = 3
my_dict['d'] = 4
  
for key, value in my_dict.items(): 
    print(key,value) 
 
from collections import OrderedDict 
    
print("An Ordered Dictionary") 
my_ordered_dict = OrderedDict() 
my_ordered_dict['a'] = 1
my_ordered_dict['b'] = 2
my_ordered_dict['c'] = 3
my_ordered_dict['d'] = 4
  
for key, value in my_ordered_dict.items(): 
    print(key, value)

Output:

A dictionary:
a 1
b 2
c 3
d 4
An Ordered Dictionary:
a 1
b 2
c 3
d 4

Note: This was executed on Python 3.7, hence the order of regular dictionary also has been retained. Try executing it on Python 3.6 or less to see that the order of elements in a regular dictionary isn't retained.

Also, as you can see to use OrderedDict, we need to import it from the collections package.

What if the key's data is changed in an OrderedDict?

When the value of a specific key is changed in an OrderedDict, the index of the key remains intact, and so does the index of the changed value associated with the key.

Time for an example:

from collections import OrderedDict 
  
my_ordered_dict = OrderedDict() 
my_ordered_dict['a'] = 1.3
my_ordered_dict['b'] = 5.8
my_ordered_dict['c'] = 8.3
my_ordered_dict['d'] = 0.5

for key, value in my_ordered_dict.items(): 
    print(key, value) 
  
my_ordered_dict['d'] = 7.9
print("\n")
print("After change in the value of key d")
for key, value in my_ordered_dict.items(): 
    print(key, value)

Output:

a 1.3
b 5.8
c 8.3
d 0.5

After the change in the value of key d
a 1.3
b 5.8
c 8.3
d 7.9

What if an element is deleted and the same element is inserted again?

An element can be deleted by specifying its key. If an element is deleted and the same element is re-inserted into the OrderedDict, it is inserted at the end of the ordered dictionary. It is similar to adding just another element into the dictionary.

from collections import OrderedDict 
  
my_ordered_dict = OrderedDict() 
my_ordered_dict['a'] = 3
my_ordered_dict['b'] = 6
my_ordered_dict['c'] = 1
my_ordered_dict['d'] = 7
  
for key, value in my_ordered_dict.items(): 
    print(key, value) 
  
print("\n")
print("Post deletion") 
my_ordered_dict.pop('c') 
for key, value in my_ordered_dict.items(): 
    print(key, value) 
  
print("\n") 
print("Post re-inserting")
my_ordered_dict['c'] = 3
for key, value in my_ordered_dict.items(): 
    print(key, value)

Output:

a 3
b 6
c 1
d 7

Post deletion
a 3
b 6
d 7

Post re-inserting
a 3
b 6
d 7
c 3

Can I use OrderedDict like a Stack?

Yes, it can be made to behave like a Stack data structure using its popitemmethod. Let's take an example,

my_ordered_dict = OrderedDict() 
my_ordered_dict['a'] = 2
my_ordered_dict['b'] = 7
my_ordered_dict['c'] = 0
my_ordered_dict['d'] = 4

for key, value in my_ordered_dict.items(): 
    print(key, value) 

my_ordered_dict.popitem()
print("\n")
print("After deletion")
for key, value in my_ordered_dict.items(): 
    print(key, value)

Output:

a 2
b 7
c 0
d 4

After deletion
a 2
b 7
c 0

It is following the Last in First out order.

Note: The only difference between a python dictionary and OrderedDict is that in OrderedDict, the order in which the elements were inserted is preserved and the data is returned in the order in which the keys were inserted.

Updated Note: Beginning from Python 3.7, the dictionary has also been programmed in such a way that the order in which elements are inserted into a normal dictionary will be preserved.

Conclusion:

In this post, we saw how an OrderedDict can be used, and how it behaves when a key's value is changed and an element, after deleting, is reinserted. Let us know if you have done some interesting stuff with the help of OrderedDict.

You may also like:

• Python Program to Insertion at the beginning in OrderedDict

• How to remove duplicate entries from a list in Python?

• Remove all duplicates from a given string in Python

• How to read CSV file in Python

How do I create an OrderedDict?

How do you implement a dictionary in Python?

How do you create an empty OrderedDict in Python?

Is OrderedDict obsolete?