C++: What is the difference between vector and list in C++?

vector — dynamic array. list — doubly linked list.

vector:

• Contiguous memory.
• Random access O(1).
• Insert/delete at end O(1) amortized.
• Insert/delete in middle O(n).
• Cache-friendly.

1std::vector<int> v = {1, 2, 3};
2v.push_back(4);
3v[2] = 10;  // Random access

list:

• Non-contiguous memory (nodes).
• Sequential access O(n).
• Insert/delete anywhere O(1).
• Cache-unfriendly.

1std::list<int> l = {1, 2, 3};
2l.push_back(4);
3// l[2] = 10;  // Error! No random access
4auto it = std::next(l.begin(), 2);
5*it = 10;

When to use:

• vector — most cases, random access needed.
• list — frequent insert/delete in middle.