Doubly Linked List in Python

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():
    head = []
    head[:] = [head, head, None]
    return head

def dll_append(head, value):
    last = head[0]
    node = [last, head, value]
    last[1] = head[0] = node
    return node

def dll_remove(node):
    prev_link, next_link, _ = node
    prev_link[1] = next_link
    next_link[0] = prev_link
    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

def dll_iter(head):
    curr = head[1]              # start at the first node
    while curr is not head:
        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()

In [43]: dll_append(head, 1)
Out[43]: [[[...], [...], None], [[...], [...], None], 1]

In [44]: dll_append(head, 2)
Out[44]: [[[[...], [...], None], [...], 1], [[...], [[...], [...], 1], None], 2]

In [45]: dll_append(head, 3)
Out[45]:
[[[[[...], [...], None], [...], 1], [...], 2],
 [[...], [[...], [[...], [...], 2], 1], None],
 3]

In [46]: list(dll_iter(head))
Out[46]: [1, 2, 3]

In [47]: head[1] == head
---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-47-c6cdf1199c54> in <module>()
----> 1 head[1] == head

RecursionError: maximum recursion depth exceeded in comparison

In [48]: head[1] is head
Out[48]: False

In [49]: id(head[1]), id(head)
Out[49]: (4359947336, 4359845960)

The value comparison operator == will not work as the nodes are compared lexicographically and recursively.

Sequences compare lexicographically using comparison of corresponding elements, whereby reflexivity of the elements is enforced.

We should use the identity comparison, is or compare the value of id as described above, see the language specification for more details.