Doubly Linked List — Two Directions

In a singly linked list, each node only knows the next node. If you need to go backwards, you're stuck — you'd have to start over from the head. A doubly linked list solves this by giving each node two pointers: prev and next.

🔗
Key difference
Each node has prev, val, and next

A singly linked node stores val + next. A doubly linked node stores prev + val + next. This extra pointer costs more memory, but you gain the ability to traverse in both directions — and to delete a node in O(1) if you already have a reference to it.

dll_node.py Doubly linked list node
Output
Forward: [1, 2, 3] Backward: [3, 2, 1]

Doubly Linked List — Bidirectional Pointers

None
prev
1
next
head
prev
2
next
prev
3
next
tail
None
next pointer
prev pointer

DLL Operations — O(1) with Node Reference

The killer feature of a doubly linked list: if you already have a reference to a node, you can insert before/after it or delete it in O(1). No traversal needed. In a singly linked list, deletion requires knowing the previous node — which means O(n) traversal from the head.

dll_operations.py Insert and delete in O(1)
Output
1 <-> 3 1 <-> 2 <-> 3 1 <-> 3

Singly vs Doubly — when to use which?

OperationSingly LinkedDoubly Linked
Insert at headO(1)O(1)
Insert at tail (with tail ptr)O(1)O(1)
Delete a given nodeO(n) — need prevO(1) — has prev
Traverse backwardNot possibleO(n)
Memory per nodeval + 1 pointerval + 2 pointers
Interview insight:
Whenever a problem requires O(1) deletion with a node reference (like LRU Cache), you need a doubly linked list. A singly linked list can't do it — you'd have to traverse from the head to find the previous node.

Problem: LRU Cache

This is the classic interview problem for doubly linked lists. It appears at Google, Meta, Amazon, and nearly every top company. Design a data structure with these operations:

  • get(key) — return the value if the key exists, otherwise return -1. Mark the key as recently used.
  • put(key, value) — insert or update the key-value pair. If the cache exceeds capacity, evict the least recently used item.

Both operations must be O(1).

🧠
Key insight
Dict for O(1) lookup + DLL for O(1) ordering

A hash map alone gives O(1) lookup, but no ordering. A linked list alone gives ordering, but O(n) lookup. Combine them: the dict maps keys to nodes, and the DLL tracks usage order. Most recently used at the head, least recently used at the tail. When you access a key, remove its node and move it to the front. When you evict, remove the tail.

lru_cache.py O(1) get and put — LeetCode 146
Output
1 -1 -1 3 4
Why dummy head and tail?
Without dummy nodes, you'd need special-case logic for inserting at an empty list or removing the only node. Dummy nodes eliminate all edge cases — _remove and _add_to_front always have valid prev and next pointers. This is a common pattern in linked list interview problems.

Problem: Remove Nth Node from End

Given a linked list, remove the Nth node from the end and return the head. This is LeetCode 19 — a two-pointer classic.

The trick: Use two pointers with a gap of N between them. Advance the "fast" pointer N steps ahead, then move both pointers together until fast reaches the end. At that point, "slow" is right before the node to remove.

remove_nth.py Two pointers with gap — O(n)
Output
1 -> 2 -> 3 -> 5
Why a dummy node?
If N equals the list length, you're removing the head itself. The dummy node ensures slow always has a valid next to skip. Without it, you'd need a special case for head removal.

Problem: Palindrome Linked List

Given a singly linked list, determine if it's a palindrome. This is LeetCode 234. The challenge: do it in O(n) time and O(1) space — no arrays, no extra lists.

Strategy: Use fast/slow pointers to find the middle, reverse the second half in-place, then compare both halves node by node.

palindrome_list.py O(n) time, O(1) space
Output
True False True True
Three techniques in one problem:
Fast/slow pointers (to find the middle), linked list reversal (to flip the second half), and two-pointer comparison. Interviewers love this because it tests multiple skills at once.

Python's deque Under the Hood

collections.deque is Python's built-in doubly-ended queue. Under the hood, it's implemented as a doubly linked list of fixed-size blocks (each block holds ~64 items). This gives you O(1) for all four end operations:

  • append(x) — add to right end
  • appendleft(x) — add to left end
  • pop() — remove from right end
  • popleft() — remove from left end
deque_demo.py O(1) operations on both ends
Output
Start: [2, 3, 4] After adds: [1, 2, 3, 4, 5] After pops: [2, 3, 4] Rotate +2: [4, 5, 1, 2, 3] Rotate -3: [2, 3, 4, 5, 1] append(0): [0] append(1): [0, 1] append(2): [0, 1, 2] append(3): [1, 2, 3] append(4): [2, 3, 4]
deque vs list for queues:
list.pop(0) is O(n) because Python shifts every element. deque.popleft() is O(1). Always use deque for FIFO queues and BFS. For stacks (LIFO), a plain list is fine since list.pop() from the end is already O(1).

Try It Yourself

Simplified LRU Cache

Implement a simplified LRUCache class. It should support get(key) and put(key, value) with a fixed capacity. When the cache is full and a new key is added, evict the least recently used item. Test it with the provided calls.

Challenge

Flatten a Multilevel Doubly Linked List
Your task:

You have a doubly linked list where some nodes have a child pointer to another doubly linked list. Flatten the entire structure into a single-level doubly linked list. The child list should be inserted between the current node and its next node. (LeetCode 430)

Example: 1 <-> 2 <-> 3 where node 2 has child 7 <-> 8 becomes 1 <-> 2 <-> 7 <-> 8 <-> 3.

Hint approach: Use a stack or recursion. When you encounter a child, save next on a stack, splice in the child list, then continue.

Iterate through the list. When curr.child exists: (1) push curr.next onto a stack, (2) set curr.next = curr.child and curr.child.prev = curr, (3) clear curr.child = None. When curr.next is None and the stack is not empty, pop the saved node and link it. This is O(n) where n is the total number of nodes.

Quiz

Question 1 of 5
What advantage does a doubly linked list have over a singly linked list?
Question 2 of 5
In the LRU Cache, what two data structures are combined, and why?
Question 3 of 5
In the "Remove Nth from End" problem, why do we move the fast pointer N+1 steps ahead (not N)?
Question 4 of 5
How does the palindrome linked list solution achieve O(1) space?
Question 5 of 5
Why is collections.deque preferred over list for implementing a queue in Python?
0
/5
Great work! You understand doubly linked lists and advanced patterns.
Africa & India's Best AI Academy
🤖 AI-first 🎓 Placement Assistance

You've built an LRU Cache from scratch.
Now master every interview pattern.

Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.

Explore our AI-era courses →