Doubly linked list

doubly_linked_list.py

class DoublyLinkedList(object):
    # Copied from Python standard Library Lib/collections.py
    # The circular doubly linked list starts and ends with a sentinel element.
    # The sentinel element never gets deleted (this simplifies the algorithm).
    # Each link is stored as a list of length three:  [PREV, NEXT, VAL].
    def __init__(self):
        self.__root = root = [] # sentinel node
        root[:] = [root, root, None]

    def append(self, val):
        root = self.__root
        last = root[0]
        last[1] = root[0] = self.__map[key] = [last, root, val]
        
    def remove(self, link):
        link_prev, link_next, _ = link
        link_prev[1] = link_next                        # update link_prev[NEXT]
        link_next[0] = link_prev                        # update link_next[PREV]