1 00:00:00,710 --> 00:00:01,700 Welcome back. 2 00:00:01,700 --> 00:00:07,130 Now in this video, let's discuss what we have to do as part of the question and how we will do it. 3 00:00:07,130 --> 00:00:12,140 And then we will also discuss the time and space complexity for these instance methods. 4 00:00:12,140 --> 00:00:12,620 All right. 5 00:00:12,620 --> 00:00:13,700 So let's get started. 6 00:00:13,700 --> 00:00:18,050 Now the first thing which is mentioned in the question is that we should be able to create a singly 7 00:00:18,050 --> 00:00:19,130 linked list object. 8 00:00:19,130 --> 00:00:19,460 All right. 9 00:00:19,460 --> 00:00:20,900 So let's see how we can do this. 10 00:00:20,900 --> 00:00:23,780 Now we have seen that for this we will use a class right. 11 00:00:23,780 --> 00:00:28,520 In a previous video we have discussed that a class is a blueprint to create objects. 12 00:00:28,520 --> 00:00:32,060 So over here we will have a class singly linked list. 13 00:00:32,060 --> 00:00:33,890 And you can see that in the question. 14 00:00:33,890 --> 00:00:37,190 It was mentioned that the singly linked list should have a head and tail. 15 00:00:37,190 --> 00:00:42,470 So when we have the constructor over here, we will just say this dot head is equal to null and this 16 00:00:42,470 --> 00:00:45,710 dot tail is equal to null because initially it's just going to be empty. 17 00:00:45,710 --> 00:00:47,840 And then we have an extra property over here. 18 00:00:47,840 --> 00:00:50,900 Now it's good to have we can track the size of the linked list. 19 00:00:50,900 --> 00:00:55,190 So initially as there is no node we will have this dot size is equal to zero. 20 00:00:55,190 --> 00:00:57,470 And then we have the node class over here. 21 00:00:57,470 --> 00:01:02,480 Now it's mentioned in the question that every node should have two properties. 22 00:01:02,480 --> 00:01:05,180 One is val and the second property is next right. 23 00:01:05,180 --> 00:01:07,340 So that's why we have two properties over here. 24 00:01:07,340 --> 00:01:13,190 So when we create a node it will have a value which is the value which is passed to it when we create 25 00:01:13,190 --> 00:01:13,610 the node. 26 00:01:13,610 --> 00:01:16,040 And then next initially we'll just point to null. 27 00:01:16,040 --> 00:01:18,080 So we have these two classes over here. 28 00:01:18,080 --> 00:01:23,660 Now we will use this class over here class singly linked list to solve the first part of the question, 29 00:01:23,660 --> 00:01:26,240 which is to create a singly linked list object. 30 00:01:26,240 --> 00:01:29,030 Now for this let's say we want to call this SL. 31 00:01:29,030 --> 00:01:35,330 So if we just want to call this SL then we can say const sl is equal to new singly linked list. 32 00:01:35,330 --> 00:01:38,480 Now by calling this we will be creating an object. 33 00:01:38,480 --> 00:01:39,710 And this is the object over here. 34 00:01:39,710 --> 00:01:43,040 Now you can see that this is very much similar to having a new array. 35 00:01:43,040 --> 00:01:43,250 Right. 36 00:01:43,250 --> 00:01:45,830 You may have seen something like this const array. 37 00:01:46,460 --> 00:01:49,220 Let's say r is equal to new. 38 00:01:49,220 --> 00:01:50,660 And then we may have array. 39 00:01:50,660 --> 00:01:52,700 And you can pass the size for example. 40 00:01:52,700 --> 00:01:53,030 Right. 41 00:01:53,030 --> 00:01:53,780 Let's say ten. 42 00:01:53,780 --> 00:01:55,520 Now again this is very much similar right. 43 00:01:55,520 --> 00:02:00,860 So you can see over here again singly linked list is not an inbuilt thing which we have in JavaScript. 44 00:02:00,860 --> 00:02:02,660 So we have defined the class over here. 45 00:02:02,660 --> 00:02:06,080 And using this class we will create the singly linked list object. 46 00:02:06,080 --> 00:02:07,790 So that's the first part of the question. 47 00:02:07,790 --> 00:02:09,560 And you can see it's pretty straightforward. 48 00:02:09,560 --> 00:02:14,330 Now for the remaining part of the question we will add instance methods in the class over here. 49 00:02:14,330 --> 00:02:17,540 We have seen previously that when you have a class you will have objects. 50 00:02:17,540 --> 00:02:19,070 And objects can have properties. 51 00:02:19,070 --> 00:02:20,450 So these are the properties. 52 00:02:20,450 --> 00:02:22,310 And then it can have instance methods. 53 00:02:22,310 --> 00:02:22,580 Right. 54 00:02:22,580 --> 00:02:24,530 So we will have instance methods. 55 00:02:24,530 --> 00:02:30,440 And that's going to be these five methods over here which is get index get add index added head and 56 00:02:30,440 --> 00:02:33,650 then add a tail added index and delete at index. 57 00:02:33,650 --> 00:02:36,260 So let's go ahead and see how we can implement these. 58 00:02:36,260 --> 00:02:38,330 So the first one over here is already done. 59 00:02:38,330 --> 00:02:40,880 Now let's proceed and go to get index. 60 00:02:42,280 --> 00:02:44,470 All right, so we are over here at Getindex. 61 00:02:44,470 --> 00:02:48,520 Now, let's say we already have a singly linked list and let it look like this. 62 00:02:48,520 --> 00:02:50,380 So we have one node with value one. 63 00:02:50,380 --> 00:02:52,750 And then we have a node with value two. 64 00:02:52,780 --> 00:02:54,790 We have a node with value three etc.. 65 00:02:54,790 --> 00:02:59,350 And again over here when we want to create this node we will call the node class. 66 00:02:59,350 --> 00:03:03,700 So we will just say for example if you want to call this one we can say const. 67 00:03:03,700 --> 00:03:05,770 And then let's say the name of this is one. 68 00:03:05,770 --> 00:03:07,630 So that's equal to new. 69 00:03:07,630 --> 00:03:10,330 And then this is the node class that we have written. 70 00:03:10,330 --> 00:03:12,250 And then we will just pass the value to it. 71 00:03:12,250 --> 00:03:13,960 So this will call the constructor. 72 00:03:13,960 --> 00:03:16,600 And it will create a node with value one. 73 00:03:16,600 --> 00:03:19,810 And the next is initially going to point to null. 74 00:03:19,810 --> 00:03:21,490 So this will be created. 75 00:03:21,490 --> 00:03:25,450 And then we'll have to create the next node and we have to add it etc.. 76 00:03:25,450 --> 00:03:28,810 So we will see over here how we do that in the next functions. 77 00:03:28,810 --> 00:03:29,170 All right. 78 00:03:29,200 --> 00:03:32,320 Now for now let's say that we already have the singly linked list. 79 00:03:32,320 --> 00:03:36,280 So we have a node with value one which is pointing to a node with value two. 80 00:03:36,280 --> 00:03:39,730 And that is pointing to this node over here with value three which is pointing to null. 81 00:03:39,730 --> 00:03:42,280 So the head is over here, which is this node over here. 82 00:03:42,280 --> 00:03:43,360 And this is the tail. 83 00:03:43,360 --> 00:03:46,840 So this is the head and this is the tail of the singly linked list. 84 00:03:46,840 --> 00:03:51,700 Now let's say we want to get the node at index two. 85 00:03:51,730 --> 00:03:53,320 So let's say index is equal to two. 86 00:03:53,320 --> 00:03:56,230 And we are calling the get index function over here. 87 00:03:56,230 --> 00:03:58,360 And the index is equal to two. 88 00:03:58,360 --> 00:03:59,620 Now let's see what happens. 89 00:03:59,620 --> 00:04:04,120 And again remember it's mentioned in the question that the singly linked list is zero indexed. 90 00:04:04,120 --> 00:04:07,840 So that means that this node over here will be treated as index zero. 91 00:04:07,870 --> 00:04:10,750 This one over here will be treated as being at index one. 92 00:04:10,750 --> 00:04:13,120 And over here we will treat it as index two. 93 00:04:13,150 --> 00:04:13,750 All right. 94 00:04:13,780 --> 00:04:16,270 Now we will have to use a variable. 95 00:04:16,270 --> 00:04:17,830 Let's say we call it current. 96 00:04:17,830 --> 00:04:20,560 And this is going to point at the head initially. 97 00:04:20,560 --> 00:04:27,670 And then we will just keep iterating through the singly linked list till we get the counter equal to 98 00:04:27,670 --> 00:04:28,570 the index over here. 99 00:04:28,570 --> 00:04:29,650 So we'll have a counter. 100 00:04:29,650 --> 00:04:31,450 So let's say counter is equal to zero. 101 00:04:31,450 --> 00:04:36,310 And you can see that currently this current over here is pointing at index zero. 102 00:04:36,310 --> 00:04:38,380 And we have our counter is equal to zero. 103 00:04:38,380 --> 00:04:44,950 Now we will keep moving the current over here towards the next in the next direction till the counter 104 00:04:44,950 --> 00:04:47,440 becomes equal to the index which is given to us. 105 00:04:47,440 --> 00:04:50,200 So over here zero and two are not equal. 106 00:04:50,200 --> 00:04:51,640 So let's move the counter. 107 00:04:51,640 --> 00:04:53,590 So the counter comes over the the current. 108 00:04:53,590 --> 00:04:54,700 So let's move the current. 109 00:04:54,700 --> 00:04:56,470 So current comes to the next node. 110 00:04:56,470 --> 00:04:57,970 And we increment the counter. 111 00:04:57,970 --> 00:04:59,680 So counter becomes equal to one. 112 00:04:59,680 --> 00:05:01,810 Now still one is not equal to two. 113 00:05:01,840 --> 00:05:04,810 Therefore we are again going to move the current pointer. 114 00:05:04,810 --> 00:05:05,050 All right. 115 00:05:05,050 --> 00:05:06,970 So it's going to move to the next node. 116 00:05:06,970 --> 00:05:08,230 So we get it over here. 117 00:05:08,710 --> 00:05:11,080 And we again increment the counter. 118 00:05:11,080 --> 00:05:12,700 The counter becomes equal to two. 119 00:05:12,700 --> 00:05:16,510 And now you can see that the counter is equal to the index. 120 00:05:16,510 --> 00:05:20,290 Both are equal to two right now because the counter is equal to index. 121 00:05:20,290 --> 00:05:22,630 We have found the node at the index. 122 00:05:22,630 --> 00:05:24,730 And then we can just return current. 123 00:05:25,270 --> 00:05:27,190 And current is pointing to this node. 124 00:05:27,190 --> 00:05:29,800 So we will be returning three which is this node over here. 125 00:05:29,800 --> 00:05:32,260 So this is how we will deal with the get index function. 126 00:05:32,260 --> 00:05:32,680 All right. 127 00:05:32,680 --> 00:05:39,490 Now remember if the index which is passed to us is less than zero or if the index is greater than equal 128 00:05:39,490 --> 00:05:42,430 to the length of the singly linked list, then it's just invalid. 129 00:05:42,430 --> 00:05:45,790 And in that case, as per the question, we will just return minus one. 130 00:05:45,790 --> 00:05:48,040 Now, even if it's equal to the length. 131 00:05:48,040 --> 00:05:48,880 Also it's invalid. 132 00:05:48,880 --> 00:05:52,360 For example, over here you can see the indices are zero, one and two. 133 00:05:52,360 --> 00:05:53,890 And the length over here is three. 134 00:05:53,890 --> 00:05:56,260 So at index three you can see there is nothing. 135 00:05:56,260 --> 00:06:00,580 So that's why if the index is greater than equal to the length or less than zero because the first one 136 00:06:00,580 --> 00:06:01,240 is zero right. 137 00:06:01,240 --> 00:06:04,510 In these in in these cases we will just return minus one. 138 00:06:04,510 --> 00:06:07,270 So this is how we solve the get index function. 139 00:06:07,270 --> 00:06:12,970 Now let's take a look at the complexity analysis of the get index um function which you have written. 140 00:06:12,970 --> 00:06:19,840 Now if we want to get the node at index, then we can say that the time complexity is going to be of 141 00:06:19,840 --> 00:06:23,260 the order of index, and the space complexity is constant space. 142 00:06:23,260 --> 00:06:25,240 We are not using any extra space now. 143 00:06:25,240 --> 00:06:31,090 The time complexity is of the order of index, because you can see we have to keep traversing the singly 144 00:06:31,090 --> 00:06:32,920 linked list till we reach the index. 145 00:06:32,920 --> 00:06:37,750 Now, in the worst case this is going to be time complexity of the order of n, right. 146 00:06:37,750 --> 00:06:42,430 So for example, if you want to get this node or if it's a very big singly linked list, and let's say 147 00:06:42,430 --> 00:06:44,380 we want to get something very close to the end. 148 00:06:44,380 --> 00:06:49,630 So in that case we can say the time complexity is of the order of n and the space complexity is constant 149 00:06:49,630 --> 00:06:50,230 space. 150 00:06:50,320 --> 00:06:50,860 All right. 151 00:06:50,860 --> 00:06:53,620 So we are done with this and we are done with this as well. 152 00:06:53,620 --> 00:07:00,190 Now let's proceed and see how we can implement an instance method to add a node at the head of the singly 153 00:07:00,190 --> 00:07:00,880 linked list. 154 00:07:01,150 --> 00:07:01,600 All right. 155 00:07:01,630 --> 00:07:05,890 Now for the added head function you can see over here the value is passed. 156 00:07:05,890 --> 00:07:07,180 The value has to be passed. 157 00:07:07,180 --> 00:07:08,680 So we will take this value. 158 00:07:08,680 --> 00:07:13,210 And we will create a node which has the value which is the given value. 159 00:07:13,210 --> 00:07:14,920 And then which is pointing to null. 160 00:07:14,920 --> 00:07:17,110 So for this we will use the node class. 161 00:07:17,110 --> 00:07:19,750 So we have seen that we have a class node right. 162 00:07:20,590 --> 00:07:26,260 Now inside this there is a constructor, and in the constructor we are passing the value. 163 00:07:28,170 --> 00:07:29,340 And then over here. 164 00:07:29,340 --> 00:07:33,660 Remember inside this we are going to say this dot value is this value which is passed to it. 165 00:07:33,660 --> 00:07:35,610 And this dot next is equal to null. 166 00:07:35,610 --> 00:07:37,230 So that's how we will have a node. 167 00:07:37,230 --> 00:07:39,330 And it has two properties which is value. 168 00:07:39,330 --> 00:07:42,390 And the next and next is going to point to null initially. 169 00:07:42,390 --> 00:07:46,590 And then the value of the node is going to be the value which is passed to it. 170 00:07:46,590 --> 00:07:48,060 So this is what we will do. 171 00:07:48,060 --> 00:07:53,280 Now let's proceed and see how we will insert it at the head of the given singly linked list. 172 00:07:53,310 --> 00:07:54,990 Now there are two possibilities. 173 00:07:54,990 --> 00:07:56,460 Let's say the head is null. 174 00:07:56,460 --> 00:08:01,590 That is, the singly linked list is empty or there is no node at this in the singly linked list. 175 00:08:01,590 --> 00:08:06,450 If this is the case, then we will just take this node which we just now created. 176 00:08:06,450 --> 00:08:12,060 And then we will say that the head and tail of the singly linked list is this node itself. 177 00:08:12,330 --> 00:08:12,690 All right. 178 00:08:12,690 --> 00:08:14,790 So then this becomes our singly linked list. 179 00:08:14,790 --> 00:08:17,550 And the head and the tail is both this node itself. 180 00:08:17,550 --> 00:08:20,460 Now if this is not the case that is if the head is not null. 181 00:08:20,460 --> 00:08:23,550 So let's say there are already some nodes and they have some values. 182 00:08:23,550 --> 00:08:26,430 Let's say we have the value one, two, three, etc. over here. 183 00:08:26,430 --> 00:08:28,230 So this is our singly linked list. 184 00:08:28,230 --> 00:08:29,940 And then we have created this node. 185 00:08:29,940 --> 00:08:34,170 Now what we have to do is at the moment this is pointing to NULL over here. 186 00:08:34,170 --> 00:08:36,030 Right now this has to be changed. 187 00:08:36,030 --> 00:08:39,090 And we have to make this point to the existing head. 188 00:08:39,090 --> 00:08:41,130 So we will have the node with value over here. 189 00:08:41,130 --> 00:08:43,590 And it's going to point to the existing head. 190 00:08:43,590 --> 00:08:47,850 And then we will just change the head of the singly linked list to this node over here. 191 00:08:49,100 --> 00:08:49,760 In this way. 192 00:08:49,760 --> 00:08:53,450 You can see we have added this node at the head of the given singly linked list. 193 00:08:53,450 --> 00:08:58,220 So this is how we will implement the added head value added head instance method. 194 00:08:58,220 --> 00:08:58,640 All right. 195 00:08:58,640 --> 00:09:02,750 Now let's take a look at the time and space complexity of this method. 196 00:09:02,750 --> 00:09:08,660 Now over here you can see the time and space complexity is going to be O of one or constant time and 197 00:09:08,660 --> 00:09:09,620 constant space. 198 00:09:09,620 --> 00:09:10,340 Why is that so. 199 00:09:10,340 --> 00:09:11,960 Because we don't need to traverse right. 200 00:09:11,960 --> 00:09:13,880 We just need to have some checks. 201 00:09:13,880 --> 00:09:15,770 This is going to be taking constant time. 202 00:09:15,770 --> 00:09:18,620 Checking if the head is null or not is a constant time operation. 203 00:09:18,620 --> 00:09:23,990 And then if it is null then over here we are just setting the head and tail to this node. 204 00:09:23,990 --> 00:09:26,600 Again you can see these are just constant time operations. 205 00:09:26,600 --> 00:09:27,770 They don't scale. 206 00:09:28,220 --> 00:09:31,070 And even if you have a very big linked linked list, right. 207 00:09:31,070 --> 00:09:35,690 If the singly linked list, let's say has hundreds of nodes, even then we know the head and we will 208 00:09:35,690 --> 00:09:39,650 just take this node and we will make it point to the existing head and make this the head. 209 00:09:39,650 --> 00:09:44,270 So you can see we it's, it's, it's, it's taking place in constant time operations. 210 00:09:44,270 --> 00:09:46,130 It's not that there are operations. 211 00:09:46,130 --> 00:09:49,790 The number of operations will scale with the inputs size scaling. 212 00:09:49,790 --> 00:09:54,380 So that's why we can see that this is going to happen in constant time and constant space. 213 00:09:54,380 --> 00:09:54,860 All right. 214 00:09:54,860 --> 00:09:56,150 So we are done with these three. 215 00:09:56,150 --> 00:09:59,060 Now let's proceed to the next one which is add at tail. 216 00:09:59,450 --> 00:10:01,610 Now over here also the value is passed to us. 217 00:10:01,610 --> 00:10:04,190 So we take this value and we make a node out of it. 218 00:10:04,190 --> 00:10:06,320 And initially it's going to point to null. 219 00:10:06,320 --> 00:10:08,390 Now let's check if the head is null. 220 00:10:08,390 --> 00:10:09,320 If the head is null. 221 00:10:09,320 --> 00:10:15,110 Again we take this node and we are going to make the head and tail point to this particular node over 222 00:10:15,110 --> 00:10:15,470 here. 223 00:10:15,470 --> 00:10:17,870 So that's similar to what we have seen in the previous function. 224 00:10:17,870 --> 00:10:21,140 Now if this is not the case, let's say there is already a linked list. 225 00:10:21,140 --> 00:10:23,420 Let's say it looks it's looking something like this. 226 00:10:23,420 --> 00:10:24,800 So there are values over here. 227 00:10:24,800 --> 00:10:28,250 Now what we need to do is we take the node which we created. 228 00:10:28,250 --> 00:10:29,780 So we have the node over here. 229 00:10:29,780 --> 00:10:32,750 Now we will take the existing tail. 230 00:10:32,750 --> 00:10:33,830 This is the existing tail. 231 00:10:33,830 --> 00:10:37,790 And you can see that the singly linked list has the head and tail property. 232 00:10:37,790 --> 00:10:39,590 So we can access the tail. 233 00:10:39,590 --> 00:10:40,970 So we access the tail. 234 00:10:40,970 --> 00:10:44,750 And then we will make the existing tail point to the new node. 235 00:10:44,750 --> 00:10:46,730 So we will make it point to the new node. 236 00:10:46,730 --> 00:10:49,160 So we will say tail this dot tail dot. 237 00:10:49,160 --> 00:10:51,800 Next is equal to the particular node which we created. 238 00:10:51,800 --> 00:10:53,720 And then we will reassign the tail. 239 00:10:53,720 --> 00:10:57,860 We will change this and we will make this particular node over here the tail. 240 00:10:57,950 --> 00:10:59,750 So this is how we will add at the tail. 241 00:10:59,750 --> 00:11:00,200 All right. 242 00:11:00,230 --> 00:11:05,060 Now let's take a look at the time and space space complexity of this instance method. 243 00:11:05,060 --> 00:11:10,850 Now again because we know the tail, even if this is a very big singly linked list, we don't need to 244 00:11:10,850 --> 00:11:13,670 traverse the singly linked list to reach the tail. 245 00:11:13,700 --> 00:11:16,010 Again, that's because we have the tail property. 246 00:11:16,010 --> 00:11:21,590 If we were not tracking the tail of the singly linked list, then it would be an O of N operation. 247 00:11:21,590 --> 00:11:25,760 But because we already know the tail, we will just say tail dot. 248 00:11:25,760 --> 00:11:27,680 Next is a node and then we will make this the tail. 249 00:11:27,680 --> 00:11:32,210 So you can see this is also a constant time operation and constant space operation. 250 00:11:32,210 --> 00:11:36,710 It's constant space because we are not using any extra space or any auxiliary space. 251 00:11:37,040 --> 00:11:37,430 All right. 252 00:11:37,430 --> 00:11:43,340 Now let's proceed to the next instance method, which is to add at a particular index and the index 253 00:11:43,340 --> 00:11:44,780 and the value is given to us. 254 00:11:45,290 --> 00:11:48,500 Now again the index and the value has to be given to us. 255 00:11:48,500 --> 00:11:50,390 So we have index comma value over here. 256 00:11:50,390 --> 00:11:52,430 Now we take the value which is given to us. 257 00:11:52,430 --> 00:11:53,840 And we make a node out of it. 258 00:11:53,840 --> 00:11:54,380 All right. 259 00:11:54,380 --> 00:11:57,650 And then we will check if the index is null. 260 00:11:57,650 --> 00:11:59,180 So if the index is invalid. 261 00:11:59,180 --> 00:12:04,460 So if the index is less than zero or greater than the length then it's an invalid index. 262 00:12:04,460 --> 00:12:04,640 Right. 263 00:12:04,640 --> 00:12:06,890 So we won't be able to insert it anywhere. 264 00:12:06,890 --> 00:12:10,700 So maybe we'll just return a message saying the index is invalid. 265 00:12:10,700 --> 00:12:15,170 Now if the index is equal to the length then we will just add it at the tail. 266 00:12:15,170 --> 00:12:15,380 Right. 267 00:12:15,380 --> 00:12:18,320 So for example if this is our singly linked list. 268 00:12:19,590 --> 00:12:20,670 This is pointing to null. 269 00:12:20,670 --> 00:12:22,710 So you can see this is zero one and two. 270 00:12:22,740 --> 00:12:24,210 The length over here is three. 271 00:12:24,210 --> 00:12:29,280 So if the index is three then that means that we have just have to add the new node over here. 272 00:12:29,280 --> 00:12:29,460 Right. 273 00:12:29,460 --> 00:12:31,110 So that's this is index three. 274 00:12:31,110 --> 00:12:33,780 So you can see this is nothing but adding at the tail. 275 00:12:33,780 --> 00:12:38,910 So if the index is equal to the length of the singly linked list we will just add at the tail. 276 00:12:38,910 --> 00:12:41,160 And for this we already have the function right. 277 00:12:41,370 --> 00:12:42,990 We have the added tail function. 278 00:12:42,990 --> 00:12:45,660 So we will just call this function and pass this value. 279 00:12:45,660 --> 00:12:50,880 So we are doing this so that we can minimize the code that we have to write the number of lines of code 280 00:12:50,880 --> 00:12:51,570 that we have to write. 281 00:12:51,570 --> 00:12:53,940 And we are trying to reuse what we have already written. 282 00:12:53,970 --> 00:12:57,630 Now if the index is equal to zero, we will just add at the head. 283 00:12:57,630 --> 00:12:59,340 And again we already have a function for that. 284 00:12:59,340 --> 00:12:59,610 Right. 285 00:12:59,610 --> 00:13:04,620 So if the index is equal to zero we will just call the added head function which we have written the 286 00:13:04,620 --> 00:13:05,310 instance method. 287 00:13:05,310 --> 00:13:07,320 And we will pass this value to it. 288 00:13:07,320 --> 00:13:10,620 Now if this is not the case then let's see how we go ahead. 289 00:13:10,620 --> 00:13:17,010 Now again, only if these things are not true, then only we need to go ahead and make a note of with 290 00:13:17,010 --> 00:13:21,900 the value that we have, because otherwise we are anyway calling these functions and inside the functions. 291 00:13:21,900 --> 00:13:23,490 We are already doing this part. 292 00:13:23,520 --> 00:13:28,680 Now, if this is not the case, that is index is not invalid, index is not equal to length, and index 293 00:13:28,680 --> 00:13:29,910 is not equal to zero. 294 00:13:29,910 --> 00:13:33,750 In that case, we will go ahead and make a note with the value. 295 00:13:33,750 --> 00:13:35,550 And then it's going to point to null. 296 00:13:35,550 --> 00:13:39,540 Now then let's say this is the singly linked list which we have. 297 00:13:39,540 --> 00:13:41,820 And let's write the indices over here. 298 00:13:41,820 --> 00:13:46,290 And let's say the index which is passed to this function over here is equal to one. 299 00:13:46,290 --> 00:13:53,970 So that means that we have to insert this node over here before the node which is currently at index 300 00:13:53,970 --> 00:13:54,540 one. 301 00:13:54,540 --> 00:13:54,780 Right. 302 00:13:54,780 --> 00:13:55,800 So that is what we have to do. 303 00:13:55,800 --> 00:13:58,920 So for this first we have to identify the previous node. 304 00:13:58,920 --> 00:13:59,370 All right. 305 00:13:59,370 --> 00:14:01,350 So we'll have to identify the previous node. 306 00:14:01,350 --> 00:14:04,530 And for this we can use the get function over here. 307 00:14:04,530 --> 00:14:08,310 Now we will just pass index minus one over here as a parameter. 308 00:14:08,310 --> 00:14:10,230 And that will return the previous node. 309 00:14:10,230 --> 00:14:12,390 So first we will get the previous node. 310 00:14:12,390 --> 00:14:15,090 And then over here we have the node which we created. 311 00:14:15,090 --> 00:14:17,970 And we have to insert it over here right before this node. 312 00:14:17,970 --> 00:14:23,940 So what we will do is we will we identified the previous node and we will make this point to the node 313 00:14:23,940 --> 00:14:25,050 which we created. 314 00:14:25,050 --> 00:14:29,490 So we severe this connection and we make it point to the node which we just now created. 315 00:14:29,490 --> 00:14:33,900 And then we will make this node over here point to this node over here. 316 00:14:33,900 --> 00:14:34,140 Right. 317 00:14:34,140 --> 00:14:36,120 Which is the which which is previous dot. 318 00:14:36,120 --> 00:14:36,540 Next. 319 00:14:36,540 --> 00:14:41,220 Initially before we remove this this can be said this is previous dot next. 320 00:14:41,220 --> 00:14:42,390 So we store it somewhere. 321 00:14:42,390 --> 00:14:46,410 And then we are going to make this node over here which is the node that we created. 322 00:14:46,410 --> 00:14:47,610 Point to this node. 323 00:14:47,610 --> 00:14:50,160 So we make this connection over here and that's it. 324 00:14:50,160 --> 00:14:50,430 Right. 325 00:14:50,430 --> 00:14:53,790 So you can see we have inserted this node before this. 326 00:14:53,790 --> 00:14:56,790 And at this moment you can see if we again write the indices. 327 00:14:56,790 --> 00:14:57,540 This is zero. 328 00:14:57,570 --> 00:14:58,350 This is one. 329 00:14:58,350 --> 00:15:00,090 This is two and this is three. 330 00:15:00,090 --> 00:15:03,570 So you can see the node was inserted at index one. 331 00:15:03,570 --> 00:15:07,500 And currently at index one we have the node that we inserted. 332 00:15:07,500 --> 00:15:08,490 So that's interesting. 333 00:15:08,490 --> 00:15:08,910 All right. 334 00:15:08,910 --> 00:15:12,360 Now let's go ahead and take a look at the time and space complexity. 335 00:15:12,390 --> 00:15:18,210 Now remember in the worst case again when we talk about big O we are talking about the worst possible 336 00:15:18,210 --> 00:15:18,570 case. 337 00:15:18,570 --> 00:15:23,280 So in the worst case getting the previous node can be an O of n operation. 338 00:15:23,280 --> 00:15:23,580 Right. 339 00:15:23,580 --> 00:15:29,010 Because let's say the know the position is somewhere very close to the end of the singly linked list. 340 00:15:29,010 --> 00:15:35,940 And then we would have to traverse the singly linked list starting from the head till two till that 341 00:15:35,940 --> 00:15:36,840 index minus one. 342 00:15:36,840 --> 00:15:39,480 So this is going to be an O of n operation. 343 00:15:39,480 --> 00:15:43,560 Just think about it like let's say the singly linked list has a hundred nodes. 344 00:15:43,560 --> 00:15:46,800 And let's say we want to insert at position 90. 345 00:15:46,800 --> 00:15:48,780 So then the previous would be 89. 346 00:15:48,780 --> 00:15:52,650 So we would have to traverse all the 89 nodes to identify this. 347 00:15:52,650 --> 00:15:52,980 Right. 348 00:15:52,980 --> 00:15:57,120 So that's why this is going to be an O of n operation in the worst case. 349 00:15:57,120 --> 00:16:00,540 So we can say the time complexity is O of n worst case. 350 00:16:00,540 --> 00:16:03,780 And the space complexity is going to be O of one. 351 00:16:03,780 --> 00:16:08,700 Again, the space complexity is O of one, because we are not using any extra space or any auxiliary 352 00:16:08,700 --> 00:16:09,330 space. 353 00:16:09,330 --> 00:16:09,930 All right. 354 00:16:09,930 --> 00:16:12,150 So we are done with these for now. 355 00:16:12,150 --> 00:16:16,290 Let's take a look at the last instance method which is delete at index. 356 00:16:16,290 --> 00:16:18,630 So the index has to be passed to this function. 357 00:16:18,630 --> 00:16:19,110 All right. 358 00:16:19,110 --> 00:16:22,020 So we start by checking whether the index is valid. 359 00:16:22,020 --> 00:16:27,690 So if the index is less than zero or greater than the length then it's an invalid index. 360 00:16:27,690 --> 00:16:30,270 And again over here it should be greater than equal to right. 361 00:16:30,270 --> 00:16:33,090 Because again for example this is our linked list. 362 00:16:34,410 --> 00:16:37,830 And let's say we have zero, one and two over here. 363 00:16:37,860 --> 00:16:41,640 Now you can see that the length of this linked list is equal to three. 364 00:16:41,670 --> 00:16:45,540 Now if you want to delete the node at index three you can see there is nothing right. 365 00:16:45,720 --> 00:16:48,720 That's why this should be greater than or equal to the length. 366 00:16:48,750 --> 00:16:54,120 So if the index is greater than or equal to the length of the singly linked list, then it's an invalid 367 00:16:54,120 --> 00:16:54,450 index. 368 00:16:54,450 --> 00:16:58,710 And maybe we can just return a message that says the index is invalid. 369 00:17:00,370 --> 00:17:02,260 Then we check if the head is null. 370 00:17:02,260 --> 00:17:04,600 So if the head is null, we will just return null. 371 00:17:04,600 --> 00:17:08,860 Again, we don't need to make this check because that's going to be already considered over here. 372 00:17:08,860 --> 00:17:09,130 Right? 373 00:17:09,130 --> 00:17:15,280 So if the head is going to be null, then the size or the length of the singly linked list is going 374 00:17:15,280 --> 00:17:16,300 to be equal to zero. 375 00:17:16,300 --> 00:17:20,860 And then whatever index we pass, it's either going to be less than zero or it's going to be greater 376 00:17:20,860 --> 00:17:21,850 than equal to zero. 377 00:17:21,850 --> 00:17:22,120 Right. 378 00:17:22,120 --> 00:17:25,900 So again over here itself it's going to identify it as invalid. 379 00:17:25,900 --> 00:17:28,120 So we don't need to make a separate check for this. 380 00:17:28,120 --> 00:17:28,480 All right. 381 00:17:28,480 --> 00:17:30,340 So this is already taken care over here. 382 00:17:30,340 --> 00:17:31,480 Now let's proceed. 383 00:17:31,480 --> 00:17:32,950 Now what are the valid cases. 384 00:17:32,950 --> 00:17:37,060 So if if the index is not invalid we proceed and check the valid cases. 385 00:17:37,060 --> 00:17:42,640 So the valid cases is that maybe we want to delete the head which is index is equal to zero. 386 00:17:42,640 --> 00:17:45,310 Or the index may be length minus one. 387 00:17:45,310 --> 00:17:47,920 In which case we want to delete the tail node. 388 00:17:47,920 --> 00:17:51,640 Or it may be another index which is not the head and not the tail. 389 00:17:51,640 --> 00:17:53,890 So let's take a look at these possibilities. 390 00:17:53,890 --> 00:17:57,100 So for this let's say this is the singly linked list which we have. 391 00:17:57,100 --> 00:18:03,670 Now if we want to delete the node at index equal to zero then we are going to identify the next node. 392 00:18:03,670 --> 00:18:04,990 So this was initially the head. 393 00:18:04,990 --> 00:18:07,780 So we are identifying the next node which is this one over here. 394 00:18:07,780 --> 00:18:10,930 And then we will just make this node over here the head right. 395 00:18:10,930 --> 00:18:12,640 So this is going to be made the head. 396 00:18:12,640 --> 00:18:13,120 All right. 397 00:18:13,120 --> 00:18:13,780 So that's it. 398 00:18:13,780 --> 00:18:18,310 So that would remove this because we are going to have the linked list starting from the head. 399 00:18:18,310 --> 00:18:19,360 And this is now the head. 400 00:18:19,360 --> 00:18:22,270 So this is no longer the head that would be removing the head. 401 00:18:22,270 --> 00:18:26,050 And if you want to remove the tail then what would we have to do. 402 00:18:26,050 --> 00:18:27,820 We have to identify the previous node. 403 00:18:28,000 --> 00:18:29,470 This is the previous node right. 404 00:18:29,470 --> 00:18:30,460 This is the current tail. 405 00:18:30,460 --> 00:18:31,540 This is the previous node. 406 00:18:31,540 --> 00:18:33,790 And then we will just make this the tail. 407 00:18:33,790 --> 00:18:35,140 We'll make this the tail. 408 00:18:35,140 --> 00:18:37,690 And then we will make the tail point to null. 409 00:18:37,690 --> 00:18:39,460 So we'll make it point to null. 410 00:18:39,460 --> 00:18:42,640 And then we just have removed this which was the tail. 411 00:18:42,640 --> 00:18:47,140 So that's how we will remove the node at index is equal to length minus one. 412 00:18:47,140 --> 00:18:47,560 All right. 413 00:18:47,560 --> 00:18:52,360 And again to identify the previous node we can use the get function which we have written over here. 414 00:18:52,360 --> 00:18:55,270 So we will just use get at index minus one. 415 00:18:55,270 --> 00:19:01,450 So over here we will pass index minus one because we know the index is equal to length minus one which 416 00:19:01,450 --> 00:19:02,380 is this over here. 417 00:19:02,380 --> 00:19:07,090 So for example over here 012 and three the index is equal to three. 418 00:19:07,090 --> 00:19:10,720 So we are going to pass three minus one which is two which is this two. 419 00:19:10,720 --> 00:19:12,700 Over here to get the previous node. 420 00:19:12,700 --> 00:19:13,210 All right. 421 00:19:13,210 --> 00:19:16,180 So this is how we take care of these two scenarios. 422 00:19:16,180 --> 00:19:20,860 Now what if we want to delete another node which is not the head and not the tail. 423 00:19:20,860 --> 00:19:24,160 Again let's take a simple singly linked list which is this one over here. 424 00:19:24,730 --> 00:19:29,110 Now let's say we want to delete the node at index is equal to one. 425 00:19:29,110 --> 00:19:31,600 So that would be the second node over here right. 426 00:19:31,600 --> 00:19:32,410 So this is one. 427 00:19:32,410 --> 00:19:33,760 So we want to remove this one. 428 00:19:33,760 --> 00:19:37,000 So again what we have to do is we have to identify the previous node. 429 00:19:37,000 --> 00:19:40,780 For this we will again make use of the get function over here. 430 00:19:40,780 --> 00:19:43,060 And we will pass the index minus one. 431 00:19:43,060 --> 00:19:44,020 So index is one. 432 00:19:44,020 --> 00:19:47,740 So we'll pass index minus one which is one minus one which is equal to zero. 433 00:19:47,740 --> 00:19:50,980 So we are going to get the node at index zero which is this one over here. 434 00:19:50,980 --> 00:19:57,010 So after identifying the previous node all we need to do is we will make this point to this one over 435 00:19:57,010 --> 00:19:57,130 here. 436 00:19:57,130 --> 00:19:57,340 Right. 437 00:19:57,340 --> 00:20:02,830 So again when this is the uh, let's say the current node, we will just store this. 438 00:20:02,830 --> 00:20:04,720 So this is going to be current dot next. 439 00:20:05,480 --> 00:20:10,790 And then we'll just say previous dot next is going to be equal to current dot next. 440 00:20:10,790 --> 00:20:12,740 So we are making this connection over here. 441 00:20:12,740 --> 00:20:13,190 All right. 442 00:20:13,190 --> 00:20:17,750 And again let's take a look at the time and space complexity of this solution. 443 00:20:17,750 --> 00:20:20,090 The space again is going to be constant space. 444 00:20:20,090 --> 00:20:22,970 You can see in all of these functions it was constant space. 445 00:20:22,970 --> 00:20:25,160 We are not using any auxiliary space. 446 00:20:25,160 --> 00:20:25,550 Now. 447 00:20:25,550 --> 00:20:27,980 What about the time complexity to delete a node? 448 00:20:27,980 --> 00:20:32,570 Now when it comes to the time complexity, let's take a look at these three scenarios. 449 00:20:32,570 --> 00:20:37,550 If we are deleting at index zero then it's going to be a constant time operation, right? 450 00:20:37,550 --> 00:20:39,980 Because we already know what is there at the head. 451 00:20:39,980 --> 00:20:43,760 We just have to move once to the next one and then set this to the head. 452 00:20:43,760 --> 00:20:48,800 So even if the singly linked list has hundreds of nodes, it's still going to be the same number of 453 00:20:48,800 --> 00:20:49,430 operations. 454 00:20:49,430 --> 00:20:53,750 So we can say that the time complexity is constant if we are deleting at the head. 455 00:20:53,750 --> 00:20:59,780 Now, if we are deleting at the tail, even though we track the tail, still it's going to be an O of 456 00:20:59,780 --> 00:21:05,210 N operation because we have to do almost n operations to identify the previous node. 457 00:21:05,210 --> 00:21:05,540 Right? 458 00:21:05,540 --> 00:21:08,210 That's why this is going to be an O of N operation. 459 00:21:08,330 --> 00:21:08,780 All right. 460 00:21:08,780 --> 00:21:14,630 Now if we are trying to delete another node which is not the head and the tail, in the worst case it 461 00:21:14,630 --> 00:21:16,490 is going to be of the order of n. 462 00:21:16,490 --> 00:21:16,940 All right. 463 00:21:16,940 --> 00:21:19,730 Again that's because we have to identify the previous node. 464 00:21:19,730 --> 00:21:23,540 So for example let's say the singly linked list has 100 nodes. 465 00:21:23,540 --> 00:21:27,440 And we want to delete the node at index equal to 95. 466 00:21:27,440 --> 00:21:31,250 So we would have to identify the node at index equal to 94. 467 00:21:31,250 --> 00:21:34,520 And for that we have to do almost n operations. 468 00:21:34,520 --> 00:21:34,790 Right. 469 00:21:34,790 --> 00:21:41,570 Almost n which is in the in this specific example we have to do 94 operations which is 100 minus six. 470 00:21:41,570 --> 00:21:43,760 And in that case the n is equal to 100. 471 00:21:43,760 --> 00:21:46,160 If the singly linked list has 100 nodes. 472 00:21:46,160 --> 00:21:52,160 So we can see that in the worst case, deleting a node from another index is going to be of the order 473 00:21:52,160 --> 00:21:52,790 of n. 474 00:21:52,790 --> 00:21:53,330 All right. 475 00:21:53,330 --> 00:21:56,390 So we have seen all these instance methods. 476 00:21:56,390 --> 00:21:56,750 All right. 477 00:21:56,750 --> 00:21:59,630 Now let's take a quick look at the time complexity. 478 00:21:59,630 --> 00:21:59,840 Again. 479 00:21:59,840 --> 00:22:00,800 Let's summarize it. 480 00:22:00,800 --> 00:22:06,350 We have seen that the space complexity in all these instances is O of one which is constant. 481 00:22:06,350 --> 00:22:06,800 All right. 482 00:22:06,800 --> 00:22:12,680 Now what about the time complexity to get at an index the node at a particular index? 483 00:22:12,680 --> 00:22:14,390 It's going to be at the time. 484 00:22:14,390 --> 00:22:16,730 Complexity is going to be of the order of the index. 485 00:22:16,730 --> 00:22:17,300 All right. 486 00:22:17,300 --> 00:22:20,150 Again in the worst case it's going to be O of n. 487 00:22:20,150 --> 00:22:20,930 All right. 488 00:22:21,320 --> 00:22:26,570 And the worst case is if you want to get the last index or if you are giving an index which is greater 489 00:22:26,570 --> 00:22:27,500 than the size. 490 00:22:27,500 --> 00:22:31,670 Again, if you track the size, then we immediately know that it's not possible. 491 00:22:31,670 --> 00:22:35,630 So if you are not tracking the size, that would be an O of N operation. 492 00:22:35,630 --> 00:22:41,540 But then if we are tracking the size, then if you want to get the node at the tail or very close to 493 00:22:41,540 --> 00:22:44,090 the tail, that's going to be an O of N operation. 494 00:22:44,090 --> 00:22:44,600 All right. 495 00:22:44,630 --> 00:22:46,370 Now let's take a look at the next one. 496 00:22:46,370 --> 00:22:49,040 Over here we have added head and the value is past. 497 00:22:49,040 --> 00:22:53,120 So over here this function over here is going to be a constant time operation. 498 00:22:53,120 --> 00:22:55,520 Because we have seen we just need to add it. 499 00:22:55,940 --> 00:22:58,760 Make the next pointer of the new node point to the head. 500 00:22:58,760 --> 00:23:00,890 And then we'll make the new node the head. 501 00:23:00,890 --> 00:23:02,990 So that's going to be a constant time operation. 502 00:23:02,990 --> 00:23:04,370 Now adding at the tail. 503 00:23:04,370 --> 00:23:08,510 That is also a constant time operation because we already are tracking the tail. 504 00:23:08,510 --> 00:23:13,820 And then we will make the existing tail point to the new node which we just now which we create. 505 00:23:13,820 --> 00:23:14,060 Right. 506 00:23:14,060 --> 00:23:16,100 So that's again a constant time operation. 507 00:23:16,100 --> 00:23:17,810 Now adding at an index. 508 00:23:17,810 --> 00:23:19,400 What about adding at an index. 509 00:23:19,400 --> 00:23:23,330 That's going to be in the worst case an O of N operation. 510 00:23:23,330 --> 00:23:23,690 Right. 511 00:23:23,690 --> 00:23:26,450 If you're adding at the head that's a constant time operation. 512 00:23:26,450 --> 00:23:30,260 But if you are adding at the tail and we don't know that we are adding at the tail, right? 513 00:23:30,260 --> 00:23:35,090 For example, in this case, if we directly call added a tail function, it's a constant time operation. 514 00:23:35,090 --> 00:23:38,210 But then if we are if we have this linked list over here. 515 00:23:39,490 --> 00:23:40,120 All right. 516 00:23:40,120 --> 00:23:41,020 It's pointing to null. 517 00:23:41,020 --> 00:23:43,750 And then let's say we are passing the index as three. 518 00:23:43,750 --> 00:23:44,590 So this is zero. 519 00:23:44,590 --> 00:23:45,730 This is one this is two. 520 00:23:45,730 --> 00:23:47,620 And we are passing index as three. 521 00:23:47,620 --> 00:23:51,220 And the value is some value let's say 4 or 5 something. 522 00:23:51,220 --> 00:23:54,160 Then we don't know that we want to add at the tail. 523 00:23:54,160 --> 00:23:54,310 Right. 524 00:23:54,310 --> 00:23:56,080 So we would have to keep traversing. 525 00:23:56,080 --> 00:23:58,210 And then that takes O of n time. 526 00:23:58,210 --> 00:24:02,140 And then we have to identify the node at the previous index which is two over here. 527 00:24:02,140 --> 00:24:06,460 So that's why this is going to be an O of N operation in the worst case. 528 00:24:06,460 --> 00:24:13,120 And again even if we are trying to add at an index close to the tail, that's also going to be an operation 529 00:24:13,120 --> 00:24:18,670 of the order of N, because it may be n minus two or n minus ten, etc., depending on how far from 530 00:24:18,670 --> 00:24:24,880 the tail it is, but then it's going to be off the order of n, so this is going to be of O of N because 531 00:24:24,880 --> 00:24:26,680 we have to find the previous node. 532 00:24:26,680 --> 00:24:27,160 All right. 533 00:24:27,160 --> 00:24:30,370 So now let's go to the next one. 534 00:24:30,370 --> 00:24:32,230 So what about deleting at an index. 535 00:24:32,230 --> 00:24:36,130 If you are deleting at the head we have seen that's a constant time operation. 536 00:24:36,130 --> 00:24:36,520 All right. 537 00:24:36,550 --> 00:24:41,830 Now if you are deleting at the tail that's going to be an O of N operation because we have to find the 538 00:24:41,830 --> 00:24:42,460 previous node. 539 00:24:42,460 --> 00:24:42,670 Right. 540 00:24:42,670 --> 00:24:48,010 So even though we are tracking the tail, still deleting at the tail is going to be o of n because we 541 00:24:48,010 --> 00:24:52,990 have to go, we have to traverse the singly linked list to identify the node which is just before the 542 00:24:52,990 --> 00:24:53,470 tail. 543 00:24:53,470 --> 00:24:59,140 And if you are trying to delete another index, then in the worst case that's going to be an O of n 544 00:24:59,140 --> 00:25:00,010 operation. 545 00:25:00,430 --> 00:25:02,200 So again what's the reason for that. 546 00:25:02,200 --> 00:25:04,810 That's because we have to identify the previous node. 547 00:25:04,810 --> 00:25:06,310 So this is a summary. 548 00:25:06,310 --> 00:25:11,410 So we have successfully discussed how to implement these instance methods. 549 00:25:11,410 --> 00:25:13,780 And in our singly linked list class. 550 00:25:13,780 --> 00:25:17,710 Now in the next video let's go ahead and implement the code of this.