1
00:00:00,650 --> 00:00:01,760
Welcome back.

2
00:00:01,760 --> 00:00:05,600
Let's try to think through how we can solve this problem.

3
00:00:05,600 --> 00:00:08,930
Let's say the given doubly linked list is this one over here.

4
00:00:08,930 --> 00:00:11,450
Now there are three possibilities, right?

5
00:00:11,450 --> 00:00:15,860
One possibility is that the input node which is to be removed is the head.

6
00:00:15,860 --> 00:00:17,540
So that's a possibility right.

7
00:00:17,540 --> 00:00:20,120
So we are asked to remove the head in this case.

8
00:00:20,120 --> 00:00:25,640
Now another possibility is that the input node which is to be removed is the tail which is this one

9
00:00:25,640 --> 00:00:26,120
over here.

10
00:00:26,120 --> 00:00:26,420
Right.

11
00:00:26,420 --> 00:00:27,800
So that is case two.

12
00:00:27,800 --> 00:00:34,220
And the other possibility is that we are asked to remove a node which is not the head nor the tail.

13
00:00:34,220 --> 00:00:34,460
Right.

14
00:00:34,460 --> 00:00:36,860
It could be one of these two nodes.

15
00:00:36,860 --> 00:00:38,690
Now these are the three scenarios.

16
00:00:38,690 --> 00:00:43,310
Now let's try to solve this question with the perspective of these three possibilities.

17
00:00:43,310 --> 00:00:47,600
Now if the input node is the head we are dealing with case one right.

18
00:00:47,600 --> 00:00:50,090
In this case, what is it that we have to do.

19
00:00:50,090 --> 00:00:52,820
We have to find the next node right.

20
00:00:52,820 --> 00:00:53,360
Definitely.

21
00:00:53,360 --> 00:00:54,650
We have to find the new head.

22
00:00:54,650 --> 00:00:54,920
Right.

23
00:00:54,920 --> 00:00:57,260
So we are trying to remove the existing head.

24
00:00:57,260 --> 00:01:01,010
So the new head will be the next node which is this one over here.

25
00:01:01,010 --> 00:01:03,260
And we have to set it to the head.

26
00:01:03,260 --> 00:01:03,830
Right.

27
00:01:03,830 --> 00:01:06,350
So this is something that we have to definitely do.

28
00:01:06,350 --> 00:01:10,280
Now what about the case where we are asked to remove the tail.

29
00:01:10,280 --> 00:01:10,670
Right.

30
00:01:10,670 --> 00:01:14,210
So if we have to do that that's case two which we have written over here.

31
00:01:14,210 --> 00:01:21,350
In this case we have to find the previous node to the existing tail and make that one the new tail.

32
00:01:21,350 --> 00:01:21,740
Right.

33
00:01:21,740 --> 00:01:27,140
So this deals with the case where we are trying to remove the head and we are trying to remove the tail.

34
00:01:27,140 --> 00:01:33,350
So these two things that is setting the new head or setting the new tail has to be done only in these

35
00:01:33,350 --> 00:01:34,730
two respective cases.

36
00:01:34,910 --> 00:01:36,890
Now let's look at a generic case.

37
00:01:37,400 --> 00:01:39,830
So we have four nodes over here.

38
00:01:39,830 --> 00:01:43,160
Now let's say we are trying to remove this node over here.

39
00:01:43,160 --> 00:01:44,420
Now what do we do.

40
00:01:44,450 --> 00:01:47,120
We check if there is a previous node.

41
00:01:47,600 --> 00:01:47,930
All right.

42
00:01:47,930 --> 00:01:52,370
So if there is a node over here that means if the previous node exists.

43
00:01:53,380 --> 00:02:00,190
And if it exists, then we have to make its next to point to this node over here.

44
00:02:00,190 --> 00:02:00,370
Right?

45
00:02:00,370 --> 00:02:06,430
We have to make its next point to the next node, which comes after we have removed this one because

46
00:02:06,430 --> 00:02:07,660
this node is no longer there.

47
00:02:07,660 --> 00:02:07,930
Right.

48
00:02:07,930 --> 00:02:10,450
So this one has to point to this one over here.

49
00:02:10,450 --> 00:02:14,260
Now remember we are we have to make this check over here.

50
00:02:14,260 --> 00:02:15,880
If previous is there.

51
00:02:15,880 --> 00:02:16,600
Why is that.

52
00:02:16,600 --> 00:02:18,790
So let's say we are trying to remove the head.

53
00:02:18,790 --> 00:02:20,860
Now there is no previous over here right.

54
00:02:20,860 --> 00:02:26,980
So if we don't make this check and if we just say that no dot previous dot next is this node over here,

55
00:02:26,980 --> 00:02:30,490
then we will be actually writing null dot next.

56
00:02:30,490 --> 00:02:30,910
Right.

57
00:02:30,910 --> 00:02:35,290
Because if we are trying to remove the head, the previous value over here is null.

58
00:02:35,290 --> 00:02:38,230
And then this operation would be null dot.

59
00:02:38,230 --> 00:02:38,590
Next.

60
00:02:38,590 --> 00:02:42,580
Right now this is something which will throw an error and we don't want this.

61
00:02:42,580 --> 00:02:46,030
That's why we have to check if the previous node exists.

62
00:02:46,030 --> 00:02:47,620
That is if it's not null.

63
00:02:47,620 --> 00:02:51,070
And if that is the case that means there is a node over here.

64
00:02:51,520 --> 00:02:55,060
There is a node which is previous to the node that we are trying to remove.

65
00:02:55,060 --> 00:02:59,080
Then that node has to be made to point to node dot.

66
00:02:59,080 --> 00:02:59,740
Next right.

67
00:02:59,740 --> 00:03:00,550
This is node dot.

68
00:03:00,550 --> 00:03:01,150
Next.

69
00:03:01,150 --> 00:03:02,680
Let me just write it over here.

70
00:03:02,680 --> 00:03:03,700
This will be node dot.

71
00:03:03,700 --> 00:03:08,020
Next if this is node this is node dot dot dot next right.

72
00:03:08,020 --> 00:03:10,210
And this will be node dot prev.

73
00:03:11,380 --> 00:03:11,770
Right.

74
00:03:11,770 --> 00:03:17,500
So no dot pref dot next has to be made to point to node dot next.

75
00:03:17,620 --> 00:03:18,280
And again.

76
00:03:18,280 --> 00:03:24,400
Similarly if the next node exists that is if there is a node over here then what do we need to do.

77
00:03:24,430 --> 00:03:28,270
We need to make it to point to this node over here because we are removing this.

78
00:03:28,270 --> 00:03:28,540
Right.

79
00:03:28,540 --> 00:03:33,040
So basically you have to remove this connection and make it to point to this node over here.

80
00:03:33,040 --> 00:03:37,000
Similarly when we did node dot dot next is equal to node dot.

81
00:03:37,000 --> 00:03:40,660
Next we were removing this connection and creating this connection.

82
00:03:40,660 --> 00:03:43,180
Again the same logic appears over here.

83
00:03:43,600 --> 00:03:46,270
Let's say we are trying to remove the remove the tail.

84
00:03:46,270 --> 00:03:49,000
In that case there is no node dot next right.

85
00:03:49,000 --> 00:03:53,440
So if you do node dot next dot prev is equal to node dot prev.

86
00:03:53,440 --> 00:03:57,370
In that case we would be saying null dot prev and that will throw an error.

87
00:03:57,370 --> 00:03:58,720
We want to avoid that.

88
00:03:58,720 --> 00:04:02,320
That's why we need to check if there is a next node.

89
00:04:02,320 --> 00:04:05,500
If there is a node after the node that we are trying to remove.

90
00:04:05,500 --> 00:04:10,120
In that case, we have to make that particular node's previous value.

91
00:04:10,120 --> 00:04:11,890
The previous value to the node.

92
00:04:11,890 --> 00:04:12,220
Right.

93
00:04:12,220 --> 00:04:15,010
Again I'm I'm using previous and next over here.

94
00:04:15,010 --> 00:04:17,470
It's important to visualize it so that you're very clear.

95
00:04:17,470 --> 00:04:23,320
So if there is a node which is next to the node that we're trying to remove, that means if this node

96
00:04:23,320 --> 00:04:28,030
over here is there, then the previous node to this node has to be made.

97
00:04:28,030 --> 00:04:30,970
This node over here, which is nothing but node dot prep.

98
00:04:30,970 --> 00:04:32,710
So this is what we need to check.

99
00:04:32,710 --> 00:04:33,040
Right.

100
00:04:33,040 --> 00:04:37,690
So this was step one where we checked whether we are trying to remove the head or the tail.

101
00:04:37,690 --> 00:04:41,290
And in that case we had to reset the head or the tail.

102
00:04:41,290 --> 00:04:44,770
Now in the generic case we are just checking if there is a previous node.

103
00:04:44,770 --> 00:04:49,510
If it's there, we are creating this connection, removing this connection and creating this connection

104
00:04:49,510 --> 00:04:49,990
over here.

105
00:04:49,990 --> 00:04:55,750
And if there is a next node, we are removing this connection and creating this connection over here.

106
00:04:56,110 --> 00:04:58,690
Now as you can see, we are almost done.

107
00:04:58,690 --> 00:05:00,700
Let me just make some space over here.

108
00:05:00,700 --> 00:05:02,920
There is just one more thing that's remaining.

109
00:05:02,920 --> 00:05:08,080
You can see that this node, which is the one that we are trying to remove, still points to these two

110
00:05:08,080 --> 00:05:08,860
nodes over here.

111
00:05:08,860 --> 00:05:09,220
Right?

112
00:05:09,220 --> 00:05:11,920
So we want to remove these two connections as well.

113
00:05:11,920 --> 00:05:13,930
So let me just draw that over here.

114
00:05:13,930 --> 00:05:17,500
So we have this node over here which is I'm just drawing it over here.

115
00:05:17,500 --> 00:05:20,260
Now currently it's pointing to these two nodes.

116
00:05:20,260 --> 00:05:20,560
Right.

117
00:05:20,560 --> 00:05:22,930
So we have to remove these two connections.

118
00:05:22,930 --> 00:05:25,150
And we have to make it to point to null.

119
00:05:25,150 --> 00:05:26,620
So these are the three steps.

120
00:05:26,620 --> 00:05:27,040
All right.

121
00:05:27,040 --> 00:05:28,720
So let's quickly reiterate.

122
00:05:28,720 --> 00:05:31,120
First we check whether we are trying to.

123
00:05:31,870 --> 00:05:37,480
Remove the head or the tail, and in either case we have to reset the head or the tail appropriately.

124
00:05:37,510 --> 00:05:40,270
Second, we check if there is a previous node.

125
00:05:40,270 --> 00:05:42,850
If it's there, we change the connection like this.

126
00:05:42,850 --> 00:05:46,090
And if there is a next node, we change the connection like this.

127
00:05:46,090 --> 00:05:46,480
Right?

128
00:05:46,480 --> 00:05:49,210
Again remember the important thing is to visualize this.

129
00:05:49,210 --> 00:05:53,890
If you can visualize this accurately then to code this becomes very easy.

130
00:05:53,890 --> 00:05:59,800
And finally we need to remove these connections because even after creating these two connections over

131
00:05:59,800 --> 00:06:04,540
here, still the node which is to be removed points to these two nodes, right?

132
00:06:04,540 --> 00:06:05,890
Which was the previous case.

133
00:06:05,890 --> 00:06:07,090
So we want to remove that.

134
00:06:07,090 --> 00:06:09,280
So we need to set the nodes.

135
00:06:09,280 --> 00:06:14,290
This is the node that we want to remove its previous and its next have to be set to null.

136
00:06:14,290 --> 00:06:15,100
And we are done.

137
00:06:15,100 --> 00:06:17,110
So that's the solution to this question.

138
00:06:17,110 --> 00:06:22,780
Now let's quickly look at the complexity analysis of this question of this solution which we have come

139
00:06:22,780 --> 00:06:29,470
up with time and space complexity of this solution is O of one or constant time and constant space.

140
00:06:29,470 --> 00:06:33,070
That's because we are not traversing the doubly linked list, right?

141
00:06:33,070 --> 00:06:35,500
The node is given as input to the function.

142
00:06:35,500 --> 00:06:37,930
And again we are not using any extra space.

143
00:06:37,930 --> 00:06:42,550
So the complexity of this solution is O of one time and space.