When to Prefer List Instead of Vector?
Vectors are sequence containers that store the data in the contiguous memory location. This allows us to directly access the element at any position in O(1) time. Whereas, lists are also a sequential container but they store data in non-contiguous memory locations. Here, each element contains the location of the next element in the sequence. To access an element inside the list, we have to go through all the elements before that element leading to the time complexity of O(N).
This difference leads to many cases where it is advantageous to use one container instead of the other. The following are a few such cases where using std::list
in place of std::vector
is more advantageous:
1. Frequent Insertions and Deletions at Both Ends
In std::list, we can efficiently perform insertions and deletions at both ends which makes it a suitable choice when we need a data structure that frequently inserts or deletes elements not only at the end but also at the beginning.
Example:
The below program illustrates the use of a std::list for frequent insertions and deletions at both ends.
// C++ program to illustrate the use of list for
// frequent insertions and deletions at both ends
#include <iostream>
#include <list>
using namespace std;
int main()
{
// Initialize a list of integers
list<int> nums = { 1, 2, 3, 4, 5 };
// Insert at the beginning
nums.push_front(0);
// Delete from the end
nums.pop_back();
// Print the list
for (int num : nums) {
cout << num << " ";
}
cout << endl;
return 0;
}
Output
0 1 2 3 4
2. Frequent Insertions and Deletions in the Middle
The std::list allows efficient insertions and deletions in the middle of the list, while std::vector does not because std::vector needs to shift all elements after the insertion or deletion point, which can be costly for large vectors. so, std::list
is a better choice.
Example:
The below program illustrates the use of list for frequent insertions and deletions in the middle.
// C++ program to illustrate the use of list for
// frequent insertions and deletions in the middle
#include <iostream>
#include <list>
using namespace std;
int main()
{
// Initialize a list of integers
list<int> nums = { 1, 2, 3, 4, 5 };
// Insert in the middle
auto it = nums.begin();
advance(it, 2);
nums.insert(it, 0);
// Delete from the middle
it = nums.begin();
advance(it, 2);
nums.erase(it);
// Print the list
for (int num : nums) {
cout << num << " ";
}
cout << endl;
return 0;
}
Output
1 2 3 4 5
3. No Random Access Required
The std::list
does not support random access so, if the program does not need to access elements by their index and only requires iterating over the elements, std::list can be a better choice as it provides efficient iteration.
Example:
The below program illustrates the use of list when there is no need for random access.
// C++ program to illustrate the use of list when
// there is no need for random access
#include <iostream>
#include <list>
using namespace std;
int main()
{
// Initialize a list of integers
list<int> nums = { 1, 2, 3, 4, 5 };
// Access elements using an iterator
for (auto it = nums.begin(); it != nums.end(); ++it) {
cout << *it << " ";
}
cout << endl;
return 0;
}
Output
1 2 3 4 5
4. Large Elements
If the elements are large, inserting or deleting elements in a std::vector can be costly as it involves copying or moving elements. In such cases, std::list can be a better choice as it only involves updating pointers of the neighboring elements, which is a constant time operation regardless of the size of the elements.
When to Use List Instead of Vector in C++?
In C++, both std::vector and std::list are sequence containers that can store a collection of elements. However, they have different characteristics and use cases. In this article, we will learn when to use a list instead of a vector in C++.