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.
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.
Doubly Linked List — Bidirectional Pointers
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.
Singly vs Doubly — when to use which?
| Operation | Singly Linked | Doubly Linked |
|---|---|---|
| Insert at head | O(1) | O(1) |
| Insert at tail (with tail ptr) | O(1) | O(1) |
| Delete a given node | O(n) — need prev | O(1) — has prev |
| Traverse backward | Not possible | O(n) |
| Memory per node | val + 1 pointer | val + 2 pointers |
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).
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.
_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.
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.
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 endappendleft(x)— add to left endpop()— remove from right endpopleft()— remove from left end
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
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.
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
collections.deque preferred over list for implementing a queue in Python?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 →