Data Structures
Doubly Linked List
Difficulty: Intermediate
Deleting a node from a singly linked list when you only hold a pointer to that node is genuinely awkward: you need the previous node too, and finding it is O(n). Add a prev pointer to every node and the same delete becomes four pointer...
Doubly Linked List
Deleting a node from a singly linked list when you only hold a pointer to that node is genuinely awkward: you need the previous node too, and finding it is O(n). Add a prev pointer to every node and the same delete becomes four pointer rewires in O(1), which is exactly the upgrade that powers LRU caches and the browser back-forward stack.
This lesson covers the Doubly Linked List node layout (value, next, prev), bidirectional traversal, insertion at head and tail and after a given node, deletion by node reference and by value, and the sentinel (dummy head and tail) pattern that eliminates almost all null-check edge cases in pointer-heavy code. You will also weigh the per-node memory cost of the extra pointer against the operations it unlocks.
In Linked Lists (Singly), head insertion was already O(1) but mid-list deletion required carrying a trailing pointer during traversal. The doubly linked list removes that constraint: every node knows its predecessor, so you can splice it out without any extra bookkeeping.
Next, Circular Linked List keeps a single direction of links but bends the list back on itself, which turns out to be the right shape for round-robin scheduling and circular buffers.
Prerequisites:
Linked Lists (Singly)Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Describe the doubly linked list node structure (value + next + prev) and explain how bidirectional links differ from a singly linked list.
Implement insertion at head, tail, and after a given node with correct prev/next pointer management in both JavaScript and Python.
Implement deletion by node reference in O(1) and deletion by value in O(n), handling all edge cases.
Traverse a doubly linked list in both forward and backward directions.
Apply the sentinel (dummy head/tail) pattern to simplify insertion and deletion code.
Compare doubly and singly linked lists in terms of time complexity, space overhead, and appropriate use cases.
Why This Matters
01
Doubly linked lists unlock O(1) deletion by node reference, a capability singly linked lists lack, which is essential for building efficient caches and editors.
02
They are the foundation for the classic LRU Cache interview problem (LeetCode 146), which combines a hash map with a doubly linked list for O(1) get and put.
03
Understanding the sentinel (dummy head/tail) pattern eliminates null-check edge cases and is a recurring trick in pointer-heavy interview questions.
04
Bidirectional traversal enables efficient undo/redo, browser forward/back navigation, and ordered iterator patterns used in real-world systems.
Key Terms
6 terms you'll encounter in this lesson
Doubly linked list
A linked list where each node stores a value, a pointer to the next node, and a pointer to the previous node, enabling bidirectional traversal.
prev pointer
A reference in each node pointing to the preceding node in the list. The head's prev is null/None (or a sentinel).
Sentinel node (dummy node)
A special placeholder node at the head and/or tail of a list that contains no real data. Sentinels eliminate null-check edge cases in insertion and deletion logic.
Bidirectional traversal
The ability to walk through a list in both forward (head to tail via next) and backward (tail to head via prev) directions.
Deletion by reference
Removing a node from the list when you already hold a direct pointer/reference to that node, achievable in O(1) by rewiring prev and next pointers.
LRU Cache
A Least Recently Used cache that evicts the least-recently-accessed item when full. Typically implemented with a hash map + doubly linked list for O(1) operations.
Heads Up
Common misconceptions to watch out for
"Deletion is always O(1) in a doubly linked list"
Deletion is O(1) only when you already have a reference to the node. If you need to find the node by value first, that search is O(n), making the overall operation O(n).
"A doubly linked list uses the same memory as a singly linked list"
Each DLL node stores an extra prev pointer, roughly doubling the pointer overhead. For a list of n nodes, a DLL uses n extra pointer-sized allocations (8 bytes each on 64-bit systems).
"Sentinels are required for a doubly linked list"
Sentinels are optional but highly recommended. Without them, every insertion and deletion function needs special-case null checks for the head and tail. Sentinels simplify the code but add two extra nodes of memory.
"Backward traversal means the list is stored in reverse"
The data is stored in the same order as a singly linked list. The prev pointers simply provide a backward reference, they do not change the logical order of elements.