List vs Vector in C++: Key Differences and When to Use Each

In C++, vector is a dynamic array that stores elements contiguously, offering fast random access and efficient memory use. list is a doubly linked list that allows fast insertions and deletions anywhere but slower access to elements by position.

Quick Comparison

Here is a quick side-by-side comparison of list and vector in C++ based on key factors.

Factor	std::vector	std::list
Storage	Contiguous memory array	Doubly linked nodes
Access speed	Fast random access (O(1))	Slow sequential access (O(n))
Insertion/deletion	Fast at end, slow in middle (O(n))	Fast anywhere (O(1))
Memory overhead	Low (just array)	Higher (extra pointers per node)
Use case	When fast access and cache efficiency matter	When frequent insertions/deletions in middle happen
Iterator invalidation	Insertions may invalidate iterators	Insertions/deletions do not invalidate other iterators

Key Differences

std::vector stores elements in a continuous block of memory, similar to an array that can grow. This allows very fast access to any element by index because the memory location is predictable. However, inserting or deleting elements in the middle requires shifting elements, which can be slow.

On the other hand, std::list uses a doubly linked list structure where each element points to the next and previous. This means elements are scattered in memory, so accessing by position is slower because you must follow links. But inserting or deleting elements anywhere is fast since it only changes pointers.

Memory usage also differs: vector uses less memory because it only stores elements, while list stores extra pointers for each node. Finally, iterator invalidation rules differ: vector iterators can be invalidated by insertions or deletions, but list iterators remain valid except for the erased elements.

Code Comparison

This example shows how to add elements and print them using std::vector.

cpp

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers;
    numbers.push_back(10);
    numbers.push_back(20);
    numbers.push_back(30);

    for (int num : numbers) {
        std::cout << num << ' ';
    }
    std::cout << '\n';
    return 0;
}

Output

10 20 30 

List Equivalent

This example shows the same task using std::list.

cpp

#include <iostream>
#include <list>

int main() {
    std::list<int> numbers;
    numbers.push_back(10);
    numbers.push_back(20);
    numbers.push_back(30);

    for (int num : numbers) {
        std::cout << num << ' ';
    }
    std::cout << '\n';
    return 0;
}

Output

10 20 30 

When to Use Which

Choose std::vector when you need fast random access to elements and your program mostly adds or removes elements at the end. It is also better for memory efficiency and cache performance.

Choose std::list when your program frequently inserts or deletes elements in the middle of the sequence and you don't need fast random access. It is ideal when iterator stability is important during modifications.

Key Takeaways

Use vector for fast random access and efficient memory use.

Use list for frequent insertions and deletions anywhere in the sequence.

Vectors store elements contiguously; lists use linked nodes with extra memory overhead.

Iterator invalidation is less of a concern with lists during insertions and deletions.

Choose based on your need for access speed versus modification flexibility.