WEBVTT 00:00.620 --> 00:01.880 Hello, my name is Stephanie. 00:01.880 --> 00:04.830 Welcome to another lecture of our Oxford course. 00:04.850 --> 00:10.940 In this lecture we are cplusplus course we will insert an item in the linked list class. 00:10.940 --> 00:12.230 So let's get started. 00:25.790 --> 00:30.230 So let's move to on the insert operation for the Linkedlist class. 00:30.410 --> 00:37.130 So there are four cases for this operation and they are those are the first case is the new item is 00:37.130 --> 00:42.680 inserted at the beginning of the linked list, which is index index of sexual. 00:42.680 --> 00:44.180 Let's do that here. 00:44.810 --> 00:46.730 So which is index. 00:47.880 --> 00:49.020 Equals. 00:50.030 --> 00:56.900 Here equals zero, which index is zero so that it becomes the head here. 00:56.900 --> 01:01.370 So in this case, it's becomes the head. 01:04.120 --> 01:08.080 We also have in the at the second here. 01:08.110 --> 01:09.310 At the second. 01:11.290 --> 01:15.040 We would also have this is the second case. 01:15.250 --> 01:20.440 So the new item is added to an empty linked list. 01:20.560 --> 01:27.760 So if the linked list has only one element, so it's going to be both here in this case of empty list, 01:27.790 --> 01:29.890 the it's going to be hit. 01:31.680 --> 01:33.570 And a tale. 01:35.750 --> 01:38.840 Tail, which in this case it's going to be head and tail. 01:38.840 --> 01:41.780 And we'll point to the only element. 01:41.780 --> 01:48.890 So they are going to be point to the same element, Same element. 01:54.320 --> 01:56.480 And also let's make this like that. 01:59.420 --> 02:00.200 Here. 02:00.410 --> 02:05.150 Also, let's take this here and make it up here. 02:11.330 --> 02:11.900 So. 02:12.200 --> 02:14.240 And the third year. 02:15.420 --> 02:15.720 Here. 02:16.140 --> 02:24.900 The third case is that the new item inserted into the last of the linked list, which is is going to 02:24.900 --> 02:27.330 be the index. 02:28.780 --> 02:31.360 Index is going to be an. 02:32.910 --> 02:33.540 Here. 02:33.540 --> 02:37.050 So the it becomes the new tail here. 02:37.050 --> 02:40.890 So it will become the new tail. 02:42.290 --> 02:44.120 So new. 02:45.020 --> 02:45.650 Tail. 02:48.690 --> 02:53.310 And last here we will talk about is the fourth. 03:00.180 --> 03:08.520 And they also have the fourth, which is the new item is inserted in the other position of linked list 03:08.550 --> 03:12.240 where the index is going to be here index. 03:14.930 --> 03:17.480 Is going to be one. 03:18.180 --> 03:19.350 From one. 03:20.200 --> 03:24.040 To n minus one. 03:24.520 --> 03:33.430 So in this is going to be one to index from one to from one to n minus one. 03:33.430 --> 03:39.460 So let's actually hide this and let's see how to create our insertion. 03:40.850 --> 03:41.570 Process here. 03:41.570 --> 03:43.300 So now here. 03:43.310 --> 03:43.780 Oops. 03:47.300 --> 03:48.740 Let's create the implement. 03:48.890 --> 03:54.980 We will also create an implementation for inserting an operation for cases one and two so we can solve 03:54.980 --> 04:00.680 these problems by creating insert hid operation that in previous lecture we did it here, insert hit, 04:00.680 --> 04:03.740 insert tail and insert here just an insert. 04:03.890 --> 04:12.290 So the implementation of this operation here, after that, we're going to after get here, as you can 04:12.290 --> 04:14.210 see, we defined here get. 04:14.210 --> 04:18.890 And after that we're going to add the insert head here. 04:18.890 --> 04:21.530 So with length list. 04:21.530 --> 04:23.780 And we also need to add the template here. 04:23.810 --> 04:27.590 The template is going to be type name. 04:28.550 --> 04:30.560 Template typing t here. 04:30.560 --> 04:32.870 And after that void the Linkedlist. 04:32.870 --> 04:37.880 As you can see here, our insertions are our returns. 04:37.910 --> 04:38.480 Nothing here. 04:38.480 --> 04:41.140 So that's why we created a void here. 04:41.150 --> 04:47.360 So now it's going to be t and insert insert heat. 04:47.360 --> 04:52.040 So it's going to we don't need val, we don't need index if we know where we are adding. 04:52.040 --> 05:00.350 So in, in insert we have to, we have to here but in insert. 05:02.190 --> 05:02.750 Hit. 05:03.210 --> 05:10.710 We don't have we just have the value that we're going to insert at the head of our list. 05:10.710 --> 05:13.530 So let's quickly clear this and come here. 05:13.530 --> 05:17.810 So now we're going to add the insert hit. 05:17.820 --> 05:21.690 And as you can see here, we just need one as a parameter. 05:22.770 --> 05:24.780 So after that. 05:25.680 --> 05:27.000 Uh, actually here. 05:27.210 --> 05:34.530 So after that, we're going to inside the inserted function, we're going to create a new node. 05:34.560 --> 05:37.980 So node to note here. 05:37.980 --> 05:39.660 So the new node is going to be. 05:40.840 --> 05:41.890 Template. 05:42.620 --> 05:43.070 Not. 05:43.850 --> 05:50.560 It's going to be a template and value here after that. 05:50.570 --> 05:58.010 So the current node or the current heat will no longer become a heat. 05:58.010 --> 06:02.780 So the next pointer of the new node will point to the current heat here. 06:02.780 --> 06:09.500 So the node next is going to be point to the current heat. 06:10.190 --> 06:14.840 After that, let's actually create the new node to become the heat. 06:14.840 --> 06:18.530 So here we're going to create heat equals node. 06:19.190 --> 06:21.200 Sign the heat to node here. 06:21.200 --> 06:23.750 So let's actually create another condition here. 06:23.750 --> 06:25.190 So another condition. 06:25.190 --> 06:32.480 So if the link list is empty, the tail is also the heat as we discussed in third case here. 06:32.480 --> 06:40.340 So if the if the my count is equals zero, then our tail is also heat. 06:41.760 --> 06:46.390 And after that we will add the after outside the if. 06:46.410 --> 06:51.870 Here we will add one element, which is going to be a increment, the one element here. 06:51.870 --> 06:58.200 So we inserted heat and after insertion here, we will add one element here. 06:58.200 --> 07:01.740 And as you can see here, the element is going to be plus one. 07:02.580 --> 07:05.640 And we will add this element inside our list. 07:06.870 --> 07:07.650 Here. 07:09.380 --> 07:17.660 So as you can see here, the insert hit operation will create a new node that assigns it to a new hit. 07:17.660 --> 07:25.670 So if the linked list is empty before applying this operation, the new node also become the tail. 07:27.260 --> 07:28.880 So, um. 07:30.720 --> 07:31.380 For this. 07:31.410 --> 07:35.160 The complexity of this operation is going to be zero. 07:36.170 --> 07:37.130 And one. 07:38.750 --> 07:42.110 So regardless of the number of the for the linked list is limited. 07:42.110 --> 07:45.530 So it's actually not that complex here for case three. 07:45.560 --> 07:54.230 As I as we learned earlier of this lecture, in the inserting operation, we can implement the insert 07:54.260 --> 07:55.340 tail operation. 07:55.340 --> 07:57.290 So the operation is simple and efficient. 07:57.290 --> 08:02.270 So we just need to create a new node and then assign it to the new tail. 08:03.170 --> 08:08.180 So the next pointer to previous tail will point to the new tail here. 08:08.180 --> 08:11.630 So let's actually delete this and come here. 08:11.630 --> 08:15.380 We create our insert hit. 08:16.460 --> 08:19.160 Insert is developed insert tail here. 08:19.160 --> 08:23.960 We're going to add now and here let's go to our coding process. 08:23.960 --> 08:29.120 So now we're going to also create a type name after the insert head. 08:29.740 --> 08:34.630 So the template type name. 08:36.930 --> 08:43.170 Name is going to be T And after that void, the length list is going to be T here. 08:43.170 --> 08:45.210 Also the insert tail. 08:45.720 --> 08:47.730 Insert tail. 08:47.760 --> 08:48.150 Oops. 08:48.840 --> 08:51.270 Insert tail here. 08:52.260 --> 08:53.710 Insert tail. 08:53.730 --> 08:56.950 And now we will pass that value here. 08:56.970 --> 08:59.220 So let's create another condition here. 08:59.220 --> 09:02.670 So if the linked list is empty, just simply invoke the insert. 09:03.630 --> 09:11.310 So here we're going to make it the if my count is empty or yeah is equal to zero, then it's going to 09:11.310 --> 09:14.730 be insert hit and just end the function here. 09:14.730 --> 09:16.410 So we will return function. 09:16.410 --> 09:26.910 So insert hit and we will pass that value to our insert hit which this will pass to our insert hit here. 09:26.970 --> 09:27.930 So. 09:30.110 --> 09:31.520 In this case is going to give. 09:31.550 --> 09:33.470 It's going to be well here. 09:33.470 --> 09:34.940 After that, we will return. 09:36.080 --> 09:36.740 Return. 09:38.700 --> 09:41.130 So if this condition is not. 09:42.210 --> 09:44.990 True, then we will create a new node. 09:45.020 --> 09:50.150 So not here, not t, not here. 09:50.150 --> 09:59.600 So new node is going to be T and we will pass value here and here we will create this code and I will 09:59.600 --> 10:01.340 explain now here. 10:01.340 --> 10:03.080 So we will write this code. 10:03.080 --> 10:07.930 So in case of that, the current tail will no longer become a tail. 10:07.940 --> 10:13.190 So the next pointer of the current tail will point to the new node here. 10:13.190 --> 10:21.110 So and we will also then a new node B, it's going to be become the tail, so tail equals node. 10:21.110 --> 10:30.020 And after that we will add one element as we did in the add in the ADD heat method here. 10:30.020 --> 10:33.530 So we will add one element plus one here. 10:33.710 --> 10:35.930 So in this case it's going to be. 10:37.530 --> 10:40.150 My count of sexual. 10:40.150 --> 10:41.310 Let's delete this. 10:43.830 --> 10:44.460 Here. 10:44.550 --> 10:48.550 So the my count is going to be plus plus. 10:48.570 --> 10:49.320 That's it. 10:50.720 --> 10:56.480 Also, please keep in mind that we might run the insert tail operation. 10:56.480 --> 11:00.770 Insert tail operation when the linked list has no elements. 11:00.770 --> 11:07.520 So if this occurs, the case two as we discussed in previous lecture and in the beginning of this lecture, 11:07.550 --> 11:14.330 the case two will happen and we can simply invoke the insert hit method. 11:14.630 --> 11:19.820 So the complexity of the insert tail method is same as our insert head method. 11:19.820 --> 11:22.910 So in this case it's going to be zero multiply by one here. 11:23.210 --> 11:28.970 So regardless of the number of the linked is list elements here, so the complexity is going to be same. 11:28.970 --> 11:31.790 So it will even invoke the insert head operation. 11:31.790 --> 11:38.780 Since the insert operation complexity is also zero one here. 11:38.780 --> 11:45.500 So now let's actually create the case for here which we need to traverse the elements for the linked 11:45.500 --> 11:50.910 list to find two elements where we want to insert the new element between them. 11:50.910 --> 11:53.640 So we will call them previous node and next node. 11:53.640 --> 12:00.720 So after we find them, we then create a new node point to the next pointer of previous node, so to 12:00.720 --> 12:05.490 new node and then point to the next pointer of the new node to the next node. 12:05.520 --> 12:07.560 So the implementation of the insert operation. 12:07.560 --> 12:12.840 So it might be complex here, but after we writing our code you will understand all of this. 12:12.840 --> 12:14.640 So after our. 12:15.450 --> 12:19.410 Insert tail method, we will create the again, the template here. 12:20.040 --> 12:21.870 So template. 12:22.170 --> 12:25.950 Template is going to be type name T. 12:28.300 --> 12:31.120 Here and we will create an insert method. 12:31.120 --> 12:34.120 So in this insert method here, we will add. 12:34.920 --> 12:36.810 The index and value. 12:37.530 --> 12:41.640 Except as you can see, we just had the value here because we are inserting. 12:41.640 --> 12:43.360 We know where we inserting, right. 12:43.380 --> 12:45.200 In this case, we're going to insert the heat. 12:45.210 --> 12:46.710 In this case, we're going to insert a tail. 12:46.740 --> 12:49.470 But in this case, we're going to need the index here. 12:49.470 --> 12:52.980 So that's why we're going to create two parameters. 12:53.340 --> 13:00.930 And here it's going to be void length list T here insert. 13:01.960 --> 13:04.180 Insert just an insert here. 13:04.180 --> 13:06.460 So first we have index and Val. 13:06.490 --> 13:09.900 And first we need to check if the index is out of bounds. 13:09.910 --> 13:23.770 So if our if our index is less than zero or our index is greater than my count, then just return here. 13:23.980 --> 13:28.090 If this not happen, let's run our function here. 13:28.090 --> 13:28.920 So if the. 13:30.170 --> 13:33.780 Let's actually insert a new hit. 13:33.800 --> 13:40.820 So if index is equal to zero, then insert hit. 13:41.360 --> 13:43.160 And we will pass our value. 13:43.160 --> 13:48.590 And as you can see, we are again using the insert hit because if our index is zero, then we can also 13:48.590 --> 13:49.720 insert hit here. 13:49.730 --> 13:52.880 So that's why we executed this, created this. 13:52.910 --> 13:58.580 If and after that then we didn't miss the our insert is completed and just return here. 13:59.360 --> 14:04.070 After that, uh, if if we are inserting a new tail. 14:04.070 --> 14:04.670 So. 14:06.190 --> 14:07.570 Else if. 14:07.660 --> 14:16.930 If our else if in our index is my count equals to my count, then we will insert a new tail. 14:17.980 --> 14:21.760 So in this case, I will explain all of things now. 14:21.910 --> 14:29.380 Insert insert tail is going to be val and return. 14:29.380 --> 14:30.700 So in this case. 14:31.700 --> 14:39.530 Uh, it will run if our node has zero elements. 14:39.530 --> 14:48.830 But if here, if, for example, if our in this case we have five elements and we we want to add in 14:48.830 --> 14:54.170 the fifth index, then we can also use the insert method for this. 14:54.170 --> 14:56.420 So we don't need to write separate method for this. 14:56.420 --> 15:03.830 So that's why we created this conditions for more efficient programming here. 15:04.130 --> 15:05.480 So now. 15:08.270 --> 15:10.580 We will start to find previous note from the Heat. 15:10.610 --> 15:12.170 In order to do that, we will create. 15:12.200 --> 15:12.890 Note here. 15:12.890 --> 15:14.120 Previous note here. 15:17.310 --> 15:22.680 Note it's going to be previous, not pre note here. 15:22.680 --> 15:24.700 It's going to be hit here. 15:24.720 --> 15:31.110 Hit And after that we'll need to traverse the elements until the selected item is found. 15:31.110 --> 15:33.690 So we will add four here. 15:33.690 --> 15:43.620 Integer is zero and while our e is less than index, then our index minus one then plus plus E here. 15:44.790 --> 15:45.540 And we will. 15:46.630 --> 15:47.650 Some previous node. 15:48.130 --> 15:51.640 Previous node equal Previous node. 15:52.450 --> 15:54.220 And next. 15:56.720 --> 16:04.070 Okay, So after that, we need to create the next node, which is the element after the previous node 16:04.100 --> 16:04.810 here. 16:04.820 --> 16:18.470 So note here the next node and assign it to previous node previous node and we will make it next here. 16:19.100 --> 16:19.460 Oops. 16:19.910 --> 16:20.870 Next. 16:21.080 --> 16:22.040 And also delete. 16:22.840 --> 16:23.090 Because. 16:24.970 --> 16:25.360 Here. 16:25.780 --> 16:28.600 So we will also make. 16:31.330 --> 16:32.530 Uh, also create a new node. 16:32.560 --> 16:33.520 Firstly here. 16:34.090 --> 16:41.200 So note here the oops node to node. 16:41.230 --> 16:51.780 The new node is going to be T, which is we will pass value here and after that we will insert, insert 16:51.910 --> 16:53.950 this, insert this new node here. 16:53.950 --> 16:59.170 So we will insert this new node between the previous node and the next node. 16:59.200 --> 17:00.130 So. 17:02.160 --> 17:04.230 Not here. 17:04.260 --> 17:05.280 Next. 17:07.450 --> 17:08.650 And next not. 17:11.600 --> 17:17.660 And previous note we will insert previous node to our next and it's going to be node here. 17:18.680 --> 17:23.930 And we ask after that signs we are executing the insert after insert operation. 17:23.930 --> 17:31.190 We're going to add one element as we did in the insert tail and insert heat method. 17:32.940 --> 17:34.230 So my count. 17:34.260 --> 17:35.030 Plus, plus. 17:35.190 --> 17:43.350 So since we need to traverse the list element, the complexity of this insert operation is n here. 17:45.360 --> 17:52.980 So, however, in the best case, the complexity is going to be here less best case, the complexity 17:52.980 --> 17:59.970 is going to be zero one, as in insert it and insert tile. 17:59.970 --> 18:06.960 So that's because since we might insert a hit, so here our tail or after the operation. 18:06.960 --> 18:09.780 So complexity of this code here. 18:10.690 --> 18:17.790 Complexity of this code is actually let me write this and make it right here. 18:17.800 --> 18:18.700 So. 18:21.390 --> 18:26.930 The complexity of this code is zero one. 18:26.940 --> 18:29.120 Signs are inserted. 18:29.130 --> 18:31.530 Complexity is zero one. 18:31.530 --> 18:37.650 That's because we know where we're inserting our value and insert is the same like the insert here. 18:37.650 --> 18:40.920 We know where we ending our. 18:42.070 --> 18:42.670 A value. 18:42.670 --> 18:48.250 But in this case, we don't know where our index is or where our values. 18:48.250 --> 18:52.120 That's why we have the o n here. 18:52.510 --> 18:55.540 So n is the index here. 18:55.540 --> 18:56.320 So. 18:57.130 --> 18:59.830 If that's why we added this here. 18:59.830 --> 19:07.270 So to reduce the complexity and a bit more code efficiency for our C plus plus.