1
00:00:00,830 --> 00:00:03,260
Hi everyone, let's do this question.

2
00:00:03,260 --> 00:00:05,900
Create a doubly linked list class.

3
00:00:05,900 --> 00:00:09,980
Write instance methods for this class to be able to one.

4
00:00:09,980 --> 00:00:13,250
Remove a node when the node to be removed is given as input.

5
00:00:13,250 --> 00:00:13,610
All right.

6
00:00:13,610 --> 00:00:15,560
So over here we need a method.

7
00:00:15,560 --> 00:00:18,050
And the input will be a particular node.

8
00:00:18,050 --> 00:00:20,720
And this function should remove that node.

9
00:00:20,720 --> 00:00:25,130
And the second part of this question is insert a node before a particular node.

10
00:00:25,130 --> 00:00:31,310
So we should be able to insert a node before a particular node, both the node to be inserted and the

11
00:00:31,310 --> 00:00:35,090
node before which the insertion is to happen will be given as input.

12
00:00:35,090 --> 00:00:41,090
If the node to be inserted is part of the linked list, then shift its place to the desired location.

13
00:00:41,090 --> 00:00:46,340
If the node to be inserted is a new node, then insert the new node at the place desired.

14
00:00:46,340 --> 00:00:47,600
So this is the question.

15
00:00:47,600 --> 00:00:50,060
Now we will solve this in two parts.

16
00:00:50,060 --> 00:00:52,250
First, let's do the first part.

17
00:00:52,250 --> 00:00:58,220
Now when you're doing this in the interview remember feel free to ask any clarifying questions so that

18
00:00:58,220 --> 00:00:59,660
you are very clear with the question.

19
00:00:59,660 --> 00:01:04,520
Now a particular one of the particular questions that you could ask is for removal.

20
00:01:04,520 --> 00:01:07,940
What if the input node is not part of the linked list.

21
00:01:07,940 --> 00:01:13,670
So for example, you have a linked list one which points to two, and these two point to null.

22
00:01:13,670 --> 00:01:15,740
So this is a doubly linked list.

23
00:01:15,740 --> 00:01:18,740
Now let's say we are calling the remove function which we write.

24
00:01:18,740 --> 00:01:22,700
And the input is another node which is not part of the linked list.

25
00:01:22,940 --> 00:01:23,300
Right.

26
00:01:23,300 --> 00:01:25,070
So what should happen now?

27
00:01:25,070 --> 00:01:28,220
The interviewer replies then no removal happens.

28
00:01:28,220 --> 00:01:28,580
All right.

29
00:01:28,580 --> 00:01:33,350
So if the node is not part of the doubly linked list then removal does not happen.

30
00:01:33,350 --> 00:01:33,830
All right.

31
00:01:33,830 --> 00:01:36,080
So this is a pretty straightforward question.

32
00:01:36,080 --> 00:01:40,820
So let's go ahead and write a few test cases to understand the question better.

33
00:01:40,820 --> 00:01:43,040
And again we are only doing the first part.

34
00:01:43,040 --> 00:01:47,690
We will look at the logic and we will code it and walk through the code.

35
00:01:47,690 --> 00:01:50,030
And then we will come back to the second part.

36
00:01:50,030 --> 00:01:50,510
All right.

37
00:01:50,510 --> 00:01:52,580
So let's look at a few test cases.

38
00:01:52,580 --> 00:01:58,970
Again test cases are just different inputs and what the expected output is with respect to those inputs.

39
00:01:59,390 --> 00:02:02,060
Now let's say we have a doubly linked list.

40
00:02:02,060 --> 00:02:02,900
This is the one.

41
00:02:02,900 --> 00:02:07,910
So we have a node with value one pointing to this node over here which has value two.

42
00:02:07,940 --> 00:02:11,060
That's pointing to this node over here which has value three.

43
00:02:11,060 --> 00:02:14,030
And that is pointing to a node with value four.

44
00:02:14,030 --> 00:02:15,440
And again it's a doubly linked list.

45
00:02:15,440 --> 00:02:17,300
So it has two pointers.

46
00:02:17,300 --> 00:02:17,720
Right.

47
00:02:17,720 --> 00:02:21,440
And then these two the head and the tail point to null at the edges.

48
00:02:21,440 --> 00:02:22,070
All right.

49
00:02:22,070 --> 00:02:25,190
Now let's say the input is node two.

50
00:02:25,190 --> 00:02:27,260
Now what is the expected output.

51
00:02:27,260 --> 00:02:29,930
We need to be able to remove this node.

52
00:02:29,930 --> 00:02:33,650
And that means that the doubly linked list will look like this.

53
00:02:33,650 --> 00:02:34,610
Now right.

54
00:02:34,610 --> 00:02:35,570
We will have one.

55
00:02:35,570 --> 00:02:36,500
Then we'll have three.

56
00:02:36,500 --> 00:02:37,220
Then we'll have four.

57
00:02:37,220 --> 00:02:38,690
So we have removed this one right.

58
00:02:38,690 --> 00:02:40,640
So this is what we need to achieve.

59
00:02:40,640 --> 00:02:42,320
So it's a pretty straightforward case.

60
00:02:42,320 --> 00:02:43,910
And again we saw the edge case.

61
00:02:43,910 --> 00:02:46,280
Let's say this is the doubly linked list.

62
00:02:46,280 --> 00:02:49,100
And the input is another node which is five.

63
00:02:49,100 --> 00:02:52,190
And let's say it's just pointing to null and null.

64
00:02:52,190 --> 00:02:54,440
So it's not part of the doubly linked list.

65
00:02:54,440 --> 00:02:56,120
So in this case nothing happens.

66
00:02:56,120 --> 00:02:56,360
Right.

67
00:02:56,360 --> 00:02:57,770
So that's the question.

68
00:02:57,770 --> 00:03:03,710
Now let's go ahead in the next video and discuss an approach with which we can solve this question.