List

List is a built-in C++ sequence container that allows non-contiguous memory allocation. When we are talking about a list, we talk about a doubly linked list. There is another type of list called forward list that means a singly linked list. 

So, for everything to be clear. 
The vector data structure allows contiguous memory allocation, meaning every element is directly after the previous element in the memory.
While, the linked list data structure has elements that have a data part (the actual value) and a pointer that contains the memory address of the next element in the list.

There are two types of linked lists in C++:

• doubly linked list - list
• singly linked list - forward list

The main difference between the doubly linked list and singly linked list is that the singly-linked lists can only iterate forward, meaning every element has its own value and the memory address of the next element. While the doubly-linked list elements keep information on how to locate the next and the previous element in the list.

We use the list (doubly-linked list) and the forward list (singly-linked list) by including them in our file using:

#include <list>
#include <forward_list>

Or, we simply only include the bits/stdc++.h header file.

Forward List

So, first we are going to talk about the forward list. We have many methods with the forward list, we are going to talk about the most useful ones.
We declare a forward list exactly like we did with the vector and deque.

forward_list<int> flist = {1, 2, 3};

We can add elements using the push_front() method and we can remove elements from the front using pop_front().

flist.push_front(5);
for (int &x : flist) // we output the elements using pointer that increases its value on every iteration
	cout << x << " ";
cout << endl;

flist.pop_front();
for (int &x : flist)
	cout << x << " ";

Output:
5 1 2 3
1 2 3

Forward List Methods

List

Next, is the list. We also have many methods used with the list data structure but you're going to be introduced to the most useful ones. 
First, you'll learn how we declare a list after including it at the top of the .cpp file. 

list<int> list1 = {1, 2, 3};

We can add elements to the list with using either the push_front() or the push_back() method.
Likewise, we can remove the first and last element using the pop_front() and pop_back() method, respectively.

list1.push_back(4);
list1.push_front(0);
for (int &x : list1)
	cout << x << " ";
cout << endl;

list1.pop_front();
list1.pop_back();
for (int &x : list1)
	cout << x << " ";

Output:
0 1 2 3 4
1 2 3

List Methods