1
00:00:00,960 --> 00:00:01,740
Hi everyone.

2
00:00:01,740 --> 00:00:04,290
So we have successfully coded this solution.

3
00:00:04,290 --> 00:00:06,330
Now let's quickly walk through it.

4
00:00:06,330 --> 00:00:12,600
Now this part over here of the code was taking care of a situation where, for example, the doubly

5
00:00:12,600 --> 00:00:18,300
linked list is just one node, like for example, this one over here, and the node position and the

6
00:00:18,300 --> 00:00:21,420
node insert is both one itself, that particular node itself.

7
00:00:21,420 --> 00:00:21,720
Right.

8
00:00:21,720 --> 00:00:25,470
So if node insert is the head and the tail right.

9
00:00:25,470 --> 00:00:28,470
So if that is the case then we just need to return.

10
00:00:28,470 --> 00:00:30,180
We just don't need to do anything.

11
00:00:30,180 --> 00:00:32,910
So we just take care of this edge case over here.

12
00:00:32,910 --> 00:00:34,170
Now we proceed.

13
00:00:34,170 --> 00:00:40,140
Now first we go ahead with the case where we pass the node insert to the remove function which we've

14
00:00:40,140 --> 00:00:43,320
already written, and we take it out of the doubly linked list.

15
00:00:43,320 --> 00:00:48,750
So if it's part of the doubly linked list, this will ensure that the node is no longer part of the

16
00:00:48,750 --> 00:00:49,800
doubly linked list.

17
00:00:49,800 --> 00:00:51,720
So that's what we're doing over here.

18
00:00:51,720 --> 00:00:57,150
Now for example, if this was the doubly linked list and let's say we are passing the position node

19
00:00:57,150 --> 00:00:59,790
as node two and the node two insert as three.

20
00:00:59,790 --> 00:01:05,520
In this case, after this line over here, what will happen is we'll have the doubly linked list look

21
00:01:05,520 --> 00:01:06,090
like this.

22
00:01:06,090 --> 00:01:07,890
That is three is taken out of it.

23
00:01:07,890 --> 00:01:09,450
And then we have three over here.

24
00:01:09,960 --> 00:01:13,830
And it's pointing to null on both the sides like previous and next.

25
00:01:13,830 --> 00:01:19,440
Now again two is the position node and three is the node insert over here in this example.

26
00:01:19,440 --> 00:01:24,090
Now we proceed over here node insert dot prev and node insert dot.

27
00:01:24,090 --> 00:01:27,120
Next that is this is the uh node.

28
00:01:27,120 --> 00:01:28,890
Insert this one over here three over here.

29
00:01:28,890 --> 00:01:30,450
Now it's previous.

30
00:01:30,450 --> 00:01:31,020
And next.

31
00:01:31,020 --> 00:01:32,400
That's what we're setting over here.

32
00:01:32,400 --> 00:01:37,710
Its previous is set to node position dot prev which is this one over here.

33
00:01:37,710 --> 00:01:39,960
And its next is set to node.

34
00:01:39,960 --> 00:01:41,250
Position this one over here.

35
00:01:41,250 --> 00:01:44,040
So we are making these two connections over here.

36
00:01:44,040 --> 00:01:44,520
All right.

37
00:01:44,520 --> 00:01:45,420
So that's done.

38
00:01:45,420 --> 00:01:48,720
Then in this case we are checking if node position is the head.

39
00:01:48,720 --> 00:01:50,910
That is are we inserting before the head.

40
00:01:50,910 --> 00:01:53,730
Now in this particular example that's not the case.

41
00:01:53,730 --> 00:01:59,580
So we come to the else part and we do node position dot prev which is one dot.

42
00:01:59,580 --> 00:01:59,910
Next.

43
00:01:59,910 --> 00:02:04,860
That is this connection over here we are breaking this connection and setting it to node insert which

44
00:02:04,860 --> 00:02:05,910
is this one over here.

45
00:02:05,910 --> 00:02:10,920
Now finally we just need to remove this connection and make it point to node insert.

46
00:02:10,920 --> 00:02:12,360
This is node insert right.

47
00:02:12,360 --> 00:02:13,860
So we are doing that over here.

48
00:02:13,860 --> 00:02:17,370
We are doing node position dot prev which is this.

49
00:02:17,370 --> 00:02:18,270
This one over here.

50
00:02:18,270 --> 00:02:21,510
And dot prev this this connection over here is broken.

51
00:02:21,510 --> 00:02:25,110
And that is set to node insert which is this one over here.

52
00:02:25,110 --> 00:02:26,640
And there we have our solution.

53
00:02:26,640 --> 00:02:32,820
And in case if it's if it was the head, if we were inserting before the head, we would have set the

54
00:02:32,820 --> 00:02:35,250
node that we are inserting as the new head.

55
00:02:35,250 --> 00:02:38,910
And then we wouldn't do this part over here because there would nothing be there.

56
00:02:38,910 --> 00:02:39,300
Right.

57
00:02:39,300 --> 00:02:42,180
So this this thing over here would not be done.

58
00:02:42,180 --> 00:02:42,630
Right.

59
00:02:42,630 --> 00:02:48,600
We'll just set the new in the node that we are inserting before the existing head as the new head.

60
00:02:48,600 --> 00:02:50,580
And this is the solution that we have done.

61
00:02:50,580 --> 00:02:54,630
And as we have seen this runs in constant space and time.

62
00:02:54,630 --> 00:02:56,970
You can see we are not using any additional space.

63
00:02:56,970 --> 00:03:00,930
So constant O of one space and we are not traversing the doubly linked list.

64
00:03:00,930 --> 00:03:01,290
Right?

65
00:03:01,290 --> 00:03:04,740
The node and the position node both are given as inputs.

66
00:03:04,740 --> 00:03:07,020
We are not traversing the doubly linked list.

67
00:03:07,020 --> 00:03:09,570
That's why it's running in constant time as well.