C++ std::list & forward_list: Doubly vs Singly Linked List Architecture

std::list is a sequence container implemented as a Doubly Linked List, while std::forward_list (C++11) is a lightweight Singly Linked List with zero memory overhead per node.

Example: Splice and In-Place Removal

#include <iostream>
#include <list>

int main() {
    std::list<int> values = {10, 25, 30, 25, 40};

    // Remove all occurrences of 25 in O(N) time with zero reallocation
    values.remove(25);

    for (int v : values) {
        std::cout << v << " ";
    }
    // Output: 10 30 40
    std::cout << "\n";
    return 0;
}

Frequently Asked Questions (FAQ) - Student & Interview Review

Q1. Why is std::vector usually faster than std::list even for insertions?

Because modern CPU hardware relies heavily on L1/L2/L3 cache prefetching. Vector's contiguous memory keeps elements right next to each other in cache. std::list stores each element in a separate heap node with pointers, causing frequent CPU cache misses and RAM latency.

Q2. When SHOULD you use std::list?

Use std::list when you require guaranteed O(1) insertions or deletions anywhere in the sequence without invalidating other iterators, or when you need zero-copy list splicing (list.splice()).