icaoberg / Data structures - Doubly Linked List

Created Sun, 03 May 2026 00:00:00 +0000 Modified Sun, 03 May 2026 09:38:16 -0400

Jupyter Notebook python

Data structures - Doubly Linked List¶

A doubly linked list is a linear data structure where each node stores a value and two pointers — one to the next node and one to the previous node. This bidirectional linkage allows O(1) insertion and deletion at both ends, as well as efficient backward traversal, at the cost of one extra pointer per node.

This notebook covers:

What is a Doubly Linked List?
The Node and DoublyLinkedList classes
Core operations: append, prepend, insert_after, delete, search, size
Example: browser history manager

1. What is a Doubly Linked List?¶

       head                                              tail
         │                                                 │
         ▼                                                 ▼
  +------+------+------+   +------+------+------+   +------+------+------+
  | None |  A   |   ●──┼──►|  ●   |  B   |   ●──┼──►|  ●   |  C   | None |
  +------+------+------+   +------+------+------+   +------+------+------+
             ◄──────────────────┤              ◄──────────────────┤
              prev pointers                    prev pointers

Each node holds:

data — the stored value
next — pointer to the next node (None at the tail)
prev — pointer to the previous node (None at the head)

Operation	Time
Append / Prepend	O(1)
Insert after node	O(1)
Delete (with reference)	O(1)
Search	O(n)
Random access	O(n)

2. The `Node` and `DoublyLinkedList` classes¶

In [1]:

class Node:
    """A single node in a doubly linked list."""

    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

    def __repr__(self):
        return f"Node({self.data!r})"


class DoublyLinkedList:
    """Doubly linked list with head and tail pointers."""

    def __init__(self):
        self.head = None
        self.tail = None
        self._size = 0

    # ------------------------------------------------------------------
    # Insertion
    # ------------------------------------------------------------------

    def append(self, data):
        """Add a node at the tail — O(1)."""
        node = Node(data)
        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 prepend(self, data):
        """Add a node at the head — O(1)."""
        node = Node(data)
        if self.head is None:
            self.head = self.tail = node
        else:
            node.next = self.head
            self.head.prev = node
            self.head = node
        self._size += 1

    def insert_after(self, target_data, new_data):
        """Insert new_data immediately after the first node with target_data."""
        current = self.head
        while current:
            if current.data == target_data:
                node = Node(new_data)
                node.prev = current
                node.next = current.next
                if current.next:
                    current.next.prev = node
                else:
                    self.tail = node
                current.next = node
                self._size += 1
                return
            current = current.next
        raise ValueError(f"{target_data!r} not found")

    # ------------------------------------------------------------------
    # Deletion
    # ------------------------------------------------------------------

    def delete(self, data):
        """Remove the first node with the given data — O(n) search, O(1) unlink."""
        current = self.head
        while current:
            if current.data == data:
                if current.prev:
                    current.prev.next = current.next
                else:
                    self.head = current.next
                if current.next:
                    current.next.prev = current.prev
                else:
                    self.tail = current.prev
                self._size -= 1
                return
            current = current.next
        raise ValueError(f"{data!r} not found")

    # ------------------------------------------------------------------
    # Query
    # ------------------------------------------------------------------

    def search(self, data):
        """Return the first node matching data, or None."""
        current = self.head
        while current:
            if current.data == data:
                return current
            current = current.next
        return None

    def size(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    # ------------------------------------------------------------------
    # Traversal
    # ------------------------------------------------------------------

    def to_list(self):
        """Return elements as a list (forward order)."""
        result, current = [], self.head
        while current:
            result.append(current.data)
            current = current.next
        return result

    def to_list_reversed(self):
        """Return elements as a list (backward order) using prev pointers."""
        result, current = [], self.tail
        while current:
            result.append(current.data)
            current = current.prev
        return result

    def __repr__(self):
        items = " ⟺ ".join(str(x) for x in self.to_list())
        return f"[{items}]"

    def __len__(self):
        return self._size

3. Core operations¶

In [2]:

dll = DoublyLinkedList()
print("Empty?  ", dll.is_empty())
print("List:   ", dll)

for v in ["B", "C", "D"]:
    dll.append(v)
    print(f"append({v!r})    →  {dll}")

dll.prepend("A")
print(f"prepend('A')  →  {dll}")
print(f"reversed:     {dll.to_list_reversed()}")

Empty?   True
List:    []
append('B')    →  [B]
append('C')    →  [B ⟺ C]
append('D')    →  [B ⟺ C ⟺ D]
prepend('A')  →  [A ⟺ B ⟺ C ⟺ D]
reversed:     ['D', 'C', 'B', 'A']

In [3]:

dll.insert_after("B", "B2")
print(f"insert_after('B', 'B2')  →  {dll}")

insert_after('B', 'B2')  →  [A ⟺ B ⟺ B2 ⟺ C ⟺ D]

In [4]:

print("search('C'):  ", dll.search("C"))
print("search('Z'):  ", dll.search("Z"))
print("size():       ", dll.size())

search('C'):   Node('C')
search('Z'):   None
size():        5

In [5]:

dll.delete("B2")
print(f"delete('B2')  →  {dll}")

dll.delete("A")   # head deletion
print(f"delete('A')   →  {dll}")

dll.delete("D")   # tail deletion
print(f"delete('D')   →  {dll}")

delete('B2')  →  [A ⟺ B ⟺ C ⟺ D]
delete('A')   →  [B ⟺ C ⟺ D]
delete('D')   →  [B ⟺ C]

In [6]:

try:
    dll.delete("Z")
except ValueError as e:
    print("Caught:", e)

try:
    dll.insert_after("Z", "X")
except ValueError as e:
    print("Caught:", e)

Caught: 'Z' not found
Caught: 'Z' not found

4. Example: browser history manager¶

A doubly linked list is a natural fit for browser history: the prev pointer enables the Back button and the next pointer enables the Forward button. Navigating to a new page discards the forward stack.

In [7]:

class BrowserHistory:
    """Browser back/forward history backed by a DoublyLinkedList."""

    def __init__(self, homepage):
        self._history = DoublyLinkedList()
        self._history.append(homepage)
        self._current = self._history.tail

    # -- navigation ---------------------------------------------------

    def visit(self, url):
        """Navigate to url, discarding any forward history."""
        # Truncate forward history
        node = self._current.next
        while node:
            nxt = node.next
            self._history.delete(node.data)
            node = nxt
        self._history.append(url)
        self._current = self._history.tail

    def back(self, steps=1):
        """Move back up to `steps` pages; return the resulting URL."""
        for _ in range(steps):
            if self._current.prev:
                self._current = self._current.prev
        return self._current.data

    def forward(self, steps=1):
        """Move forward up to `steps` pages; return the resulting URL."""
        for _ in range(steps):
            if self._current.next:
                self._current = self._current.next
        return self._current.data

    # -- inspection ---------------------------------------------------

    @property
    def current(self):
        return self._current.data

    def full_history(self):
        return self._history.to_list()

    def __repr__(self):
        return f"BrowserHistory(current={self.current!r})"

In [8]:

bh = BrowserHistory("https://example.com")
print("Start:   ", bh.current)

bh.visit("https://news.ycombinator.com")
bh.visit("https://python.org")
bh.visit("https://docs.python.org/3/")
print("After visits:", bh.full_history())
print("Current:     ", bh.current)

print("Back 1:      ", bh.back(1))
print("Back 2:      ", bh.back(2))
print("Forward 1:   ", bh.forward(1))

# Visiting a new page should discard forward history
bh.visit("https://realpython.com")
print("After new visit:", bh.full_history())
print("Current:        ", bh.current)

# Can't go forward — no forward history
print("Forward (no-op):", bh.forward(5))

Start:    https://example.com
After visits: ['https://example.com', 'https://news.ycombinator.com', 'https://python.org', 'https://docs.python.org/3/']
Current:      https://docs.python.org/3/
Back 1:       https://python.org
Back 2:       https://example.com
Forward 1:    https://news.ycombinator.com
After new visit: ['https://example.com', 'https://news.ycombinator.com', 'https://realpython.com']
Current:         https://realpython.com
Forward (no-op): https://realpython.com

Licensed under the GNU General Public License v2.0 (GPL-2).
You may redistribute and/or modify this work under the terms of GPL-2.
This work is distributed WITHOUT ANY WARRANTY.
Happy computing.