Hello again! In this video, we are going to look at the forward list.
The containers that we have looked at so far,
string vector and arrays, built-in or library. They all use a single block of memory, which will store
all the elements in the container.
A list has quite a different structure.
Each element has its own memory allocation, which is known as a node.
This will contain the data for the element. And also a pointer.
This pointer has the address of the node which follows, in the list.
The last node in the list has a pointer which is invalid, a null pointer, and that indicates that there
is no following node.
So the structure will look something like this. We have the first element which has data with the
value 4. The second elements has data with the value 3.
And the first element has a pointer, which is the address of this node.
And then this node has a pointer, which is the address of the next node, and so on.
When we get to the last node, the pointer is invalid, and that is how we know it is the last node.
To iterate through a list, we start at the first node. We get the link pointer, and then we follow
it.
And that will take us to the second node.
Then we get the link points of the second node, and we follow that to the third node, and so on.
When we get to a node with an invalid pointer, we stop. Because that is the last one.
This data structure is known as a forward list, or a singly-linked list.
We can iterate forwards through the list, just by following the pointers. Going backwards is a bit more
involved, but it is possible! The C++ standard library provides a forward_list class, which
is an implementation of the single-linked list.
Adding an element at the back of a linked list involves creating a node for the element.
We go to the last node in the list and get its pointer.
And we make the pointer point to our new node. And that will make our new node, the last node in the
list.
So we node to give it an invalid "next" pointer.
If we are going to insert a node in the middle of the linked list, we node to find the node before it.
Then we node to get its link pointer, and make it point to our new node.
We also node to get the node which follows it, and then our link pointer is going to point to the
following node.
So when we add an element to the list, only the previous element and the element that we are adding
are affected.
The rest of the list is left completely untouched.
So it works like this. If we want to add an element with the value 2 after this element, we get
the link pointer
of this element to point to our new node, and then our link pointer points to the one which followed
the element with the value 3.
To remove an element from a linked list, we go to the previous node again, and we change its link pointer,
so it is pointing to the node which follows our one. And that will detach our node from the list, and then
we can release the memory it is using. And again, only the previous node and the next node are affected.
The rest of the list is entirely untouched.
So this is how it works.
We go to the previous element. We get its link pointer, and we make it point to the element which
follows ours.
List operations are a bit different from the other sequential containers. We will look at those later on.
There is one which is peculiar to forward lists. Usually with a sequential container,
if we want to add or remove an element, we can call insert() and erase().
These will take an iterator, and these will add or remove an element, just before that iterator.
This requires that the container supports reverse iterators, which forward_list does not do.
It only supports forward iterators.
So instead, there are different member functions: insert_after() and erase_after().
So these will take an iterator as argument, but they will insert or remove the element which follows
that iterator.
So let's have a quick look at a forward_list.
We need the header.
We create an instance of a list, as you would expect.
We can do a range-for loop, to print out all the elements.
We can call insert_after(). We need to get an iterator.
We are going to do the same example that we had on the slide.
So we are going to insert an element with value 2, after the second element.
So we need an iterator to the second element.
So we get the begin() return value and advance it by 1.
And then we erase that element.
So again, we get the second element, and we call erase_after().
And there we are, we start off with elements 4, 3 and 1.
We insert an element with value 2 after the element with value 3.
And then we remove the element which followed the element with value 3.
And that takes us back to the original list.
Okay, so that is it for this video.
I will see you next time.
But until then, keep coding!