Forward List in STL

What is a Forward List?

A forward_list in C++ is a singly linked list container that allows sequential access to its elements. Unlike other list containers in the STL, such as list or deque, forward_list supports only forward iteration, hence the name.

Characteristics

1. Singly Linked List Structure:
   1. A forward_list is implemented as a singly linked list, where each element (node) contains a pointer to the next element in the sequence.
   2. Unlike doubly linked lists, forward_list nodes only maintain a forward link, resulting in reduced memory overhead.
2. Forward Iteration Only:
   1. The forward_list supports forward iteration only, as the name suggests. This means traversal through the elements can only be done in a forward direction.
   2. Iterators allow movement from one element to the next but not backward.
3. Efficient Insertion and Deletion:
   1. Insertion and deletion operations at the beginning of a forward_list are particularly efficient, typically requiring constant time complexity O(1).
   2. Operations such as push_front(), insert_after(), and erase_after() provide efficient ways to modify the list.
4. No Random Access:
   1. Unlike array-like containers such as std::vector or std::array, forward_list does not support random access to elements.
   2. Accessing elements by index or position is not directly possible; instead, traversal from the beginning of the list is necessary to reach a specific element.
5. Reduced Memory Overhead:
   1. Due to its singly linked structure, forward_list generally consumes less memory compared to doubly linked list containers like std::list.
   2. Each node in the list requires memory for storing the data element and a pointer to the next node, resulting in a smaller memory footprint.
6. No Reverse Iteration:
   1. Since forward_list nodes only maintain a forward link, reverse iteration (traversing from the end to the beginning) is not supported.
   2. To traverse the list in reverse order, it would be necessary to first reverse the list or use alternative data structures.

Syntax:

#include <forward_list> // Include the forward_list header

int main() {
    // Declaration and Initialization
    std::forward_list<DataType> forwardListName; // Create an empty forward_list
    std::forward_list<DataType> forwardListName = {val1, val2, val3}; // Create and initialize with values
    
    // Iterators
    forwardListName.begin(); // Iterator pointing to the first element
    forwardListName.end(); // Iterator pointing to one past the last element

    // Capacity
    forwardListName.empty(); // Returns true if the forward_list is empty, false otherwise
    forwardListName.size(); // Returns the number of elements in the forward_list
    
    // Modifiers
    forwardListName.push_front(value); // Insert element at the beginning
    forwardListName.pop_front(); // Remove the first element
    forwardListName.insert_after(iterator, value); // Insert element after the specified position
    forwardListName.erase_after(iterator); // Remove element after the specified position
    forwardListName.clear(); // Remove all elements
    
    // Operations
    forwardListName.merge(otherForwardList); // Merge two forward_lists
    forwardListName.sort(); // Sort elements in non-descending order
    forwardListName.reverse(); // Reverse the order of elements
    
    // Element Access
    forwardListName.front(); // Access the first element
    
    // Iteration
    for (auto it = forwardListName.begin(); it != forwardListName.end(); ++it) {
        // Access each element using the iterator 'it'
    }
    
    return 0;
}

Functions

1 push_front():

Adds a new element at the beginning of the forward_list.

#include <iostream>
#include <forward_list>

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

    // Inserting an element at the beginning
    myForwardList.push_front(40);

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

    return 0;
}

Complexity: O(1) - Constant time. This operation always takes the same amount of time, regardless of the size of the forward_list.

2 pop_front():

Removes the first element from the forward_list.

#include <iostream>
#include <forward_list>

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

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

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

    return 0;
}

Complexity: O(1) - Constant time. This operation always takes the same amount of time, regardless of the size of the forward_list.

3 insert_after()

It insert an element after a specified position in the forward_list.

#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> myForwardList = {30, 10};

    // Inserting an element after the first position
    auto it = myForwardList.begin();
    myForwardList.insert_after(it, 20);

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

    return 0;
}

Complexity: The time complexity of insert_after() is constant O(1) because it involves creating a new node and adjusting pointer which is independent of the size of the forward_list.

4 erase_after()

It is used to remove an element after a specified position in the forward_list.

#include <iostream>
#include <forward_list>

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

    // Removing the element after the first position
    auto it = myForwardList.begin();
    myForwardList.erase_after(it);

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

    return 0;
}

Complexity: The time complexity of erase_after() is constant O(1) because it involves adjusting pointers to remove an element, which is independent of the of the forward_list.

5 clear()

It is used to remove all elements from the forward_list.

#include <iostream>
#include <forward_list>

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

    // Clearing all elements
    myForwardList.clear();

    // Displaying elements (should be empty)
    for (int num : myForwardList) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Complexity: The time complexity of clear() is linear O(N), where N is the number of elements in the forward_list. It involves deallocating memory for each node, and the time required is proportional to the size of the list.