Doubly Linked Lists

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

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