C++ Lists

In C++, std::list is a part of the Standard Template Library (STL) and represents a doubly linked list. Unlike std::vector, which is a dynamic array, std::list is designed for situations where frequent insertions and deletions of elements at arbitrary positions are required.

Key Features of `std::list`

Doubly Linked List: Each element (node) in a std::list contains pointers to both the previous and next elements. This allows for bidirectional traversal and efficient insertions/deletions from both ends and within the list.
Non-contiguous Storage: Elements are not stored in contiguous memory locations, unlike std::vector.
Efficient Insertions/Deletions: Insertions and deletions at any position are efficient (constant time), but random access is not supported.
Bidirectional Iterators: Supports iterators that allow traversing the list in both directions.

Basic Operations

1. Including the Header

To use std::list, include the header file:

cpp
#include

2. Declaring and Initializing a List

cpp
#include 
#include 

using namespace std;

int main() {
    // Default constructor
    list<int> lst1;

    // Initialization with values
    list<int> lst2 = {1, 2, 3, 4, 5};

    // Initialization with a size
    list<int> lst3(5, 10); // Creates a list with 5 elements, all initialized to 10

    return 0;
}

3. Adding Elements

cpp
#include 
#include 

using namespace std;

int main() {
    list<int> lst;

    // Adding elements at the end
    lst.push_back(1);
    lst.push_back(2);
    lst.push_back(3);

    // Adding elements at the beginning
    lst.push_front(0);

    // Inserting elements at a specific position
    auto it = lst.begin();
    ++it; // Move iterator to the second position
    lst.insert(it, 4); // Inserts 4 before the second element

    return 0;
}

4. Accessing Elements

std::list does not support direct indexing. Instead, use iterators to access elements:

cpp
#include 
#include 

using namespace std;

int main() {
    list<int> lst = {1, 2, 3, 4, 5};

    // Accessing elements using iterators
    for (auto it = lst.begin(); it != lst.end(); ++it) {
        cout << *it << " "; // Output: 1 2 3 4 5
    }
    cout << endl;

    return 0;
}

5. Modifying Elements

cpp
#include 
#include 

using namespace std;

int main() {
    list<int> lst = {1, 2, 3, 4, 5};

    // Modifying elements
    auto it = lst.begin();
    ++it; // Move iterator to the second element
    *it = 10; // Change second element to 10

    for (auto num : lst) {
        cout << num << " "; // Output: 1 10 3 4 5
    }
    cout << endl;

    return 0;
}

6. Removing Elements

cpp
#include 
#include 

using namespace std;

int main() {
    list<int> lst = {1, 2, 3, 4, 5};

    // Removing the last element
    lst.pop_back();

    // Removing the first element
    lst.pop_front();

    // Removing a specific element
    auto it = lst.begin();
    ++it; // Move iterator to the second element
    lst.erase(it); // Removes the second element

    // Clearing all elements
    lst.clear();

    return 0;
}

7. Iterating Over a List

cpp
#include 
#include 

using namespace std;

int main() {
    list<int> lst = {1, 2, 3, 4, 5};

    // Using range-based for loop
    for (int num : lst) {
        cout << num << " "; // Output: 1 2 3 4 5
    }
    cout << endl;

    // Using iterator
    for (auto it = lst.begin(); it != lst.end(); ++it) {
        cout << *it << " "; // Output: 1 2 3 4 5
    }
    cout << endl;

    return 0;
}

Advanced Features

1. Splicing

You can transfer elements between lists using splice:

cpp
#include 
#include 

using namespace std;

int main() {
    list<int> lst1 = {1, 2, 3};
    list<int> lst2 = {4, 5, 6};

    // Splicing elements from lst2 into lst1
    lst1.splice(lst1.end(), lst2);

    // lst1 now contains: 1 2 3 4 5 6
    // lst2 is now empty

    return 0;
}

2. Sorting

You can sort a std::list using the sort method:

cpp
#include 
#include 

using namespace std;

int main() {
    list<int> lst = {4, 1, 3, 5, 2};

    // Sorting the list
    lst.sort();

    for (int num : lst) {
        cout << num << " "; // Output: 1 2 3 4 5
    }
    cout << endl;

    return 0;
}

3. Merging

You can merge two sorted lists:

cpp
#include 
#include 

using namespace std;

int main() {
    list<int> lst1 = {1, 3, 5};
    list<int> lst2 = {2, 4, 6};

    // Merging lst2 into lst1
    lst1.merge(lst2);

    for (int num : lst1) {
        cout << num << " "; // Output: 1 2 3 4 5 6
    }
    cout << endl;

    return 0;
}

Performance Considerations

Insertion/Deletion: Efficient for operations at the beginning, end, or within the list (except for random access).
Access: Does not support direct random access; traversal is linear in time complexity.
Memory Usage: Each element in a std::list requires additional memory for storing pointers to the previous and next elements.

Summary

std::list is a doubly linked list that allows efficient insertions and deletions at both ends and within the list.
It supports bidirectional iteration and has operations like splicing, sorting, and merging.
It does not support direct indexing, so access to elements is done through iterators.

std::list is suitable for scenarios where frequent insertions and deletions are required, and direct access to elements is not critical.

techmore.in