1
00:00:01,090 --> 00:00:02,200
Hi everyone.

2
00:00:02,200 --> 00:00:05,620
Let's think in this video how we can solve this question.

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

4
00:00:08,800 --> 00:00:11,860
And let's say the value given to us is equal to two.

5
00:00:11,890 --> 00:00:17,710
So we need to remove all the nodes from this doubly linked list which have a value equal to two.

6
00:00:17,740 --> 00:00:21,220
So what we will do is we will traverse the doubly linked list.

7
00:00:21,220 --> 00:00:26,980
And for every node where the value is equal to two, we will call the remove function which we have

8
00:00:26,980 --> 00:00:28,360
already written previously.

9
00:00:28,360 --> 00:00:30,220
And we will just remove that node.

10
00:00:30,220 --> 00:00:35,740
So let's look at how to traverse this doubly linked list in a smart manner, so that we don't lose the

11
00:00:35,740 --> 00:00:38,410
connection when we remove a particular node.

12
00:00:38,410 --> 00:00:39,820
Now we start with the head.

13
00:00:39,820 --> 00:00:40,810
So this is the head.

14
00:00:40,810 --> 00:00:44,230
Let's have a variable ker and let it point to the head.

15
00:00:44,230 --> 00:00:44,800
All right.

16
00:00:44,800 --> 00:00:49,510
Now let's create another variable temp and let it also point to ker.

17
00:00:49,540 --> 00:00:50,140
All right.

18
00:00:50,140 --> 00:00:52,300
Now let's move ker.

19
00:00:52,330 --> 00:00:53,710
Let's move it ahead.

20
00:00:53,710 --> 00:00:57,400
So ker moves ahead and temp is now over here.

21
00:00:57,400 --> 00:01:03,130
Now we we check whether temp the value in temp is equal to the given value.

22
00:01:03,130 --> 00:01:03,550
All right.

23
00:01:03,550 --> 00:01:04,930
Now why do we do this.

24
00:01:04,930 --> 00:01:06,670
Why do we have this mechanism.

25
00:01:06,670 --> 00:01:10,180
This is done so that we don't lose the next value right.

26
00:01:10,180 --> 00:01:15,490
For example if we did not have this temp value and let's say just ker was over here and we are checking

27
00:01:15,490 --> 00:01:18,760
whether the current value is equal to the value given.

28
00:01:18,760 --> 00:01:21,340
And if it's given, let's say we are passing that node.

29
00:01:21,340 --> 00:01:25,540
In that case, let's say over here we have the value equal.

30
00:01:25,540 --> 00:01:27,520
And let's say we did not have a temp variable.

31
00:01:27,520 --> 00:01:28,720
Let's say this was not there.

32
00:01:28,720 --> 00:01:31,480
So we are just having this ker pointer.

33
00:01:31,480 --> 00:01:35,170
And we see that its value is the same as the given value.

34
00:01:35,170 --> 00:01:38,020
And we pass this node and we remove this node.

35
00:01:38,020 --> 00:01:43,030
If we do that then we will not be able to traverse the remaining part of the doubly linked list.

36
00:01:43,030 --> 00:01:45,130
So that's why we need to avoid this.

37
00:01:45,130 --> 00:01:48,280
And hence we are using another variable also.

38
00:01:48,280 --> 00:01:48,700
All right.

39
00:01:48,700 --> 00:01:50,800
So that we don't lose the next value.

40
00:01:50,800 --> 00:01:55,660
Now once we have this arrangement we check the value in temp which is equal to one.

41
00:01:55,660 --> 00:01:59,800
And we see that that value is not equal to the value which is given to us.

42
00:01:59,800 --> 00:02:00,280
All right.

43
00:02:00,280 --> 00:02:02,140
So we don't need to remove this node.

44
00:02:02,140 --> 00:02:05,800
Now what we do is we move ker and temp ahead.

45
00:02:05,800 --> 00:02:07,060
So how do we do that.

46
00:02:07,060 --> 00:02:10,420
We we we already have ker as the next value.

47
00:02:10,420 --> 00:02:11,560
Now in the loop.

48
00:02:11,560 --> 00:02:14,200
In the next loop again we set temp to ker.

49
00:02:14,830 --> 00:02:17,050
And then we set ker to car dot next.

50
00:02:17,050 --> 00:02:18,940
So we move these two ahead.

51
00:02:18,940 --> 00:02:20,950
So that's what happens basically.

52
00:02:20,950 --> 00:02:25,270
And then we check the value of temp whether it's equal to the given value.

53
00:02:25,270 --> 00:02:26,590
And we see it's equal.

54
00:02:26,590 --> 00:02:28,150
So we pass temp.

55
00:02:28,150 --> 00:02:30,790
We pass this node to the remove function.

56
00:02:30,790 --> 00:02:32,440
So we do remove temp.

57
00:02:32,440 --> 00:02:36,160
And that removes this node from the doubly linked list.

58
00:02:36,160 --> 00:02:36,640
All right.

59
00:02:36,640 --> 00:02:41,200
Now what we do we again move these two and we repeat this process.

60
00:02:41,200 --> 00:02:44,500
We again check whether temp dot val is equal to the given value.

61
00:02:44,500 --> 00:02:45,550
Yes that's true.

62
00:02:45,550 --> 00:02:48,400
So we remove this node and this is removed.

63
00:02:48,400 --> 00:02:50,080
Again we move this forward.

64
00:02:50,080 --> 00:02:50,590
All right.

65
00:02:50,590 --> 00:02:52,930
We again check whether the value is equal.

66
00:02:52,930 --> 00:02:54,610
But over here it's not equal.

67
00:02:54,610 --> 00:02:55,510
It's three over here.

68
00:02:55,510 --> 00:02:56,860
And this is equal to two.

69
00:02:56,890 --> 00:02:58,810
So we don't remove this node.

70
00:02:58,810 --> 00:03:01,810
Again we move this forward and we check this value.

71
00:03:01,810 --> 00:03:03,640
And this value they are equal.

72
00:03:03,640 --> 00:03:05,860
So we remove this node as well.

73
00:03:05,860 --> 00:03:09,910
And again we move this forward and we check and the value is equal.

74
00:03:09,910 --> 00:03:12,400
So we remove this node as well.

75
00:03:12,400 --> 00:03:12,940
All right.

76
00:03:12,940 --> 00:03:16,000
And then finally we see that ker is equal to null.

77
00:03:16,000 --> 00:03:19,780
So we will be looping as long as ker is truthy.

78
00:03:19,810 --> 00:03:22,300
Now when ker is equal to null it will be false.

79
00:03:22,420 --> 00:03:24,130
And we will come out of the loop.

80
00:03:24,130 --> 00:03:24,520
Right.

81
00:03:24,520 --> 00:03:27,490
And we will just be left with this part of the.

82
00:03:27,520 --> 00:03:29,320
This is the new doubly linked list.

83
00:03:29,320 --> 00:03:32,350
All the nodes with value two have been removed from it.

84
00:03:32,350 --> 00:03:34,540
Now this is pretty straightforward.

85
00:03:34,540 --> 00:03:39,580
The only thing that you need to keep in mind is when you remove, you should not lose the next value.

86
00:03:39,580 --> 00:03:43,360
And that's why we were using a temp variable as well as the current variable.

87
00:03:43,360 --> 00:03:43,930
All right.

88
00:03:43,930 --> 00:03:49,000
Now let's quickly look at the time complexity and the space complexity of this solution.

89
00:03:49,000 --> 00:03:53,320
Now over here you can see that we have to traverse the doubly linked list once right.

90
00:03:53,320 --> 00:04:00,040
Therefore clearly the time complexity is O of n where n is the length of the doubly linked list because

91
00:04:00,040 --> 00:04:01,690
we have to traverse it once, right?

92
00:04:01,690 --> 00:04:06,610
We have to see every node once and check whether the value is equal to the given value.

93
00:04:06,670 --> 00:04:09,190
And what about the space complexity?

94
00:04:09,190 --> 00:04:12,040
We are not using any additional space, right?

95
00:04:12,040 --> 00:04:16,330
So the space complexity is O of one or constant space.