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

In C++, vector is a dynamic array offering fast random access and efficient memory use, while list is a doubly linked list optimized for fast insertions and deletions anywhere but slower random access. Choose vector for most cases needing quick access and list when frequent insertions or deletions in the middle are required.

Quick Comparison

This table summarizes the main differences between vector and list in C++.

Factor	std::vector	std::list
Data Structure	Dynamic array	Doubly linked list
Access Speed	Fast random access (O(1))	Slow random access (O(n))
Insertion/Deletion	Fast at end, slow in middle (O(n))	Fast anywhere (O(1))
Memory Usage	Contiguous, less overhead	Non-contiguous, more overhead per element
Cache Performance	Better due to contiguous memory	Poorer due to scattered nodes
Use Case	When fast access and compact storage needed	When frequent insertions/deletions in middle needed

Key Differences

std::vector stores elements in a contiguous block of memory, like an array that can grow. This allows very fast access to any element by index, making it ideal when you need to read or write elements quickly. However, inserting or deleting elements in the middle requires shifting elements, which can be slow.

On the other hand, std::list is a doubly linked list where each element points to the next and previous. This means elements are scattered in memory, so accessing by index is slow because you must traverse nodes one by one. But inserting or deleting elements anywhere is fast because you only change pointers, not move other elements.

Memory-wise, vector uses less overhead since it stores elements contiguously, while list uses extra memory for pointers in each node. Also, vector benefits from better cache locality, making it faster in practice for many tasks.

Code Comparison

Here is how you 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 (size_t i = 0; i < numbers.size(); ++i) {
        std::cout << numbers[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

Output

10 20 30 

List Equivalent

Here is the same task done with 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 << std::endl;
    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 when memory efficiency and cache speed matter.

Choose std::list when your program frequently inserts or deletes elements in the middle of the sequence and random access speed is not important. This is common in complex data structures or algorithms that reorder elements often.

Key Takeaways

Use vector for fast random access and efficient memory use.

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

vector stores elements contiguously, improving cache performance.

list has slower access but constant-time insertions and deletions.

Pick the container based on your program's access and modification patterns.