What is std::list?

At its core, std::list is a doubly linked list container in C++'s STL. Unlike array-based containers such as std::vector or std::deque which utilizes contiguous memory storage, std::list organizes elements as nodes linked together through pointers. Each node in the list contains both a data element and pointers to the previous and next nodes, facilitating efficient traversal and manipulation of the list.

Characteristics

1. Doubly Linked List Structure:
   1. std::list is implemented as a doubly linked list, where each element (node) contains pointers to both the previous and next elements in the sequence.
   2. This doubly linked structure allows for efficient traversal in both forward and backward directions.
2. Dynamic Memory Allocation:
   1. std::list dynamically allocates memory for each node as elements are added to the list.
   2. This dynamic memory allocation enables std::list to grow or shrink dynamically, without the need for contiguous memory allocation.
3. Efficient Insertion and Deletion:
   1. Insertion and deletion operations at any position within the list have a constant-time complexity O(1).
   2. These operations involve updating pointers to link or unlink nodes, which can be done efficiently regardless of the list's size.
4. Bidirectional Iteration:
   1. std::list supports bidirectional iteration, allowing traversal of elements both forwards and backwards.
   2. Iterators provide efficient means to navigate through the elements of the list in either direction.
5. No Random Access:
   1. Unlike array-based containers such as std::vector, std::list does not support random access to elements.
   2. Accessing elements by index or position requires sequential traversal from the beginning or end of the list.
6. Memory Efficiency:
   1. std::list offers efficient memory utilization, as it only requires memory for the data elements and the pointers to the previous and next nodes.
   2. Each node in the list consumes memory for the data element and two pointer variables, resulting in a memory-efficient data structure.
7. No Contiguous Memory Allocation:
   1. Unlike array-based containers that store elements in contiguous memory locations, std::list does not require contiguous memory allocation.
   2. This characteristic allows for efficient insertion and deletion operations without the overhead of reallocation or shifting of elements.

Syntax

#include <list> // Include the list header

int main() {
    // Declaration and Initialization
    std::list<DataType> myList; // Create an empty list
    std::list<DataType> myList = {val1, val2, val3}; // Create and initialize with values
    
    // Iterators
    myList.begin(); // Iterator pointing to the first element
    myList.end(); // Iterator pointing to one past the last element
    
    // Capacity
    myList.empty(); // Returns true if the list is empty, false otherwise
    myList.size(); // Returns the number of elements in the list
    
    // Modifiers
    myList.push_front(value); // Insert element at the beginning
    myList.pop_front(); // Remove the first element
    myList.push_back(value); // Insert element at the end
    myList.pop_back(); // Remove the last element
    myList.insert(iterator, value); // Insert element at the specified position
    myList.erase(iterator); // Remove element at the specified position
    myList.clear(); // Remove all elements
    
    // Element Access
    myList.front(); // Access the first element
    myList.back(); // Access the last element
    
    // Iteration
    for (auto it = myList.begin(); it != myList.end(); ++it) {
        // Access each element using the iterator 'it'
    }
    
    return 0;
}

Functions

1 push_front()

It is used to insert an element at the beginning of the list.

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {2, 3, 4};
    
    // Inserting an element at the beginning
    myList.push_front(1);

    // Displaying elements
    for (int num : myList) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Complexity: The time complexity of push_front() is constant O(1) because it involves inserting the element at the beginning of the list, which can be done in constant time regardless of the list's size.

2 pop_front()

It is used to remove the first element from the list.

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {1, 2, 3, 4};

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

    // Displaying elements
    for (int num : myList) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Complexity:

• The time complexity is constant O(1)because it involves removing the first element of the list, which can be done in constant time regardless of the list's size.

3 push_back()

It is used to insert an element at the end of the list.

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {1, 2, 3};

    // Inserting an element at the end
    myList.push_back(4);

    // Displaying elements
    for (int num : myList) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Complexity:

• The time complexity is constant O(1) because it involves inserting the element at the end of the list, which can be done in constant time regardless of the list's size.

4 pop_back()

It is used to remove the last element from the list.

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {1, 2, 3, 4};

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

    // Displaying elements
    for (int num : myList) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Complexity:

• The time complexity is constant O(1)because it involves removing the last element of the list, which can be done in constant time regardless of the list's size.

5 insert()

It is used to insert an element at a specified position in the list.

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {1, 2, 4};

    // Inserting an element at the second position
    auto it = myList.begin();
    std::advance(it, 1); // Move iterator to the desired position
    myList.insert(it, 3);

    // Displaying elements
    for (int num : myList) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Complexity:

The time complexity is linear O(N) in the worst case because it involves traversing the list to reach the specified position. However, for inserting at the beginning or end (with iterators), it's constant O(1).

6 erase()

It is used to remove an element from a specified position in the list.

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {1, 2, 3, 4};

    // Removing the second element
    auto it = myList.begin();
    std::advance(it, 1); // Move iterator to the desired position
    myList.erase(it);

    // Displaying elements
    for (int num : myList) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Complexity:

• The time complexity is constant O(1) because it involves removing the element at the specified position, which can be done in constant time regardless of the list's size.