The list container in the C++ Standard Template Library (STL) is a doubly linked list.
Unlike arrays or vectors, list allows fast insertion and deletion at both ends, as well as in the middle, without reallocating or shifting elements.
It’s ideal for situations where frequent insertions or deletions are needed but random access is not a priority.
Key Features of list
- Doubly Linked List: Supports forward and backward traversal.
- Efficient Insertions and Deletions: Operations at the front, back, or middle are efficient.
- Bidirectional Traversal: Supports reverse iterators.
Basic Syntax
#include <list> using namespace std; list<int> lst;
Let’s explore common operations and examples to understand how list works.
1. Initializing a list
A list can be initialized with default values, a specified size, or with an initializer list.
#include <iostream>
#include <list>
using namespace std;
int main() {
// Empty list
list<int> lst1;
// Initialize with values
list<int> lst2 = {10, 20, 30, 40, 50};
// Display elements
cout << "Elements in lst2: ";
for (int val : lst2) {
cout << val << " ";
}
cout << endl;
return 0;
}
Output:
Elements in lst2: 10 20 30 40 50
2. Adding Elements
list supports push_front and push_back for adding elements to the front and back, respectively. emplace_front and emplace_back can also be used for in-place construction.
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> lst = {20, 30, 40};
// Add elements at the front and back
lst.push_front(10);
lst.push_back(50);
cout << "Elements after push_front and push_back: ";
for (int val : lst) {
cout << val << " ";
}
cout << endl;
return 0;
}
Output:
Elements after push_front and push_back: 10 20 30 40 50
3. Inserting Elements at Specific Positions
The insert function allows insertion at specific positions within the list.
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> lst = {10, 20, 40};
// Insert 30 at the second position
auto it = lst.begin();
advance(it, 2);
lst.insert(it, 30);
cout << "Elements after insertion: ";
for (int val : lst) {
cout << val << " ";
}
cout << endl;
return 0;
}
Output:
Elements after insertion: 10 20 30 40
4. Removing Elements
You can remove elements using pop_front and pop_back. The remove function removes all occurrences of a specific value, while erase removes elements at a specific position.
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> lst = {10, 20, 30, 40, 50, 30};
// Remove first and last elements
lst.pop_front();
lst.pop_back();
// Remove all occurrences of 30
lst.remove(30);
cout << "Elements after removals: ";
for (int val : lst) {
cout << val << " ";
}
cout << endl;
return 0;
}
Output:
Elements after removals: 20 40
5. Accessing Elements
list does not support random access (no [] operator or at function), so you must use iterators to access elements.
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> lst = {10, 20, 30, 40, 50};
cout << "Elements: ";
for (auto it = lst.begin(); it != lst.end(); ++it) {
cout << *it << " ";
}
cout << endl;
return 0;
}
Output:
Elements: 10 20 30 40 50
6. Resizing a list
The resize function changes the number of elements in the list. If the new size is greater, new elements are added with a specified default value; if smaller, extra elements are removed.
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> lst = {10, 20, 30};
// Resize to larger size with default value 0
lst.resize(5, 0);
cout << "Elements after resizing to 5: ";
for (int val : lst) {
cout << val << " ";
}
cout << endl;
// Resize to smaller size
lst.resize(2);
cout << "Elements after resizing to 2: ";
for (int val : lst) {
cout << val << " ";
}
cout << endl;
return 0;
}
Output:
Elements after resizing to 5: 10 20 30 0 0 Elements after resizing to 2: 10 20
7. Sorting a list
The sort function sorts elements in ascending order.
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> lst = {50, 10, 40, 30, 20};
// Sorting the list
lst.sort();
cout << "Elements after sorting: ";
for (int val : lst) {
cout << val << " ";
}
cout << endl;
return 0;
}
Output:
Elements after sorting: 10 20 30 40 50
8. Reversing a list
The reverse function reverses the order of elements in the list.
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> lst = {10, 20, 30, 40, 50};
// Reversing the list
lst.reverse();
cout << "Elements after reversing: ";
for (int val : lst) {
cout << val << " ";
}
cout << endl;
return 0;
}
Output:
Elements after reversing: 50 40 30 20 10
9. Merging Two lists
The merge function merges two sorted lists into one sorted list. Both lists must be sorted beforehand.
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> lst1 = {10, 30, 50};
list<int> lst2 = {20, 40, 60};
// Merging two sorted lists
lst1.merge(lst2);
cout << "Merged list: ";
for (int val : lst1) {
cout << val << " ";
}
cout << endl;
return 0;
}
Output:
Merged list: 10 20 30 40 50 60
10. Splicing Elements from One List to Another
The splice function transfers elements from one list to another at a specified position.
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> lst1 = {10, 20, 30};
list<int> lst2 = {40, 50, 60};
// Splicing lst2 into lst1 after the first element
auto it = lst1.begin();
++it;
lst1.splice(it, lst2);
cout << "List 1 after splicing: ";
for (int val : lst1) {
cout << val << " ";
}
cout << endl;
cout << "List 2 after splicing (should be empty): ";
for (int val : lst2) {
cout << val << " ";
}
cout << endl;
return 0;
}
Output:
List 1 after splicing: 10 40 50 60 20 30 List 2 after splicing (should be empty):
Summary Table of list Operations
| Operation | Code Example | Description |
|---|---|---|
| Initialize | list<int> lst = {10, 20, 30}; | Creates a list with initial values |
| Add at front | lst.push_front(5); | Adds an element to the front |
| Add at back | lst.push_back(50); | Adds an element to the back |
| Insert at position | lst.insert(it, 25); | Inserts element at a specified position |
| Remove from front | lst.pop_front(); | Removes the first element |
| Remove from back | lst.pop_back(); | Removes the last element |
| Remove specific value | lst.remove(30); | Removes all occurrences of a specified value |
| Clear | lst.clear(); | Removes all elements |
| Resize | lst.resize(5, 100); | Resizes list, fills new slots with default value |
| Sort | lst.sort(); | Sorts elements in ascending order |
| Reverse | lst.reverse(); | Reverses the order of elements |
| Merge | lst1.merge(lst2); | Merges two sorted lists |
| Splice | lst1.splice(it, lst2); | Transfers elements from lst2 into lst1 |
Complete Example
This example demonstrates initializing a list, adding and removing elements, sorting, reversing, merging, and splicing.
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> lst1 = {10, 20, 30};
list<int> lst2 = {15, 25, 35};
// Add elements
lst1.push_front(5);
lst1.push_back(40);
cout << "List 1 after adding elements: ";
for (int val : lst1) {
cout << val << " ";
}
cout << endl;
// Sort and reverse
lst1.sort();
lst1.reverse();
cout << "List 1 after sorting and reversing: ";
for (int val : lst1) {
cout << val << " ";
}
cout << endl;
// Merge with another sorted list
lst1.sort();
lst2.sort();
lst1.merge(lst2);
cout << "List 1 after merging with List 2: ";
for (int val : lst1) {
cout << val << " ";
}
cout << endl;
// Splice elements
list<int> lst3 = {50, 60};
auto it = lst1.begin();
advance(it, 3);
lst1.splice(it, lst3);
cout << "List 1 after splicing with List 3: ";
for (int val : lst1) {
cout << val << " ";
}
cout << endl;
return 0;
}
Sample Output:
List 1 after adding elements: 5 10 20 30 40 List 1 after sorting and reversing: 40 30 20 10 5 List 1 after merging with List 2: 5 10 15 20 25 30 35 40 List 1 after splicing with List 3: 5 10 15 50 60 20 25 30 35 40
Key Takeaways
- list is a doubly linked list, suitable for efficient insertions and deletions.
- It allows bidirectional traversal with iterators, supporting operations like insertion, deletion, sorting, reversing, merging, and splicing.
- list is ideal when random access isn’t needed, and you need frequent modifications at both ends or in the middle.