1
00:00:00,800 --> 00:00:01,850
Hi everyone.

2
00:00:01,850 --> 00:00:09,020
Let's go ahead and write the next function, which is a function which asks us to insert a given node

3
00:00:09,020 --> 00:00:10,640
at a given position.

4
00:00:10,640 --> 00:00:13,970
So let's call this function insert position.

5
00:00:14,480 --> 00:00:17,360
And a position will be given to us.

6
00:00:17,360 --> 00:00:21,140
And the node which is to be inserted will be given to us.

7
00:00:21,140 --> 00:00:28,010
Now for this we will make use of the insert before or insert b function that we have already written.

8
00:00:28,010 --> 00:00:31,880
Now this function helps us to insert before any given node.

9
00:00:31,880 --> 00:00:37,880
Now the difference over here is we will be given a position right instead of a particular node.

10
00:00:37,880 --> 00:00:44,330
So what we will do is we will traverse the given doubly linked list, and we will identify the node

11
00:00:44,330 --> 00:00:45,860
at the given position.

12
00:00:45,860 --> 00:00:52,550
If that node can be identified then we will pass that node and this node over here to the function that

13
00:00:52,550 --> 00:00:58,190
we have already written, so that the given node over here will be inserted before that particular node,

14
00:00:58,190 --> 00:01:00,680
which we find out at the given position.

15
00:01:00,680 --> 00:01:01,910
So that is one thing.

16
00:01:01,910 --> 00:01:09,890
Now if the position given is greater than like for example over here the possible positions are zero,

17
00:01:09,890 --> 00:01:12,170
one, two, three and four.

18
00:01:12,170 --> 00:01:16,340
Now let's say the given node position is five or 20 or 100.

19
00:01:16,340 --> 00:01:21,830
In that case we will insert the node at the tail and we will make it the new tail.

20
00:01:21,830 --> 00:01:23,960
Now there is also an edge case.

21
00:01:23,960 --> 00:01:26,960
What if the doubly linked list is just empty.

22
00:01:26,960 --> 00:01:30,650
And we are asked to insert the node at a particular position?

23
00:01:30,650 --> 00:01:37,940
In that case, we will just make the given node as the head and the tail, and the empty doubly linked

24
00:01:37,940 --> 00:01:41,360
list will now be turned into a doubly linked list with one node.

25
00:01:41,360 --> 00:01:45,050
So that's a brief outline of what we are going to do.

26
00:01:45,050 --> 00:01:45,530
Now.

27
00:01:45,530 --> 00:01:48,980
First let's create a variable.

28
00:01:48,980 --> 00:01:52,550
Let's call it cur and let that be equal to this dot head.

29
00:01:54,260 --> 00:01:56,480
Now we will go.

30
00:01:56,480 --> 00:01:58,130
Also, we will need a counter, right?

31
00:01:58,130 --> 00:01:59,270
Let's have a counter.

32
00:01:59,270 --> 00:02:06,680
Let counter is equal to zero because we will need to identify the node at the position which is given

33
00:02:06,680 --> 00:02:07,040
to us.

34
00:02:07,040 --> 00:02:08,810
So that's why we will have a counter.

35
00:02:08,810 --> 00:02:12,590
And we will check whether the position is equal to the counter.

36
00:02:12,590 --> 00:02:19,010
And if it's not equal, we will keep incrementing cur to the next node so that when counter becomes

37
00:02:19,010 --> 00:02:23,120
equal to the position, we can identify the node at that particular position.

38
00:02:23,120 --> 00:02:25,850
So for this let's use a while loop.

39
00:02:25,850 --> 00:02:30,050
So while cur not equal to null.

40
00:02:31,630 --> 00:02:32,410
And.

41
00:02:35,030 --> 00:02:38,840
Counter not equal to position.

42
00:02:40,480 --> 00:02:41,980
Why do we have this over here?

43
00:02:42,010 --> 00:02:43,180
Car not equal to null.

44
00:02:43,180 --> 00:02:50,170
Because let's say in this case we have only 012, three, four for valid positions at which we can insert.

45
00:02:50,170 --> 00:02:52,540
Now let's say the position given is 100, right.

46
00:02:52,540 --> 00:02:55,090
So at this stage we will reach over here.

47
00:02:55,180 --> 00:02:56,740
All these will not match.

48
00:02:56,740 --> 00:03:01,030
Then when we reach over here we can identify that we have already come to null.

49
00:03:01,030 --> 00:03:02,890
So we can come out of the while loop.

50
00:03:02,890 --> 00:03:05,740
So that's why we are putting car not equal to null.

51
00:03:05,770 --> 00:03:06,370
All right.

52
00:03:06,400 --> 00:03:13,150
Now if the counter is not equal to the position, what we will do is we will make car equal to car dot

53
00:03:13,150 --> 00:03:13,840
next.

54
00:03:14,410 --> 00:03:16,150
And we will increment the counter.

55
00:03:16,150 --> 00:03:18,100
So counter plus plus.

56
00:03:18,460 --> 00:03:18,790
All right.

57
00:03:18,790 --> 00:03:22,480
So when we come out of this while loop there are two possibilities.

58
00:03:22,480 --> 00:03:26,350
One is let's say counter became equal to position right.

59
00:03:26,350 --> 00:03:29,920
So car is still not equal to null in that case.

60
00:03:29,920 --> 00:03:30,130
Right.

61
00:03:30,130 --> 00:03:32,920
If we are able to identify a valid position.

62
00:03:32,920 --> 00:03:34,660
So let's say if car.

63
00:03:35,520 --> 00:03:37,110
Not equal to null.

64
00:03:37,590 --> 00:03:40,590
So that means counter is equal to position, right?

65
00:03:40,590 --> 00:03:45,660
That means we have identified the node before which we need to insert this given node over here.

66
00:03:45,690 --> 00:03:52,680
Therefore we can just call the function which we have already written insert b and then we can pass

67
00:03:52,680 --> 00:03:54,420
cur as the position node.

68
00:03:54,420 --> 00:03:58,590
And then we pass the given node over here which is the node to be inserted.

69
00:03:58,590 --> 00:04:01,500
So this node will be inserted before cur.

70
00:04:01,500 --> 00:04:04,560
And now cur is the node at the given position.

71
00:04:04,560 --> 00:04:07,020
So yes, we will get the correct answer in this case.

72
00:04:07,020 --> 00:04:10,560
For example, let's say the given position was three.

73
00:04:10,560 --> 00:04:12,420
So 0123.

74
00:04:12,420 --> 00:04:12,960
So cur.

75
00:04:12,960 --> 00:04:19,080
At this point when counter is equal to position, cur will be over here and then we will pass four and

76
00:04:19,080 --> 00:04:22,650
the node, let's say whichever node we want to insert before four.

77
00:04:22,650 --> 00:04:24,360
And then that would be inserted over here.

78
00:04:24,360 --> 00:04:25,500
Let's say it's given five.

79
00:04:25,500 --> 00:04:27,180
So five will be inserted over here.

80
00:04:27,180 --> 00:04:28,320
And then we'll have four.

81
00:04:28,320 --> 00:04:29,700
And then that will point to null.

82
00:04:29,700 --> 00:04:34,560
And that will be taken care by the insert B function which we have already written.

83
00:04:34,770 --> 00:04:37,950
Now let's also now look at the else case.

84
00:04:37,950 --> 00:04:41,970
If this is not true, that means cur is now equal to null.

85
00:04:42,000 --> 00:04:43,650
Now there are two possibilities.

86
00:04:43,650 --> 00:04:49,590
One is that if the position given is like 100 or 20 or something else in this case, right, we have

87
00:04:49,590 --> 00:04:52,560
only four valid positions zero, one, two, three, four.

88
00:04:52,560 --> 00:04:57,420
So if the position given is five or 100 or 10, we will insert it at the tail.

89
00:04:57,420 --> 00:04:59,550
So that is one possibility.

90
00:04:59,550 --> 00:05:03,870
And the other possibility is if the doubly linked list itself is null.

91
00:05:03,870 --> 00:05:04,290
Right.

92
00:05:04,290 --> 00:05:08,040
If if if if it does not have any nodes in this case.

93
00:05:08,040 --> 00:05:13,680
Also, when we set Curry's equal to this dot head at this point itself, cur will be equal to null.

94
00:05:13,680 --> 00:05:17,610
So this will fail and this also will fail right.

95
00:05:17,610 --> 00:05:18,900
So we will come over here.

96
00:05:18,900 --> 00:05:24,810
Now we will check inside this else whether this dot head is equal to null.

97
00:05:25,770 --> 00:05:30,900
This is to see whether the doubly linked list itself is empty, or it does not have any node.

98
00:05:30,900 --> 00:05:37,380
In this case, we just have to set the head and the tail to null to the node which is given to us.

99
00:05:37,380 --> 00:05:37,920
Right.

100
00:05:37,920 --> 00:05:42,210
Because we're inserting that node into the doubly linked list.

101
00:05:43,460 --> 00:05:43,970
All right.

102
00:05:43,970 --> 00:05:46,310
Now what if.

103
00:05:48,110 --> 00:05:50,660
Let's say this is also not true.

104
00:05:50,660 --> 00:05:55,190
So head is also not null and car is equal to null.

105
00:05:55,190 --> 00:06:00,260
So that means the position at which we have to insert the given node is the tail.

106
00:06:00,260 --> 00:06:00,650
Right.

107
00:06:00,650 --> 00:06:06,020
So we just need to go ahead and write the code to insert the given node at the tail.

108
00:06:06,020 --> 00:06:10,790
So it's very much similar to the code that we have already written over here.

109
00:06:10,790 --> 00:06:12,590
So let's go ahead and discuss this.

110
00:06:12,590 --> 00:06:17,480
So the first step will be let's remove the given node from the doubly linked list.

111
00:06:17,480 --> 00:06:18,020
Right.

112
00:06:18,810 --> 00:06:19,590
Why is that so?

113
00:06:19,620 --> 00:06:21,150
Why do we need to do this?

114
00:06:21,150 --> 00:06:27,540
This is to just to ensure that in case the node which we have to insert this node over here, right.

115
00:06:27,540 --> 00:06:31,590
If it's part of the given doubly linked list, then we need to remove it out.

116
00:06:31,590 --> 00:06:34,980
We did the same thing over here also right this dot remove.

117
00:06:34,980 --> 00:06:37,170
And this was the node which we had to insert.

118
00:06:37,170 --> 00:06:42,120
So if the node is part of the doubly linked list first we remove it from where it is.

119
00:06:42,120 --> 00:06:45,840
And then we put it back to the position where we need it to be.

120
00:06:45,840 --> 00:06:48,390
In this case that position is the tail.

121
00:06:48,390 --> 00:06:48,840
All right.

122
00:06:48,840 --> 00:06:52,050
So now we have taken the node out of the doubly linked list.

123
00:06:52,050 --> 00:06:58,200
Now let's place it into the position that is the tail or the end of the doubly linked list.

124
00:06:58,200 --> 00:07:00,210
For this what do we need to do.

125
00:07:00,240 --> 00:07:01,470
We need to make that.

126
00:07:01,500 --> 00:07:03,360
We we need to make a few connections.

127
00:07:03,360 --> 00:07:03,780
Right.

128
00:07:03,780 --> 00:07:09,630
So if this node becomes the tail then its next should be equal to null right.

129
00:07:09,630 --> 00:07:11,490
Because the tail will tails.

130
00:07:11,490 --> 00:07:18,120
Next will be pointing to null and its previous node dot prev should be equal to the current tail, right?

131
00:07:18,120 --> 00:07:20,340
Because we are inserting at the tail.

132
00:07:20,340 --> 00:07:21,750
So these are two changes.

133
00:07:21,750 --> 00:07:23,610
And then the current tail.

134
00:07:23,610 --> 00:07:27,030
The current tail should point to the node.

135
00:07:27,030 --> 00:07:31,530
The tails next should point to the node because we are inserting it after the node.

136
00:07:31,530 --> 00:07:34,230
So this dot tail dot next should be equal to node.

137
00:07:34,230 --> 00:07:38,550
And finally we should change the tail and update it to the node.

138
00:07:38,550 --> 00:07:40,950
Because now this has to be made the node right.

139
00:07:40,950 --> 00:07:42,540
So this has been inserted as the tail.

140
00:07:42,540 --> 00:07:44,460
So this is the tail at this point.

141
00:07:44,460 --> 00:07:45,450
And we are done.

142
00:07:45,450 --> 00:07:49,410
We have successfully inserted the node at the given position.

143
00:07:49,410 --> 00:07:50,880
So we have written the code for that.

144
00:07:50,880 --> 00:07:53,550
Now let's go ahead and test our code.

145
00:07:54,510 --> 00:07:56,880
To test this, let's call it.

146
00:07:56,880 --> 00:08:02,610
And at at the current moment, we have linked the doubly linked list where one is pointing to two,

147
00:08:02,610 --> 00:08:03,330
pointing to three.

148
00:08:03,330 --> 00:08:05,370
That's pointing to four, that's pointing to five.

149
00:08:05,370 --> 00:08:07,200
So this is the current situation.

150
00:08:07,200 --> 00:08:09,750
Let me just quickly write the positions also.

151
00:08:09,750 --> 00:08:11,280
So this is position zero.

152
00:08:11,310 --> 00:08:12,930
This is position one.

153
00:08:12,930 --> 00:08:14,490
This is position two.

154
00:08:15,000 --> 00:08:15,240
Oops.

155
00:08:15,240 --> 00:08:16,680
And this is three.

156
00:08:16,710 --> 00:08:18,060
This is four.

157
00:08:18,060 --> 00:08:20,820
Now let's say we want to shift.

158
00:08:21,430 --> 00:08:24,070
Node four to position one, right.

159
00:08:24,070 --> 00:08:26,050
So what would that look like.

160
00:08:26,050 --> 00:08:28,240
We'll have this is position zero.

161
00:08:28,270 --> 00:08:29,770
We want it at position one.

162
00:08:29,770 --> 00:08:33,580
So over here this is position one will have node four there.

163
00:08:33,580 --> 00:08:37,330
And then we have two three and five.

164
00:08:37,330 --> 00:08:39,130
So this is the expected output.

165
00:08:39,130 --> 00:08:40,540
Let me comment this out.

166
00:08:41,730 --> 00:08:44,850
We want to move for to position one.

167
00:08:44,850 --> 00:08:47,640
So let's call it we have, uh.

168
00:08:49,060 --> 00:08:56,260
Link list doubly dot insert position, and at position one we want node four.

169
00:08:56,290 --> 00:08:58,660
Now let's run it and see what's happening.

170
00:09:01,610 --> 00:09:02,000
All right.

171
00:09:02,000 --> 00:09:04,070
Now let's look at our doubly linked list.

172
00:09:04,760 --> 00:09:06,740
And this is the expectation.

173
00:09:07,070 --> 00:09:10,070
We want it to be 14235.

174
00:09:10,070 --> 00:09:11,060
So let's try.

175
00:09:11,090 --> 00:09:12,080
Let's take a look at it.

176
00:09:12,110 --> 00:09:14,120
We have the head with value one.

177
00:09:14,150 --> 00:09:16,910
It's pointing to four which is what we expected.

178
00:09:16,910 --> 00:09:20,960
And that is pointing to two which is pointing to three.

179
00:09:20,960 --> 00:09:24,560
And that is pointing to five which is again pointing to null.

180
00:09:24,560 --> 00:09:26,180
And it's in two directions.

181
00:09:26,180 --> 00:09:28,610
There is next and previous in all of these cases.

182
00:09:28,610 --> 00:09:30,500
So yes, our code is working.

183
00:09:30,500 --> 00:09:33,890
We were able to successfully insert at position one.

184
00:09:33,890 --> 00:09:36,860
Now what if I wanted to insert at position zero.

185
00:09:36,890 --> 00:09:38,270
Let's again try that.

186
00:09:39,760 --> 00:09:42,670
And let's take a look at our doubly linked list.

187
00:09:44,150 --> 00:09:46,880
So in this case, the new head has to be for.

188
00:09:46,880 --> 00:09:47,360
Yes.

189
00:09:47,360 --> 00:09:52,760
And then that has to point to one which will point to two, that will point to three and that will point

190
00:09:52,760 --> 00:09:54,470
to five and that will point to null.

191
00:09:54,470 --> 00:09:55,970
So yes, that's also working.

192
00:09:55,970 --> 00:10:00,140
Now what if we want to insert at position let's say 20.

193
00:10:00,950 --> 00:10:01,280
All right.

194
00:10:01,280 --> 00:10:03,080
So we have 12345.

195
00:10:03,080 --> 00:10:05,630
And then we are inserting at position 20.

196
00:10:05,630 --> 00:10:07,820
So four should become the new tail right.

197
00:10:07,820 --> 00:10:10,340
So it should be 1235 and four.

198
00:10:10,340 --> 00:10:11,390
So let's run it.

199
00:10:12,020 --> 00:10:15,170
And let's take a look at our linked list.

200
00:10:15,170 --> 00:10:21,440
Doubly so over here we have one which is pointing to two which is pointing to three which is pointing

201
00:10:21,470 --> 00:10:22,280
to five.

202
00:10:22,280 --> 00:10:25,490
And four is inserted at the tail which is working.

203
00:10:25,490 --> 00:10:27,170
And that's what we wanted.

204
00:10:27,170 --> 00:10:29,480
So yes, our code is working.

205
00:10:29,480 --> 00:10:35,990
Now let's take a sample input and quickly walk through the code, because in any interview question

206
00:10:35,990 --> 00:10:36,860
you will have to do this.

207
00:10:36,860 --> 00:10:42,440
Once you have written the code, the interviewer will ask you to walk you to to walk through the code

208
00:10:42,440 --> 00:10:46,130
that you have written and explain what the variables are at each stage.

209
00:10:46,130 --> 00:10:47,720
So let's quickly do that now.