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.
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;
}
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;
}
#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;
}
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;
}
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;
}
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;
}
Note :
splice
doesn't copy or move the elements of the 'spliced' container
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.