WEBVTT 00:01.110 --> 00:02.370 Hello, my name is Typhoon. 00:02.370 --> 00:04.920 Welcome to another lecture of our oxalic course. 00:04.920 --> 00:10.980 In this lecture of our oxide course, you will learn about the removing an item from the linked list 00:11.010 --> 00:12.230 a d t. 00:12.390 --> 00:14.130 So let's get started. 00:26.220 --> 00:28.620 So similar to the inserting operation. 00:28.620 --> 00:35.230 The removing operation also has several cases, and there are three cases here. 00:35.250 --> 00:39.840 So firstly, let's actually make this here the first case. 00:40.590 --> 00:45.400 Here, the second case and the third case here. 00:45.420 --> 00:53.080 So similarly here, the removed in the first case, the removed item is in the head. 00:53.100 --> 00:55.410 So in the head. 00:57.320 --> 01:02.630 So which is index is equals to zero. 01:02.810 --> 01:04.880 So index. 01:05.850 --> 01:07.710 Equals to zero. 01:11.170 --> 01:16.720 And the second case is the removed items is in the tail. 01:16.720 --> 01:18.520 So it's in the tail. 01:19.770 --> 01:22.450 Tail and linked list. 01:22.470 --> 01:26.910 So index is our index is going to be index. 01:27.960 --> 01:29.770 Is going to be an. 01:31.860 --> 01:34.680 And minus one. 01:35.550 --> 01:39.130 In case of it's our removed item, it's going to be in the tail here. 01:39.150 --> 01:48.120 So the removed item here in the third case we have a remove item is in the other position of the linked 01:48.120 --> 01:48.270 list. 01:48.270 --> 01:53.010 So in this case, it's going to we're going to write it other here and let's actually use a different 01:53.010 --> 01:53.970 color for other. 01:56.870 --> 01:57.560 Other. 01:57.560 --> 02:00.200 And here then. 02:01.310 --> 02:02.990 It's going to be index. 02:04.880 --> 02:05.990 Index. 02:13.120 --> 02:15.280 Is going to be one. 02:16.480 --> 02:22.840 From one to index N minus two here. 02:22.840 --> 02:26.410 So here, actually, let's write it in the different color. 02:26.410 --> 02:28.090 So from. 02:30.150 --> 02:32.970 From index one. 02:33.000 --> 02:34.440 The first index. 02:36.040 --> 02:38.200 To hear from. 02:39.630 --> 02:40.560 To. 02:43.190 --> 02:43.850 Here. 02:43.850 --> 02:47.600 So from it's going to be in the other. 02:47.690 --> 02:51.020 In the third scenario, our index is index. 02:51.260 --> 02:59.360 From index first index and then from that from the first index until the N minus one index here. 02:59.360 --> 03:02.930 So which is the last index, but minus one here. 03:03.830 --> 03:05.090 So now. 03:07.010 --> 03:08.030 The first case here. 03:08.030 --> 03:12.500 Let's develop the first case and then we're going to create our another cases here. 03:12.500 --> 03:16.640 So first, actually, let's move this here. 03:18.530 --> 03:19.190 Yes. 03:21.350 --> 03:21.950 Here. 03:24.670 --> 03:25.600 Now. 03:26.720 --> 03:28.790 Let's implement the first. 03:29.960 --> 03:31.190 Search here. 03:31.190 --> 03:36.860 So we're going to create a new tree here, which is going to be here. 03:36.860 --> 03:44.390 So we're going to have we have here the remove heat, remove tail and just remove, which is this is 03:44.390 --> 03:46.280 the third case here. 03:46.280 --> 03:47.900 This is third case. 03:47.900 --> 03:50.210 Remove tail is second case. 03:50.920 --> 03:55.660 And remove heat is first case here. 03:55.930 --> 03:59.200 So now let's create our application. 03:59.200 --> 04:01.990 Firstly, we're going to create the case one here. 04:02.320 --> 04:05.110 So the implementation is straightforward here. 04:05.110 --> 04:10.600 So we're going to create we just need to point the heat pointer to the node, which is pointed by the 04:10.600 --> 04:12.450 next pointer of the current heat. 04:12.460 --> 04:16.330 In other words, the second element and delete the first element of the linked list. 04:16.330 --> 04:26.770 So here template the type name T and after that void linked list, we're going to create the. 04:28.580 --> 04:30.080 Remove heat here. 04:30.080 --> 04:33.890 So remove heat. 04:33.890 --> 04:42.200 And after that we can create a condition which is going to be do nothing if the if the list is empty. 04:42.230 --> 04:45.170 Since we don't have anything to remove in this list here. 04:45.170 --> 04:52.820 So my count, if our list count is zero, then just return and do nothing but. 04:54.140 --> 04:56.960 After that, we're going to save the current hit to new node. 04:56.960 --> 04:59.300 So in this case node here. 04:59.810 --> 05:02.090 Node and hit. 05:02.420 --> 05:07.340 And we will point the hit pointer to the element next to the current hit. 05:07.340 --> 05:17.990 So in this case it's going to be the hit equals hit and next year initialize hit to hit next here and 05:17.990 --> 05:23.660 after that now it's safe to remove the first element so delete node. 05:24.350 --> 05:24.950 Here. 05:24.950 --> 05:26.420 After that, we will. 05:29.750 --> 05:33.110 Decrement our count here, which is going to be minus one. 05:33.790 --> 05:35.200 So here. 05:37.860 --> 05:42.380 Decrease the one element from my count since we removed one from the heat. 05:42.450 --> 05:48.600 So as we can see in this code, regardless of the number of the length list element, the complexity 05:48.600 --> 05:55.380 of operation is zero and one, which is the best case scenario here. 05:57.140 --> 05:58.030 Zero one. 05:59.100 --> 06:00.060 So. 06:01.440 --> 06:03.180 For the removed tail operation. 06:03.180 --> 06:07.350 We have to traverse all list elements so that we have two less nodes. 06:07.350 --> 06:11.550 So which are indexes in minus one and N minus two. 06:11.550 --> 06:19.520 And then we set the next pointer to the next pointer of the end to, to the point of null. 06:19.530 --> 06:25.680 So after that we can safely remove the last node since the operation must traverse all list elements. 06:25.680 --> 06:31.110 So the complexity will be here zero here in the if we're going to write it here. 06:31.110 --> 06:34.770 So the complexity is going to be zero multiply by N. 06:34.770 --> 06:40.560 So here we're going to template template type. 06:41.480 --> 06:51.320 Typename t void the linked list we're going to hear t and after that we will remove tail. 06:52.010 --> 07:01.490 So after that, as we're going to as we did in this here, if my if count my count equals to zero, 07:01.520 --> 07:05.240 then return just do nothing. 07:05.420 --> 07:11.510 And after that, if list element is only one, just simply call the remove hit here. 07:11.510 --> 07:20.990 If my count is equal to one, then just simply call the return or remove hit here. 07:20.990 --> 07:24.650 So remove hit and after that we will return here. 07:24.650 --> 07:27.560 Since we removed and completed our operation here. 07:27.560 --> 07:31.940 And after that we need to start a start. 07:33.090 --> 07:33.480 Yeah. 07:33.480 --> 07:35.740 Start to find previous note from the heat. 07:35.760 --> 07:38.850 So in this case, we're going to create the here. 07:39.650 --> 07:40.250 Not. 07:41.270 --> 07:42.570 Not here to. 07:43.820 --> 07:46.160 And previous note. 07:49.840 --> 07:50.710 Hit here. 07:52.000 --> 07:59.650 And after that, we're going to create a candidate of items, candidate of removed items, which is 07:59.650 --> 08:01.270 the element next to the preview node. 08:01.300 --> 08:09.700 Here in this case, we're going to create the node t pointer here and hit points to next. 08:10.990 --> 08:15.460 After that, we will traverse elements until the last until the last elements here. 08:15.460 --> 08:23.650 So in this case, while while the node next here is not equal to null. 08:24.710 --> 08:25.580 Null. 08:25.610 --> 08:30.050 Then we're going to print node three. 08:30.080 --> 08:33.980 Previous node next here. 08:35.430 --> 08:36.290 Next. 08:36.300 --> 08:38.910 And after that node equals node. 08:40.010 --> 08:40.790 Next. 08:42.110 --> 08:51.470 So the then the pre note here previous note now became a tail so that the next pointer of the pre note 08:51.560 --> 08:52.380 points to null. 08:52.400 --> 09:02.090 So in order to do that we're going to create the pre note pre note here next and null here. 09:02.090 --> 09:12.290 So the tail is going to be pre note here so now it's safe to remove the last element delete delete note 09:12.290 --> 09:15.110 and after that we will. 09:16.790 --> 09:22.190 Decrease the decrement the size of our my count since the element is removed here. 09:22.190 --> 09:24.590 So the last operation is the remove operation. 09:24.590 --> 09:28.970 And here this is the complexity of this operation is going to be. 09:29.300 --> 09:31.610 Yeah, the complexity of this operation is going to be. 09:35.220 --> 09:36.150 Yeah, it is. 09:36.960 --> 09:39.660 Uh, it is the same with the heat. 09:39.660 --> 09:40.890 So it's going to be. 09:42.120 --> 09:43.950 Zero and one. 09:43.950 --> 09:51.300 So the best case scenario here and we can also develop our review operation. 09:51.510 --> 09:57.450 This is the last operation which we will remove the least element between the first and last element. 09:57.450 --> 10:02.160 So in this operation, we need to traverse the least element until the selected item is index. 10:02.160 --> 10:09.660 Selected indexes reached so similar to the index of insert operation, we need to find the element before 10:09.660 --> 10:11.760 and after selecting index. 10:11.760 --> 10:18.180 So after we find them we can link them together and then we can safely remove the element in the selected 10:18.180 --> 10:19.320 index here. 10:19.320 --> 10:24.660 So let's create our delete or remove operation here. 10:24.660 --> 10:40.620 So now template Typename here T and after that void the linked list t here and remove remove here just 10:40.620 --> 10:43.630 to remove which is going to get the index parameter here. 10:43.630 --> 10:49.150 And after that, if our list is empty, my count is empty zero. 10:49.180 --> 10:52.930 Then return and do nothing since we don't have anything to return. 10:52.930 --> 10:55.900 And after that let me actually check the lecture time. 10:55.900 --> 10:56.260 Yeah. 10:56.260 --> 10:58.210 So after that return here. 10:58.210 --> 11:00.100 So if our. 11:01.450 --> 11:04.000 And also we're going to also do the. 11:05.050 --> 11:14.200 If here if index is less than zero or index is greater than equal, index is greater than or equal to 11:14.200 --> 11:18.430 my count, then return. 11:20.430 --> 11:22.560 So awesome. 11:22.560 --> 11:26.370 And yeah, in this case, we're going to just return and do nothing. 11:26.370 --> 11:27.990 So if our. 11:28.830 --> 11:30.810 So in this case, it's going to be out of bounds. 11:30.810 --> 11:37.200 So if our index is less than zero or index is equal to or greater than zero, then this is the out of 11:37.200 --> 11:37.710 bounds. 11:37.710 --> 11:40.410 And here then return and do nothing. 11:40.410 --> 11:46.620 So if our, uh, if we don't have anything in our list, then also return signs. 11:46.620 --> 11:48.900 We don't have anything to remove here, so. 11:50.140 --> 11:52.930 Here, we will develop our. 11:54.040 --> 11:56.260 If our index is zero. 11:57.380 --> 12:00.800 Signs if our index is zero. 12:00.800 --> 12:07.490 So this means we are going to delete the first element since we already developed our the remove heat. 12:07.520 --> 12:09.920 Then we're just going to remove the heat here. 12:09.920 --> 12:16.160 So we will execute, remove heat and successfully executed here and removed item. 12:16.160 --> 12:24.740 So if the here after that if our removing or remove if our removing the current tail we're going to 12:24.740 --> 12:27.650 also add the else if here. 12:29.250 --> 12:32.580 Index and my count. 12:32.610 --> 12:33.780 Minus one. 12:34.640 --> 12:36.230 And remove tail. 12:36.980 --> 12:39.350 After that, we can also return here. 12:39.440 --> 12:43.910 So this is also successfully executed and we removed item from the list. 12:43.940 --> 12:48.260 Now let's get started with the our real remove method here. 12:48.260 --> 12:52.390 So now we're going to traverse the list here from the heat. 12:52.400 --> 12:59.960 So note to previous note, please note here and heat here. 13:00.980 --> 13:02.630 Not like this here heat. 13:02.630 --> 13:05.810 And we will find the element before the selected index. 13:05.810 --> 13:08.450 So we're going to create a for loop integer. 13:08.840 --> 13:11.120 Integer is zero here. 13:11.120 --> 13:21.350 E while e less than index minus one, then increment E plus e by one here, increment e by one. 13:21.350 --> 13:28.820 After that we will print here equals previous note pre note. 13:29.650 --> 13:30.520 Next. 13:31.900 --> 13:33.490 And here. 13:36.210 --> 13:39.870 We will the removal remove the element is after the preview node here. 13:39.870 --> 13:40.830 So we will. 13:41.040 --> 13:41.550 Oops. 13:41.790 --> 13:42.450 Here. 13:42.450 --> 13:42.780 Yeah. 13:42.780 --> 13:52.710 So here node t here and not the previous node and the next. 13:54.170 --> 13:55.100 Next year. 13:55.130 --> 14:01.500 After that, the node will be the neighborhood of the previous node. 14:01.520 --> 14:02.720 So if the node is removed. 14:02.720 --> 14:08.390 So in this case, we're going to do the node to the next node. 14:09.410 --> 14:10.280 Node. 14:10.820 --> 14:16.610 Yeah, the next node to the next node is going to be node here. 14:17.940 --> 14:18.720 Next. 14:20.240 --> 14:23.700 And after that we will link the previous node to the next node. 14:23.720 --> 14:26.750 So previous node to. 14:28.230 --> 14:30.570 Next and next node. 14:32.300 --> 14:35.660 And after that, now it's safe to remove the selected index element. 14:35.690 --> 14:39.200 Now we're going to go delete Node. 14:39.350 --> 14:40.640 And after that we. 14:41.990 --> 14:48.920 Need to decrement the decrement count of our list since the one element is removed here. 14:48.920 --> 14:56.140 So as you can see in this code, we will invoke the remove heat operation if the index is equal to zero 14:56.150 --> 15:01.100 and will invoke the remove tail operation here. 15:01.100 --> 15:02.000 Remove tail operation. 15:02.000 --> 15:05.180 If the index equals my count minus one. 15:05.180 --> 15:12.260 So it's not clear that in the best case here, which is remove heat and remove tail is invoked, the 15:12.260 --> 15:14.420 complexity is zero one. 15:14.420 --> 15:21.230 And in the worst case, when the remove tail actual remove tail is invoked, the complex is zero. 15:21.230 --> 15:22.160 And here.