Doubly Linked Lists and Python's deque

What you'll walk away with

Explain the core ideas behind Doubly Linked Lists and Python's deque
Run the sample Python code and verify its output
Apply the technique correctly to the Tutorial Platform and production scenarios

Build the mental model

In a singly linked list, each node only points forward, so removing the last element still requires walking from the head to find its predecessor — O(n). A doubly linked list fixes this by giving every node a `prev` pointer alongside `next`, so from any node you can reach its neighbor in either direction in O(1), which means insertion and removal at both ends of the list are O(1). You rarely implement this by hand in Python because `collections.deque` already is one — it's built on a doubly linked structure internally, so `append`, `appendleft`, `pop`, and `popleft` are all O(1). That makes deque the theoretically correct choice — not just a convenience — whenever both ends of a sequence matter: queues, stacks, sliding windows, or a bounded recent-history buffer, all of which a plain Python list handles poorly at one end or the other.

Connect it to a real scenario

The Tutorial Platform's 'Recently Viewed Lessons' panel can be built directly on a deque — each newly opened lesson gets pushed to the front with appendleft(), and with maxlen set, the oldest entry automatically falls off the back, all in O(1).

Each node stores both next and prev, so navigation works in either direction in O(1)
Python's deque is built on a doubly linked structure, giving O(1) append/pop from both ends
A plain list's pop(0) is O(n) because every remaining element must shift left

Try the working example

python

from collections import deque

# deque is a doubly linked list under the hood, so both ends are O(1)
recent_lessons = deque(maxlen=3)

recent_lessons.append("intro")        # add to right end - O(1)
recent_lessons.append("variables")
recent_lessons.appendleft("welcome")  # add to left end - O(1), no shifting
print(list(recent_lessons))

recent_lessons.pop()      # remove from right end - O(1)
recent_lessons.popleft()  # remove from left end - O(1)
print(list(recent_lessons))

# Contrast: a plain list's pop(0) is O(n) because every remaining
# element must shift left by one to fill the gap.

You should see

The first print shows ["welcome", "intro", "variables"]; after calling pop() and popleft(), the second print shows ["intro"].

5-minute try-it

Rewrite the code using a plain Python list with insert(0, ...) and pop(0) instead — the result is the same, but reason about why it gets slower as the number of elements grows.

One important caution

Implementing a recent-history buffer with a plain list and `list.insert(0, item)` — every element has to shift, making it O(n) instead of O(1)

Assuming deque supports fast random access like an array — indexing into the middle (`d[5]`) is O(n) because of the underlying linked structure, unlike a list's O(1) indexing

Python Docs — collections.deque — Data Structures & Algorithms

Easy traps

Implementing a recent-history buffer with a plain list and `list.insert(0, item)` — every element has to shift, making it O(n) instead of O(1)
Assuming deque supports fast random access like an array — indexing into the middle (`d[5]`) is O(n) because of the underlying linked structure, unlike a list's O(1) indexing
Validate sample code in a local or test environment before applying it to a production system.

Exercise

Rewrite the code using a plain Python list with insert(0, ...) and pop(0) instead — the result is the same, but reason about why it gets slower as the number of elements grows.

You'll know it worked when: The first print shows ["welcome", "intro", "variables"]; after calling pop() and popleft(), the second print shows ["intro"].