# Doubly Linked List in Python

pythonalgorithm

As a hacker, it is a shame of being amazed by the magic without digging into the prestige. So I checkout the implementation of OrderedDict, and found how OrderedDict handles the insertion order internally: a doubly linked list to track the insertion order, with a dict mapping the key to the node for quick access.

It is worthy noting that the doubly linked list is implemented in a bizarre and elegant way, here is a stripped version for the sake of simplicity:

def dll_init():

return node

def dll_remove(node):
return node

def dll_insert_before(succedent, value):
# Create a node to host value, and insert BEFORE the succedent
node = [succedent[0], succedent, value]
succedent[0][1] = node
succedent[0] = node
return node

def dll_insert_after(precedent, value):
# Create a node to host value, and insert AFTER the precedent
node = [precedent, precedent[1], value]
precedent[1][0] = node
precedent[1] = node
return node

curr = head[1]              # start at the first node
yield curr[2]           # yield the curr[KEY]
curr = curr[1]          # move to next node


Each node of the doubly linked list is a tuple of (next_node, previous_node, value). The most intriguing part is head[:] = [head, head, None]: we create a sentinel by setting the head’s next_node, previous_node pointing to itself. If the list is not empty, the head’s previous_node will point to the last node, tail; and the tail’s next_node will point to the head. The rest of the code is just self-explained.

Let’s play it in the sandbox:

In [42]: head = dll_init()

Out[43]: [[[...], [...], None], [[...], [...], None], 1]

Out[44]: [[[[...], [...], None], [...], 1], [[...], [[...], [...], 1], None], 2]

Out[45]:
[[[[[...], [...], None], [...], 1], [...], 2],
[[...], [[...], [[...], [...], 2], 1], None],
3]

Out[46]: [1, 2, 3]

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
in ()

RecursionError: maximum recursion depth exceeded in comparison

Out[49]: (4359947336, 4359845960)
The value comparison operator == will not work as the nodes are compared lexicographically and recursively.
We should use the identity comparison, is or compare the value of id as described above, see the language specification for more details.