1
00:00:00,490 --> 00:00:01,420
Welcome back.

2
00:00:01,420 --> 00:00:05,200
Let's now go ahead and discuss how we can solve this question.

3
00:00:05,200 --> 00:00:06,940
Now there are two possibilities.

4
00:00:06,940 --> 00:00:13,720
The node which is given to us could be either a new node which is not part of the existing doubly linked

5
00:00:13,720 --> 00:00:19,480
list, or it can be an existing node in the doubly linked list, and in which case we have to shift

6
00:00:19,480 --> 00:00:20,290
its position.

7
00:00:20,290 --> 00:00:22,030
So these are two possibilities.

8
00:00:22,030 --> 00:00:28,660
Now these two possibilities will be handled by the existing method that we have written which is insert

9
00:00:28,660 --> 00:00:29,500
before write.

10
00:00:29,500 --> 00:00:30,970
So how was it handled.

11
00:00:30,970 --> 00:00:35,500
It was handled because if it's an existing node we're just removing it first.

12
00:00:35,500 --> 00:00:35,770
Right.

13
00:00:35,770 --> 00:00:38,890
So we are removing it for removing it from the doubly linked list.

14
00:00:38,890 --> 00:00:41,920
And then these two cases will become the same case.

15
00:00:41,920 --> 00:00:45,040
All right now let's take a sample doubly linked list.

16
00:00:45,040 --> 00:00:46,870
So we have 123 and four.

17
00:00:46,870 --> 00:00:52,090
Now this is already handled with our existing function insert before a given node.

18
00:00:52,090 --> 00:00:54,610
So we are going to make use of that same node.

19
00:00:54,610 --> 00:01:00,670
And then we are just trying to have an extra function which will make use of the previous instance method

20
00:01:00,670 --> 00:01:01,450
that we have used.

21
00:01:01,450 --> 00:01:03,910
And we will try to solve the different possibilities.

22
00:01:03,910 --> 00:01:05,440
Now what are the possibilities?

23
00:01:05,440 --> 00:01:11,080
As we have seen in the case of the test cases, one possibility is that the position may be zero or

24
00:01:11,080 --> 00:01:11,620
the head right.

25
00:01:11,620 --> 00:01:13,270
In this case the position is zero.

26
00:01:13,270 --> 00:01:18,880
Another possibility is that over here in this doubly linked list over here, the positions one, 2 or

27
00:01:18,880 --> 00:01:19,930
3 could be given.

28
00:01:19,930 --> 00:01:25,330
And another possibility is that a position is mentioned which is greater than three, something like

29
00:01:25,330 --> 00:01:25,780
100.

30
00:01:25,780 --> 00:01:31,300
And we have clarified from the interviewer that in that case we will just insert the node at the tail.

31
00:01:31,300 --> 00:01:31,810
All right.

32
00:01:31,840 --> 00:01:35,140
Now let's go ahead and explore these three possibilities.

33
00:01:35,140 --> 00:01:37,240
Let's say the node is five.

34
00:01:37,240 --> 00:01:39,130
And let's say the first case.

35
00:01:39,130 --> 00:01:43,870
Let's look at the first case where we want to insert this particular node at position zero.

36
00:01:43,870 --> 00:01:47,710
Now if we want to do this then over here we have our doubly linked list.

37
00:01:47,710 --> 00:01:52,540
All we are going to do is we are going to call our function insert B right insert before.

38
00:01:52,540 --> 00:01:55,780
So we are going to call the same function which we have previously written.

39
00:01:55,780 --> 00:02:00,040
And then we will just identify that at index zero we have node one.

40
00:02:00,040 --> 00:02:05,890
So we are going to pass node one and then node five which is the node that we want to insert at position

41
00:02:05,890 --> 00:02:06,340
zero.

42
00:02:06,340 --> 00:02:08,920
So in this way we will solve the first case.

43
00:02:08,920 --> 00:02:13,210
And we are just trying to reuse maximum of the code that we have already written.

44
00:02:13,240 --> 00:02:15,310
Now let's proceed.

45
00:02:15,310 --> 00:02:18,280
What if we want to insert at positions one, 2 or 3?

46
00:02:18,280 --> 00:02:23,050
In these cases we will just have to identify the node at that particular position.

47
00:02:23,050 --> 00:02:23,320
Right.

48
00:02:23,320 --> 00:02:25,570
So we need to find the node at position.

49
00:02:25,570 --> 00:02:29,320
For this we will use a counter and we will traverse the given doubly linked list.

50
00:02:29,320 --> 00:02:31,180
So initially the counter will be zero.

51
00:02:31,180 --> 00:02:35,020
And then we will keep moving the counter and a particular current node.

52
00:02:35,020 --> 00:02:40,480
We will keep moving the current node along with the counter till the counter is equal to position.

53
00:02:40,480 --> 00:02:43,450
So in that way we will find the node at the given position.

54
00:02:43,450 --> 00:02:46,030
And then again we will call the insert function.

55
00:02:46,030 --> 00:02:51,250
And we will pass the node at that particular position and the node which we want to insert which is

56
00:02:51,250 --> 00:02:52,210
this node over here.

57
00:02:52,210 --> 00:02:55,300
And then finally again that's the only way.

58
00:02:55,300 --> 00:02:55,450
Right.

59
00:02:55,450 --> 00:02:56,890
So there is just one way of doing that.

60
00:02:56,890 --> 00:02:58,810
We have to traverse the array for this.

61
00:02:58,810 --> 00:03:01,180
And then finally we have this third case over here.

62
00:03:01,180 --> 00:03:05,860
If you want to insert at a position which is greater than three for example 100.

63
00:03:05,860 --> 00:03:09,430
In that case we will just make the given node to be the tail.

64
00:03:09,430 --> 00:03:11,470
So for this we will keep traversing the array.

65
00:03:11,470 --> 00:03:19,210
And if we reach null if the current node becomes null before we reach a case where the counter is equal

66
00:03:19,210 --> 00:03:24,430
to the given position, then we can understand that the position which is given to us is greater than

67
00:03:24,430 --> 00:03:29,740
the last index of the doubly linked list, and in that case we will insert the node at the tail.

68
00:03:29,740 --> 00:03:31,540
So we'll have five over here.

69
00:03:31,540 --> 00:03:35,380
Now its previous and its next connections have to be made.

70
00:03:35,380 --> 00:03:35,740
All right.

71
00:03:35,740 --> 00:03:38,350
So we'll need to identify the previous node.

72
00:03:38,350 --> 00:03:44,560
So we have to connect the previous of the node which is to be inserted to the previous tail.

73
00:03:44,560 --> 00:03:47,260
And then its next has to be connected to null.

74
00:03:47,260 --> 00:03:50,770
And then this connection over here has to be severe.

75
00:03:50,770 --> 00:03:55,090
And it has to be connected to the new node that we have just now inserted.

76
00:03:55,090 --> 00:03:57,730
And then the new node has to be made the tail.

77
00:03:57,730 --> 00:03:59,680
So that is how we will solve this question.

78
00:03:59,680 --> 00:04:04,180
Now you can see that it's pretty much easy because we have already written this function.

79
00:04:04,180 --> 00:04:08,020
And we are going to make use of this function in as many cases as possible.

80
00:04:08,020 --> 00:04:11,350
Now let's take a look at the time and space complexity of this solution.

81
00:04:11,350 --> 00:04:17,380
The time complexity is going to be O of N in the worst case, where we are going to insert the particular

82
00:04:17,380 --> 00:04:21,190
node which is given to us at a position which is greater than the size.

83
00:04:21,190 --> 00:04:23,020
Now we have to identify this.

84
00:04:23,050 --> 00:04:28,330
So that's why we have to traverse the doubly linked list once to identify that yes, we have reached

85
00:04:28,330 --> 00:04:32,890
null and we have not yet reached a situation where the counter is equal to the position.

86
00:04:32,890 --> 00:04:35,320
So that means that the position is greater than the size.

87
00:04:35,320 --> 00:04:40,030
So we don't know initially, if we are not tracking the size, then we won't know initially itself that

88
00:04:40,030 --> 00:04:41,740
the position is greater than or equal to size.

89
00:04:41,740 --> 00:04:46,240
So that's why the in the worst case the time complexity is going to be O of n.

90
00:04:46,240 --> 00:04:51,460
And if we are inserting at the head, that is, if the position is zero, then we can just insert at

91
00:04:51,460 --> 00:04:52,210
constant time.

92
00:04:52,210 --> 00:04:54,670
So that's an O of one operation.

93
00:04:54,670 --> 00:04:59,080
Now the space complexity is going to be O of one because we are not using any extra space.