WEBVTT 00:00.150 --> 00:03.840 Hello again! In this video, we are going to look at the C++ list 00:04.010 --> 00:11.370 class. We have already looked at forward_list, which implements a single-linked list, in which each node 00:11.820 --> 00:13.740 has a pointer to the node which follows it. 00:14.640 --> 00:20.190 There are also double-linked lists, in which the nodes also have a pointer to the previous node, the one which 00:20.190 --> 00:21.180 comes before it. 00:22.110 --> 00:25.530 So this means it is very easy to go backwards in a double-linked list. 00:25.920 --> 00:32.730 You just follow the pointer to the previous node. And the C++ library provides the list class, which 00:32.730 --> 00:34.380 implements double-linked lists. 00:36.670 --> 00:39.100 So a double-linked list will look like this. 00:39.670 --> 00:43.360 We have the first element which has its pointer to the following element. 00:44.290 --> 00:48.010 The following elements also has a pointer which goes back to the first element. 00:48.370 --> 00:52.510 So we have the "next" pointer, which goes to the following element, and the "previous" pointer, which 00:52.510 --> 00:54.340 goes to the "before" element. 00:54.730 --> 01:00.790 And then this has a "next" pointer to the following element, and that has a "previous" pointer to the "before" 01:00.790 --> 01:01.690 element, and so on. 01:03.250 --> 01:06.850 When we get to the last element, the next pointer is null. 01:06.910 --> 01:09.130 So there is no following element. 01:09.730 --> 01:14.520 And also at the beginning, the previous pointer is null because there is no "before" element. 01:17.800 --> 01:21.850 If we want to add an element at the back of the list, we create node. 01:22.360 --> 01:27.490 We go to the node which is currently the last node, and we make its "next" link point to us. 01:28.300 --> 01:31.330 Then we make our "previous" link point to the last node. 01:31.990 --> 01:36.100 And once you have done that, the node has been added and it now becomes the last node. 01:36.940 --> 01:39.850 So this will only affect our node and the current last node. 01:40.330 --> 01:43.030 All the other elements in the list are left unaffected. 01:45.770 --> 01:52.430 If we want to insert a node in the middle of a linked list, between two elements, we need to find the 01:52.430 --> 01:56.330 elements before and after the insertion point, where we are going to add our element. 01:57.770 --> 02:04.190 We make our "next" link point to the following node, the one that comes after and we make our "previous" 02:04.190 --> 02:05.930 link point to the "before" node. 02:07.670 --> 02:13.160 Then we go to the "before" node, we make its "next" link point to us, and we make the following node's 02:13.160 --> 02:19.550 "previous" link point to us. So only the previous node, our node and the following node are changed. 02:19.940 --> 02:22.010 All the other elements in the list are unmodified. 02:25.500 --> 02:31.800 So it works like this. Before, the element "three" had a next link to element "one", and element "one" 02:31.800 --> 02:33.300 had a previous link to "three". 02:34.200 --> 02:38.010 Now we've hooked these up differently, so "three" now has a next link to "two". 02:38.580 --> 02:40.530 And "one" has a previous link to "two". 02:41.370 --> 02:46.050 And then our new element has previous link to "three" and next link to "one". 02:47.730 --> 02:51.870 So all we need to do to add this element is just change a few pointers around. 02:54.570 --> 02:59.750 For removing an element from a linked list, again, we need to identify the following and before nodes. 03:00.510 --> 03:06.870 We go to the before node and make its next link point to the following node, and we make the previous 03:06.870 --> 03:13.410 link on the following node point to the before node, and then that will release our nodes, and we can destroy 03:13.410 --> 03:13.560 it. 03:14.220 --> 03:16.830 And again, it is just those three nodes which are modified. 03:18.900 --> 03:23.520 So we go to the "three" node and we make its next link go back to "one" again. 03:24.150 --> 03:27.210 And this element's previous link goes back to "three" again. 03:28.020 --> 03:30.810 And that will just unhook this node, and it leaves the list. 03:32.700 --> 03:34.180 OK, so let's try this out. 03:34.200 --> 03:35.790 So we use the header 03:35.790 --> 03:41.310 for a double-linked list. We create an object. We can loop over it. 03:43.890 --> 03:48.990 We are going to insert a new element before the last element, like we did in the slide. 03:49.260 --> 03:51.660 So we need to get an iterator to the last element. 03:52.500 --> 03:58.260 So if we get the return value from end() and go back by one, that will be an iterator to the last element. 03:59.100 --> 04:03.060 Then we call insert() with this iterator and the value as arguments. 04:03.510 --> 04:08.790 So this will add a new element with 2 before the last element. And then, to remove it, 04:08.820 --> 04:11.520 we call erase(), with that iterator as the argument. 04:14.580 --> 04:16.770 So we started off with 4, 3 and 1. 04:17.160 --> 04:20.220 We inserted an element with value 2 before the last one. 04:20.670 --> 04:21.930 And then we removed it. 04:25.600 --> 04:30.850 So as you can see, adding or removing elements from the middle of the list just involves a few pointer 04:30.850 --> 04:31.450 assignments. 04:32.140 --> 04:37.510 It is not like a vctor where you, usually, need to move elements around, and you may need to reallocate 04:37.510 --> 04:42.760 the memory block. Lists do not support random access. 04:43.060 --> 04:48.790 There is no notion of indexing or subscription notation, and you cannot jump around. If you are at some node 04:48.790 --> 04:52.900 and you want to get to another node, then you have to go one node at a time. 04:53.110 --> 04:56.940 You cannot just jump to it like you can with the vector. Lists 04:56.950 --> 04:59.770 use more memory. As well as the element, 04:59.770 --> 05:04.120 you need a pointer, or two pointers for double-linked list. The best situation for 05:04.120 --> 05:09.250 using a list is if you are going to be adding or removing lots of elements frequently, especially if 05:09.250 --> 05:10.720 they are in the middle of the list. 05:11.110 --> 05:12.790 Okay, so that is it for this video. 05:13.240 --> 05:14.110 I will see you next time. 05:14.350 --> 05:16.390 Until then, keep coding!