[C++] Lists

[C++] Lists

The List is a Data Structure or a Container that, unlike some other data structures, allows insertion and deletion of elements anywhere in the container, and it's done very efficiently in constant time(without needing to loop through the container and add or replace) which is also represented as 0(1) in terms of Big 0 notation which is very efficient.

image.png

Things to Note about a List:

It does not allow direct element access either through the subscript operator [] or .at() method.

It provides bi-directional iteration support(you can iterate in both directions) unlike forward_list.

Efficient insertion and deletion of elements anywhere in the container.

Elements are stored in non-contiguous memory which means the memory address of its individual elements aren't stored together in a memory block(for more info, go here)

The list is a convenient choice when multiple insertions and deletion from different parts of a container without needing direct access to the elements.

The header file for list needs to be included before lists can be used. Lists have front and back element access :

#include <iostream>
#include <string>
#include <list> //LIST HEADER FILE

using std::cout;
using std::cin;
using std::endl;

int main() {
    std::list<std::string> test;
    test = {std::string {"Hello"}, "Bye"};
    cout << test.front() << " " << test.back() << endl;
    return 0;
}

image.png

It also has a couple of other methods that are common in other containers :

int main() {
    std::list<std::string> test;
    test = {std::string {"Hello"}, "Bye"};
    ///EMPTY() CHECKS TO SEE IF THE LIST IS EMPTY, IT RETURNS A BOOLEAN
    if(test.empty())
        cout << "List is Empty\n";
    else
        cout << "List isn't Empty, it has a size of " << test.size() << endl; //SIZE() RETURNS THE SIZE OF THE LIST
    return 0;
}

image.png

#include <iostream>
#include <string>
#include <list>

using std::cout;
using std::cin;
using std::endl;
void view(std::list<std::string> t){
    cout << "[ ";
    for(auto &a: t)
        cout << a << " ";
    cout << "]\n";
}
int main() {
    std::list<std::string> test;
    test = {std::string {"Hello"}, "Bye"};
    view(test);
    test.clear(); //REMOVES ALL ELEMENTS IN THE CONTAINER
    if(test.empty())
        cout << "Empty\n";
    else
        cout << "Not Empty\n";

    test.push_back("Hello");
    test.push_back("Bye");
    test.erase(test.begin()); //ERASE THE FIRST ELEMENT
    view(test);
    return 0;
}

image.png

Now for inserting elements into the middle of a list, you have to use either insert or emplace, the methods expect an iterator and the argument to be inserted, it is inserted behind the element pointed to by the iterator:

int main() {
    std::list<std::string> test;
    test = {std::string {"Hello"}, "There", "Bye"};
    view(test);
    std::list<std::string>::iterator it = ++(test.begin()); //ITERATOR IS POINTING TO 'THERE'
    test.insert(it, "boy");
    view(test);
    test.emplace(it, "girl"); //PLACES 'GIRL' BEFORE 'THERE'
    view(test);
    test.pop_front(); //REMOVES ELEMENT FROM THE FRONT
    view(test);
    test.push_front("Hello"); //PUSHES ELEMENT TO THE FRONT
    view(test);
    return 0;
}

image.png

int main() {
    std::list<int> list1 = { 5,9,0,1,3 };
    std::list<int> list2 = { 8,7,2,6,4 };

    list1.sort(); //SORTS THE LIST IN ASCENDING ORDER
    list2.sort();
    view(list1);
    view(list2);
    list1.merge(list2); //JOINS THE TWO SORTED LIST LISTS INTO ONE 'SORTED' LIST
    cout << "merged: ";
    view(list1);
    return 0;
}

image.png

Notice how the merged list are even sorted further when joined together

void view(std::list<int> t){
    if(t.empty())
        cout << "Empty\n";
    else{
        cout << "[ ";
        for(auto &a: t)
            cout << a << " ";
        cout << "]\n";
    }
}
int main() {
    std::list<int> list1 = {1,2,3,4,5,9,0};
    std::list<int> list2 = {6,7,8};
    view(list1);
    view(list2);
    auto it = list1.begin();
    std::advance(it, 5); //ADVANCES THE ITERATOR FORWARD 2 TIMES. IT NOW POINTS TO 9
    list1.splice(it, list2); //ALL ELEMENTS OF 'LIST2' ARE NOW PLACED BEFORE THE ELEMENT WHICH THE 'IT' POINTS TO
    view(list1);
    view(list2); //NOW EMPTY SINCE ITS ELEMENTS HAVE BEEN SPLICED
    return 0;
}

image.png

Note : splice doesn't copy or move the elements of the 'spliced' container

image.png

There are other methods in a list, you can get more info on lists here. Like i said earlier, if you need a container for multiple insertions and deletions anywhere in the container without needing direct access to the elements then the list is a good choice due to its efficiency.