std::list

std::list is a doubly linked list container provided by the Standard Template Library (STL).

Unlike std::vector, which uses a dynamic array, std::list stores elements in a linked list data structure.

Each element in the list (node) contains a value and two pointers, one to the previous node and one to the next node, allowing efficient insertion and deletion of elements anywhere in the list.

Creating a std::list:

To use std::list, you need to include the <list> header.

#include <iostream>
#include <list>

int main() {
    // Create an empty list of integers
    std::list<int> myList;

    // Create a list with initial values using initializer list
    std::list<int> initializedList = {10, 20, 30, 40, 50};

    return 0;
}

In C++, std::list is a doubly linked list container provided by the Standard Template Library (STL). Unlike std::vector, which uses a dynamic array, std::list stores elements in a linked list data structure. Each element in the list (node) contains a value and two pointers, one to the previous node and one to the next node, allowing efficient insertion and deletion of elements anywhere in the list.

Advantages of std::list:

Efficient insertion and deletion: std::list allows constant time insertion and deletion of elements anywhere in the list.
No reallocation: Insertions and deletions do not require reallocation and shifting elements as in std::vector.
Stable iterators: Iterators remain valid even after inserting or erasing elements.

Disadvantages of std::list:

No direct access: Unlike std::vector, std::list does not support constant-time access using indexing. Accessing elements requires traversing the list from the beginning or end.
Higher memory overhead: Each element in the list requires extra memory for two pointers (for the previous and next nodes).
Less cache-friendly: Elements in a linked list may not be stored contiguously in memory, potentially leading to poorer cache performance compared to std::vector.

std::list is useful in scenarios where frequent insertion and deletion of elements at any position are required. It is especially efficient for large lists where reallocation overhead and contiguous memory storage can become a performance bottleneck. However, if you need constant-time access using indexing or better cache performance, std::vector might be a more suitable choice.

Important Functions of std::list:

push_back(value):

Adds an element to the end of the list.

Time Complexity: Constant time (O(1)).
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <list>

int main() {
    std::list<int> myList;

    myList.push_back(10);
    myList.push_back(20);
    myList.push_back(30);

    return 0;
}

push_front(value):

Adds an element to the beginning of the list.

Time Complexity: Constant time (O(1)).
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <list>

int main() {
    std::list<int> myList;

    myList.push_front(10);
    myList.push_front(20);
    myList.push_front(30);

    return 0;
}

pop_back():

Removes the last element from the list.

Time Complexity: Constant time (O(1)).
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {10, 20, 30};

    myList.pop_back(); // After this, myList contains {10, 20}

    return 0;
}

pop_front():

Removes the first element from the list.

Time Complexity: Constant time (O(1)).
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {10, 20, 30};

    myList.pop_front(); // After this, myList contains {20, 30}

    return 0;
}

size():

Returns the number of elements in the list.

Time Complexity: Constant time (O(1)).
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {10, 20, 30};

    std::cout << "Size of the list: " << myList.size() << std::endl; // Output: 3

    return 0;
}

empty():

Checks if the list is empty.

Time Complexity: Constant time (O(1)).
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <list>

int main() {
    std::list<int> myList;

    if (myList.empty()) {
        std::cout << "List is empty." << std::endl;
    } else {
        std::cout << "List is not empty." << std::endl;
    }

    return 0;
}

clear():

Removes all elements from the list.

Time Complexity: Linear time (O(n)).
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {10, 20, 30};

    myList.clear(); // After this, myList is empty

    return 0;
}

front():

Returns a reference to the first element in the list.

Time Complexity: Constant time (O(1)).
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {10, 20, 30};

    int firstElement = myList.front(); // firstElement = 10

    return 0;
}

back():

Returns a reference to the last element in the list.

Time Complexity: Constant time (O(1)).
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {10, 20, 30};

    int lastElement = myList.back(); // lastElement = 30

    return 0;
}

emplace_front(args…):

Adds a new element to the beginning of the list using its constructor with provided arguments.

Time Complexity: Constant time (O(1)).
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <list>

class MyClass {
public:
    MyClass(int a, int b) {
        std::cout << "Constructor called with arguments " << a << " and " << b << std::endl;
    }
};

int main() {
    std::list<MyClass> myList;

    myList.emplace_front(10, 20); // Calls the constructor of MyClass with arguments 10 and 20

    return 0;
}

emplace_back(args…):

Adds a new element to the end of the list using its constructor with provided arguments.

Time Complexity: Constant time (O(1)).
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <list>

class MyClass {
public:
    MyClass(int a, int b) {
        std::cout << "Constructor called with arguments " << a << " and " << b << std::endl;
    }
};

int main() {
    std::list<MyClass> myList;

    myList.emplace_back(10, 20); // Calls the constructor of MyClass with arguments 10 and 20

    return 0;
}

insert(position, value):

Inserts an element with the specified value at the given position in the list.

Time Complexity: Constant time (O(1)).
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {10, 30};

    auto it = myList.begin();
    ++it; // Move iterator to the second position

    myList.insert(it, 20); // After this, myList contains {10, 20,

 30}

    return 0;
}

erase(position):

Removes the element at the specified position from the list.

Time Complexity: Constant time (O(1)).
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {10, 20, 30};

    auto it = myList.begin();
    ++it; // Move iterator to the second position

    myList.erase(it); // After this, myList contains {10, 30}

    return 0;
}

remove(value):

Removes all occurrences of the specified value from the list.

Time Complexity: Linear time (O(n)).
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {10, 20, 30, 20, 40};

    myList.remove(20); // After this, myList contains {10, 30, 40}

    return 0;
}

unique():

Removes consecutive duplicate elements from the list.

Time Complexity: Linear time (O(n)).
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {10, 20, 20, 30, 30, 40};

    myList.unique(); // After this, myList contains {10, 20, 30, 40}

    return 0;
}

sort():

Sorts the elements in the list in ascending order.

Time Complexity: Linearithmic time (O(n log n)).
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {30, 10, 50, 20, 40};

    myList.sort(); // After this, myList contains {10, 20, 30, 40, 50}

    return 0;
}

reverse():

Reverses the order of elements in the list.

Time Complexity: Linear time (O(n)).
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {10, 20, 30};

    myList.reverse(); // After this, myList contains {30, 20, 10}

    return 0;
}