std::list
Doubly linked list
Interview Relevant: Linked list implementation
std::list
Doubly linked list. O(1) insertion/deletion anywhere.
Code Examples
Doubly linked list operations.
cpp
1#include <list>
2
3list<int> lst = {3, 1, 4, 1, 5};
4
5// Add elements
6lst.push_back(9);
7lst.push_front(2);
8lst.insert(++lst.begin(), 7); // After first
9
10// Remove elements
11lst.pop_back();
12lst.pop_front();
13lst.remove(1); // Remove all 1s
14lst.remove_if([](int x) { return x > 4; });
15
16// Splice - move elements between lists
17list<int> lst2 = {10, 20};
18lst.splice(lst.end(), lst2); // Move lst2 to end of lst
19
20// List-specific operations (more efficient than algorithms)
21lst.sort();
22lst.unique(); // Remove consecutive duplicates
23lst.reverse();
24lst.merge(lst2); // Merge sorted lists
25
26// No random access! Must iterate
27// lst[0]; // Error!
28auto it = lst.begin();
29advance(it, 2); // Move iterator forward