Doubly Linked Lists

Doubly linked lists hold references to both the previous and next elements

Doubly linked lists are particularly useful when paired with other data structures like hash tables since it allows for $O(1)$ retrieval and deletions

It is easiest to use a dummy head and tail pointer for the doubly linked list to avoid weird edge cases

class DoublyLinkedList:
    def __init__(self):
        self.head = Node(0, 'HEAD')
        self.tail = Node(-1, 'TAIL')
	# Setup the dummy pointers
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def insert_end(self, node):
        last = self.tail.prev
	# Fix the last element pointers
        last.next = node
        node.prev = last
	# Set the current element pointers
        node.next = self.tail
        self.tail.prev = node
        self.size += 1

        return node

    def delete(self, node):
        node_prev, node_next = node.prev, node.next
	# All we need to do is re-point the next and prev
	# Don't need to care too much about head/tail 
	# because we're using dummy pointers
        node.prev.next = node_next
        node.next.prev = node_prev
        node.next = None
        node.prev = None
        self.size -= 1

    def front(self):
        if self.head.next == self.tail: return None
        return self.head.next

    def length(self):
        return self.size

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None
        self.prev = None