std::list in C++: Doubly Linked Storage and List Operations
What is std::list in C++: Doubly Linked Storage and List Operations? std::list is a sequence container implemented as a doubly linked list. Each node contains a data element and two pointers (prev and next). It allows $O(1)$ cons...
How does std::list work internally, and when should it be preferred over std::vector?
Explanation & In-Depth Details
```text
┌──────────────┐ ┌──────────────┐ ┌──────────────┐
│ [prev|10|next]│◄───►│ [prev|20|next]│◄───►│ [prev|30|next]│
└──────────────┘ └──────────────┘ └──────────────┘
```
2. Dedicated List Algorithms:
`std::list` provides member algorithms like `.sort()`, `.splice()`, `.merge()`, and `.reverse()` because standard algorithms requiring random-access iterators (like `std::sort`) cannot operate on linked lists.
Code Example
#include <iostream>
#include <list>
int main() {
std::list<int> taskQueue = {101, 102, 105};
// Insert at front and back in O(1)
taskQueue.push_front(100);
taskQueue.push_back(106);
// Insert in the middle without moving other elements
auto it = taskQueue.begin();
std::advance(it, 3); // Move to 105
taskQueue.insert(it, 103);
std::cout << "Task Queue: ";
for (int t : taskQueue) std::cout << t << " ";
std::cout << "\n";
// Fast O(1) node splicing
std::list<int> urgentTasks = {999};
taskQueue.splice(taskQueue.begin(), urgentTasks);
std::cout << "After Splicing Urgent Task: ";
for (int t : taskQueue) std::cout << t << " ";
std::cout << "\n";
return 0;
}Interview Question & Tips
A: No. Iterators and references to other elements remain valid because nodes are allocated individually on the heap and do not move in memory.
Q: Why doesn't `std::sort(list.begin(), list.end())` work on `std::list`?
A: `std::sort` requires RandomAccessIterator, whereas `std::list` only provides BidirectionalIterator. Use `list.sort()` instead.
Best Practices
• Use `.splice()` to transfer elements between lists in $O(1)$ without copying or memory reallocations.
• Do not use `std::list` for small primitive elements where cache-friendly `std::vector` outperforms it.
This study reference for std::list in C++: Doubly Linked Storage and List Operations is curated and verified against recognized curriculum benchmarks, peer-reviewed textbooks, and official technical documentation: