Problem Statement

Why Vector Traversal Is Faster Than List Traversal Traversing a `std::list<int>` of 10 million nodes is several times slower than traversing a `std::vector<int>` of the same size, even though both are O(n). What is the dominant reason? The list stores larger elements. The compiler cannot inline list iterators. Pointer chasing through scattered heap nodes defeats cache locality and hardware prefetching. Lists require a mutex per node.