WEBVTT 00:00.150 --> 00:03.450 Hello again! In this video, we are going to look at the forward list. 00:04.320 --> 00:06.630 The containers that we have looked at so far, 00:06.800 --> 00:14.370 string vector and arrays, built-in or library. They all use a single block of memory, which will store 00:14.370 --> 00:15.660 all the elements in the container. 00:16.740 --> 00:18.690 A list has quite a different structure. 00:19.050 --> 00:22.890 Each element has its own memory allocation, which is known as a node. 00:23.520 --> 00:27.600 This will contain the data for the element. And also a pointer. 00:28.830 --> 00:32.760 This pointer has the address of the node which follows, in the list. 00:34.650 --> 00:40.050 The last node in the list has a pointer which is invalid, a null pointer, and that indicates that there 00:40.050 --> 00:41.610 is no following node. 00:44.000 --> 00:47.960 So the structure will look something like this. We have the first element which has data with the 00:47.960 --> 00:52.110 value 4. The second elements has data with the value 3. 00:52.550 --> 00:55.760 And the first element has a pointer, which is the address of this node. 00:56.630 --> 01:00.410 And then this node has a pointer, which is the address of the next node, and so on. 01:01.520 --> 01:06.920 When we get to the last node, the pointer is invalid, and that is how we know it is the last node. 01:10.240 --> 01:16.180 To iterate through a list, we start at the first node. We get the link pointer, and then we follow 01:16.180 --> 01:16.360 it. 01:16.750 --> 01:18.430 And that will take us to the second node. 01:19.150 --> 01:24.490 Then we get the link points of the second node, and we follow that to the third node, and so on. 01:25.210 --> 01:29.560 When we get to a node with an invalid pointer, we stop. Because that is the last one. 01:32.480 --> 01:36.410 This data structure is known as a forward list, or a singly-linked list. 01:37.160 --> 01:42.650 We can iterate forwards through the list, just by following the pointers. Going backwards is a bit more 01:42.770 --> 01:49.790 involved, but it is possible! The C++ standard library provides a forward_list class, which 01:49.790 --> 01:52.100 is an implementation of the single-linked list. 01:55.350 --> 02:00.300 Adding an element at the back of a linked list involves creating a node for the element. 02:01.620 --> 02:05.460 We go to the last node in the list and get its pointer. 02:06.150 --> 02:11.130 And we make the pointer point to our new node. And that will make our new node, the last node in the 02:11.130 --> 02:11.430 list. 02:11.850 --> 02:14.580 So we node to give it an invalid "next" pointer. 02:15.900 --> 02:20.760 If we are going to insert a node in the middle of the linked list, we node to find the node before it. 02:21.240 --> 02:24.960 Then we node to get its link pointer, and make it point to our new node. 02:25.560 --> 02:31.860 We also node to get the node which follows it, and then our link pointer is going to point to the 02:31.860 --> 02:32.610 following node. 02:33.690 --> 02:38.940 So when we add an element to the list, only the previous element and the element that we are adding 02:38.940 --> 02:39.570 are affected. 02:40.020 --> 02:41.970 The rest of the list is left completely untouched. 02:43.850 --> 02:50.150 So it works like this. If we want to add an element with the value 2 after this element, we get 02:50.150 --> 02:50.960 the link pointer 02:51.590 --> 02:58.040 of this element to point to our new node, and then our link pointer points to the one which followed 02:58.040 --> 02:59.930 the element with the value 3. 03:03.180 --> 03:09.450 To remove an element from a linked list, we go to the previous node again, and we change its link pointer, 03:09.600 --> 03:16.110 so it is pointing to the node which follows our one. And that will detach our node from the list, and then 03:16.110 --> 03:21.240 we can release the memory it is using. And again, only the previous node and the next node are affected. 03:21.900 --> 03:23.640 The rest of the list is entirely untouched. 03:25.200 --> 03:26.190 So this is how it works. 03:26.190 --> 03:31.320 We go to the previous element. We get its link pointer, and we make it point to the element which 03:31.620 --> 03:32.460 follows ours. 03:34.970 --> 03:39.590 List operations are a bit different from the other sequential containers. We will look at those later on. 03:40.280 --> 03:45.140 There is one which is peculiar to forward lists. Usually with a sequential container, 03:45.140 --> 03:48.950 if we want to add or remove an element, we can call insert() and erase(). 03:49.520 --> 03:55.070 These will take an iterator, and these will add or remove an element, just before that iterator. 03:56.960 --> 04:01.100 This requires that the container supports reverse iterators, which forward_list does not do. 04:01.430 --> 04:03.200 It only supports forward iterators. 04:04.070 --> 04:08.990 So instead, there are different member functions: insert_after() and erase_after(). 04:09.680 --> 04:14.960 So these will take an iterator as argument, but they will insert or remove the element which follows 04:14.960 --> 04:15.680 that iterator. 04:18.190 --> 04:20.350 So let's have a quick look at a forward_list. 04:20.860 --> 04:23.050 We need the header. 04:23.980 --> 04:27.160 We create an instance of a list, as you would expect. 04:27.790 --> 04:30.310 We can do a range-for loop, to print out all the elements. 04:32.530 --> 04:35.320 We can call insert_after(). We need to get an iterator. 04:36.520 --> 04:39.260 We are going to do the same example that we had on the slide. 04:39.280 --> 04:43.150 So we are going to insert an element with value 2, after the second element. 04:43.600 --> 04:45.760 So we need an iterator to the second element. 04:46.510 --> 04:50.290 So we get the begin() return value and advance it by 1. 04:53.250 --> 04:54.800 And then we erase that element. 04:54.810 --> 04:58.980 So again, we get the second element, and we call erase_after(). 05:03.060 --> 05:05.850 And there we are, we start off with elements 4, 3 and 1. 05:06.450 --> 05:10.350 We insert an element with value 2 after the element with value 3. 05:11.220 --> 05:15.210 And then we remove the element which followed the element with value 3. 05:15.810 --> 05:17.460 And that takes us back to the original list. 05:18.960 --> 05:20.520 Okay, so that is it for this video. 05:20.760 --> 05:21.630 I will see you next time. 05:21.630 --> 05:23.820 But until then, keep coding!