DataslopeDoubly Linked Lists and std::list
Learn previous and next pointers, bidirectional traversal, std::list iterators, splicing use cases, and cycle detection patterns
A doubly linked list gives every node two links: prev and next. That extra pointer allows bidirectional traversal and O(1) deletion when you already have a pointer or iterator to the node.
The shape of a doubly linked list
A singly linked list can move forward only. A doubly linked list can walk backward from the tail.
A tiny implementation
This class keeps both head and tail, so pushing at either end is O(1). It also frees nodes in the destructor.
Deletion when you have the node
If you already have a pointer to a middle node, a doubly linked list can unlink it by changing the neighboring prev and next links. Finding that node by value is still O(n).
std::list
std::list<T> is the STL doubly linked list. It has stable iterators: inserting or erasing elsewhere does not invalidate iterators to other elements. It does not support random access with list[i].
When should you choose std::list?
Almost never as a default. std::vector or std::deque usually wins because contiguous or block-based storage is much more cache-friendly. Choose std::list only when its special properties matter.
| Good reason | Why it matters |
|---|---|
splice | Move nodes between lists in O(1) without copying values |
| stable iterators | Keep references to nodes while inserting elsewhere |
| frequent known-position insert/erase | You already have the iterator, so no search cost |
Iterator-based erase
With std::list, erasing through an iterator returns the next iterator, which is handy while filtering.
Big-O can hide cache costs
A list may advertise O(1) insertion once you have an iterator, but walking to that iterator and chasing scattered nodes can dominate runtime.
Practice: print backward
Walk from tail to head using prev pointers and print each value on its own line.
Practice: detect a cycle
Implement Floyd's slow/fast pointer algorithm in hasCycle. The driver builds a small cycled list and prints the result.
Check your understanding
What extra link does a doubly linked list node store compared with a singly linked list node?
A pointer to the head of the whole program
A pointer to the previous node
A copy of every earlier value
A random-access index table
Which statement about std::list is true?
It has stable iterators for elements not erased, but it does not support random access.
It is always faster than std::vector for iteration.
It stores all values contiguously.
It can only store integers.
When is std::list most defensible?
When you need millions of random index lookups
When you want the best cache locality for scanning
When you rely on splice operations or stable iterators.
When values must be sorted automatically