Hello again! In this video, we are going to look at the C++ list
class. We have already looked at forward_list, which implements a single-linked list, in which each node
has a pointer to the node which follows it.
There are also double-linked lists, in which the nodes also have a pointer to the previous node, the one which
comes before it.
So this means it is very easy to go backwards in a double-linked list.
You just follow the pointer to the previous node. And the C++ library provides the list class, which
implements double-linked lists.
So a double-linked list will look like this.
We have the first element which has its pointer to the following element.
The following elements also has a pointer which goes back to the first element.
So we have the "next" pointer, which goes to the following element, and the "previous" pointer, which
goes to the "before" element.
And then this has a "next" pointer to the following element, and that has a "previous" pointer to the "before"
element, and so on.
When we get to the last element, the next pointer is null.
So there is no following element.
And also at the beginning, the previous pointer is null because there is no "before" element.
If we want to add an element at the back of the list, we create node.
We go to the node which is currently the last node, and we make its "next" link point to us.
Then we make our "previous" link point to the last node.
And once you have done that, the node has been added and it now becomes the last node.
So this will only affect our node and the current last node.
All the other elements in the list are left unaffected.
If we want to insert a node in the middle of a linked list, between two elements, we need to find the
elements before and after the insertion point, where we are going to add our element.
We make our "next" link point to the following node, the one that comes after and we make our "previous"
link point to the "before" node.
Then we go to the "before" node, we make its "next" link point to us, and we make the following node's
"previous" link point to us. So only the previous node, our node and the following node are changed.
All the other elements in the list are unmodified.
So it works like this. Before, the element "three" had a next link to element "one", and element "one"
had a previous link to "three".
Now we've hooked these up differently, so "three" now has a next link to "two".
And "one" has a previous link to "two".
And then our new element has previous link to "three" and next link to "one".
So all we need to do to add this element is just change a few pointers around.
For removing an element from a linked list, again, we need to identify the following and before nodes.
We go to the before node and make its next link point to the following node, and we make the previous
link on the following node point to the before node, and then that will release our nodes, and we can destroy
it.
And again, it is just those three nodes which are modified.
So we go to the "three" node and we make its next link go back to "one" again.
And this element's previous link goes back to "three" again.
And that will just unhook this node, and it leaves the list.
OK, so let's try this out.
So we use the header
for a double-linked list. We create an object. We can loop over it.
We are going to insert a new element before the last element, like we did in the slide.
So we need to get an iterator to the last element.
So if we get the return value from end() and go back by one, that will be an iterator to the last element.
Then we call insert() with this iterator and the value as arguments.
So this will add a new element with 2 before the last element. And then, to remove it,
we call erase(), with that iterator as the argument.
So we started off with 4, 3 and 1.
We inserted an element with value 2 before the last one.
And then we removed it.
So as you can see, adding or removing elements from the middle of the list just involves a few pointer
assignments.
It is not like a vctor where you, usually, need to move elements around, and you may need to reallocate
the memory block. Lists do not support random access.
There is no notion of indexing or subscription notation, and you cannot jump around. If you are at some node
and you want to get to another node, then you have to go one node at a time.
You cannot just jump to it like you can with the vector. Lists
use more memory. As well as the element,
you need a pointer, or two pointers for double-linked list. The best situation for
using a list is if you are going to be adding or removing lots of elements frequently, especially if
they are in the middle of the list.
Okay, so that is it for this video.
I will see you next time.
Until then, keep coding!