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)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.tail
        self.tail.prev = self.head
        self.size = 0

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

        return node

    def delete(self, node):
        node_prev, node_next = node.prev,
	# 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_next = node_prev = None
        node.prev = None
        self.size -= 1

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

    def length(self):
        return self.size

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

Last updated