C++ List
Understanding doubly-linked list containers
📋 What is C++ List?
C++ List is a doubly-linked list container that allows efficient insertion and deletion at any position. Unlike vectors, lists don't provide random access but excel at frequent insertions and deletions.
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> myList = {1, 2, 3, 4, 5};
for(int num : myList) {
cout << num << " ";
}
return 0;
}
Output:
1 2 3 4 5
Key List Operations
Push Front/Back
Add elements at beginning or end
myList.push_front(0);
myList.push_back(6);Pop Front/Back
Remove elements from beginning or end
myList.pop_front();
myList.pop_back();Insert
Insert elements at any position
auto it = myList.begin();
myList.insert(it, 10);Remove
Remove specific values or ranges
myList.remove(3);
myList.erase(it);🔹 Basic List Operations
C++ lists are doubly-linked sequences providing efficient insertion and deletion anywhere. Common
operations include push_front(), push_back(), pop_front(),
pop_back(), and insert() at an iterator position. Unlike vectors, lists don’t support
random access but excel at frequent modifications. They also offer unique functions like splice() to
transfer nodes between lists and merge() to combine sorted lists efficiently.
#include <iostream>
#include <list>
using namespace std;
int main() {
// Create a list
list<int> numbers;
// Add elements
numbers.push_back(10);
numbers.push_back(20);
numbers.push_front(5);
// Display list
cout << "List: ";
for(int num : numbers) {
cout << num << " ";
}
cout << endl;
// Size and empty check
cout << "Size: " << numbers.size() << endl;
cout << "Empty: " << (numbers.empty() ? "Yes" : "No") << endl;
return 0;
}Output:
List: 5 10 20
Size: 3
Empty: No
🔹 List Insertion and Deletion
Lists support constant-time insertion and deletion of elements at any position using iterators.
Functions like insert() add elements before a given iterator, and erase() removes the
element at an iterator. For example, you can insert a fruit into the middle of a list or remove a specific item by
value. This performance characteristic makes lists ideal for applications requiring frequent internal modifications,
such as managing ordered task lists or adjacency lists in graphs.
#include <iostream>
#include <list>
using namespace std;
int main() {
list<string> fruits = {"apple", "banana", "cherry"};
// Insert at beginning
fruits.push_front("orange");
// Insert at specific position
auto it = fruits.begin();
advance(it, 2); // Move iterator to 3rd position
fruits.insert(it, "grape");
// Display list
cout << "Fruits: ";
for(const string& fruit : fruits) {
cout << fruit << " ";
}
cout << endl;
// Remove specific element
fruits.remove("banana");
cout << "After removing banana: ";
for(const string& fruit : fruits) {
cout << fruit << " ";
}
return 0;
}Output:
Fruits: orange apple grape banana cherry
After removing banana: orange apple grape cherry
🔹 List Sorting and Merging
Lists have member functions sort() and merge() optimized for linked
structure. Unlike generic std::sort, which requires random-access iterators,
list::sort works in O(n log n) time via merge sort. list::merge efficiently combines two
sorted lists into one, preserving order. These specialized operations avoid the overhead of copying elements,
providing better performance than using standard algorithms on lists.
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> list1 = {3, 1, 4, 1, 5};
list<int> list2 = {2, 6, 8};
// Sort lists
list1.sort();
list2.sort();
cout << "Sorted list1: ";
for(int num : list1) {
cout << num << " ";
}
cout << endl;
// Merge sorted lists
list1.merge(list2);
cout << "Merged list: ";
for(int num : list1) {
cout << num << " ";
}
return 0;
}Output:
Sorted list1: 1 1 3 4 5
Merged list: 1 1 2 3 4 5 6 8