Doubly Linked Lists

Analogy categoryAnalogies

Introduction

A doubly linked list extends the singly linked list by giving each node a reference to both the next node and the previous node. This bidirectional linking allows traversal in either direction and makes certain operations, such as deleting a given node or inserting before a node, more efficient because there is no need to keep a separate reference to the previous node during traversal.

🏏

Cricket analogy: Like a scorer's ledger that lets you flip forward to see the next over and backward to the previous over instantly, without re-reading the whole scorecard.

Structure/Syntax

python

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


class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

Explanation

Every DNode carries a prev and a next pointer, and the list tracks both a head and a tail reference. This design makes appending to the end O(1) because the tail is always directly reachable, and it makes deleting a known node O(1) because you can relink its prev and next neighbors without searching for them. The tradeoff is extra memory per node for the additional pointer and slightly more bookkeeping to keep prev/next consistent on every mutation.

🏏

Cricket analogy: Like a stadium keeping both the scoreboard's first and last entry pointers live, so adding the final ball's score or removing a no-ball is instant, at the cost of extra scoreboard wiring.

Example

python

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


class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def push_back(self, value):
        node = DNode(value)
        if self.tail is None:
            self.head = self.tail = node
        else:
            node.prev = self.tail
            self.tail.next = node
            self.tail = node
        self.size += 1

    def remove(self, node):
        if node.prev is not None:
            node.prev.next = node.next
        else:
            self.head = node.next
        if node.next is not None:
            node.next.prev = node.prev
        else:
            self.tail = node.prev
        self.size -= 1

    def to_list_forward(self):
        result = []
        current = self.head
        while current is not None:
            result.append(current.value)
            current = current.next
        return result


dll = DoublyLinkedList()
dll.push_back(1)
dll.push_back(2)
dll.push_back(3)
middle = dll.head.next
dll.remove(middle)
print(dll.to_list_forward())

Complexity

push_back is O(1) because the tail pointer is maintained directly. Removing a node given a direct reference to it is O(1) since both neighbors can be relinked without traversal. Searching for a value by content is still O(n) because there is no indexing. Space complexity is O(n) with roughly double the pointer overhead per node compared to a singly linked list.

🏏

Cricket analogy: Like adding the latest ball to the scoreboard is instant, removing a flagged no-ball once you know its position is instant, but finding which over a specific run was scored in still means scanning the whole card, and the card needs double the notation space.

Key Takeaways

Each node stores both a next and a prev pointer, enabling traversal in both directions.
Maintaining a tail pointer makes tail insertion O(1), unlike a plain singly linked list.
Deleting a node given a direct reference is O(1) since neighbors can be relinked without traversal.
Extra prev pointers increase memory usage per node compared to singly linked lists.
Doubly linked lists are commonly used to implement deques and LRU caches.

Practice what you learned

1. What extra field does a doubly linked list node have compared to a singly linked list node?

2. Given a direct reference to a node in a doubly linked list, what is the time complexity of removing it?

3. Why does a doubly linked list use more memory per node than a singly linked list?

4. In the example code, what happens to dll.tail when the last node in the list is removed?

Was this page helpful?

Singly Linked Lists

Circular Linked Lists

Topics covered

#Python#DataStructuresStudyNotes#DataStructures#DoublyLinkedLists#Doubly#Linked#Lists#Structure#StudyNotes#SkillVeris