1
00:00:00,410 --> 00:00:06,110
‫So now we're going to create our get function and we'll start our get function out like this.

2
00:00:06,110 --> 00:00:09,110
‫We're looking for a node at an index.

3
00:00:09,470 --> 00:00:14,840
‫So I'm going to start this out with a singly linked list and then we'll talk about the differences in

4
00:00:14,840 --> 00:00:18,440
‫the get function when we do a doubly linked list.

5
00:00:18,770 --> 00:00:25,640
‫If you remember in our get function for a singly linked list, we could get the node at the index of

6
00:00:25,640 --> 00:00:31,580
‫zero or one or two or three, but we can't have anything out of range.

7
00:00:31,580 --> 00:00:37,250
‫So less than zero or greater than or equal to the length.

8
00:00:37,790 --> 00:00:43,790
‫So we'll start out with this same if statement, if it's out of range, will return null pointer.

9
00:00:44,390 --> 00:00:46,940
‫So let's bring this back up.

10
00:00:47,090 --> 00:00:52,160
‫We need to have a variable, we'll call it temp that we set equal to head.

11
00:00:52,820 --> 00:01:00,260
‫We'll create this like this temp equals head and I'm going to remove head and tail that we had a for

12
00:01:00,260 --> 00:01:05,630
‫loop that would iterate through the linked list and we would say temp equals temp next.

13
00:01:05,780 --> 00:01:11,960
‫And if we were looking for something at the index of two, this would loop one two times and then we

14
00:01:11,960 --> 00:01:14,090
‫would return temp.

15
00:01:14,750 --> 00:01:17,690
‫And this was the entire function.

16
00:01:17,690 --> 00:01:27,200
‫Forget for a singly linked list and this function will work as it is written for a doubly linked list.

17
00:01:27,530 --> 00:01:34,430
‫However, there's an optimization that we're going to write where it runs more efficiently for a doubly

18
00:01:34,430 --> 00:01:35,450
‫linked list.

19
00:01:36,020 --> 00:01:41,450
‫So I'm going to bring this linked list back, and then we're going to change it into a doubly linked

20
00:01:41,450 --> 00:01:42,080
‫list.

21
00:01:42,930 --> 00:01:46,980
‫Let's say we want to get the node at the index of one.

22
00:01:47,250 --> 00:01:53,010
‫The most efficient way to get there would be to start at the head and iterate through until we got to

23
00:01:53,010 --> 00:01:56,130
‫this node and then we would return it.

24
00:01:56,340 --> 00:02:00,030
‫But what if we wanted this node at the index of two?

25
00:02:00,360 --> 00:02:05,010
‫The most efficient way to get to this node is not to start at the head.

26
00:02:05,040 --> 00:02:10,950
‫The most efficient way to do this is to start at the tail and go the other way.

27
00:02:11,220 --> 00:02:13,460
‫So we want to start at the head.

28
00:02:13,470 --> 00:02:19,380
‫If the node is in the first half of the linked list and we want to start at the tail if it's in the

29
00:02:19,380 --> 00:02:21,600
‫second half of the linked list.

30
00:02:22,320 --> 00:02:24,660
‫So now let's bring this code back.

31
00:02:25,150 --> 00:02:32,200
‫So with this for loop, we only want to run this if the node we're looking for is in the first half

32
00:02:32,200 --> 00:02:33,490
‫of the length list.

33
00:02:33,880 --> 00:02:40,330
‫So we're going to wrap this in an if statement and say if the index is less than the length divided

34
00:02:40,330 --> 00:02:44,380
‫by two, only then do we run this for loop.

35
00:02:44,710 --> 00:02:51,100
‫Otherwise we know it's in the second half and we'll say else, and the first thing we'll do here is

36
00:02:51,100 --> 00:02:53,560
‫set temp to be equal to tail.

37
00:02:53,560 --> 00:02:55,810
‫So let's bring this up.

38
00:02:55,810 --> 00:03:00,340
‫That's just taking temp and moving it to the other end of the length list.

39
00:03:00,700 --> 00:03:04,030
‫And then we'll also create a for loop for this.

40
00:03:04,300 --> 00:03:10,690
‫But I is equal to the length minus one, which in this case is this index here.

41
00:03:10,990 --> 00:03:17,680
‫And then each time we go through the for loop, we are decrement the index and then inside of the for

42
00:03:17,680 --> 00:03:21,040
‫loop we're saying temp equals temp previous.

43
00:03:21,250 --> 00:03:26,590
‫So if we're looking for the item at the index of two, that's going to move temp to here.

44
00:03:27,570 --> 00:03:30,330
‫And then we return temp.

45
00:03:30,990 --> 00:03:38,930
‫So let's add this in with the rest of our code and this is our get function for a doubly linked list.

46
00:03:38,940 --> 00:03:45,780
‫We have this if statement up here for when we have an item in the first half of the doubly linked list

47
00:03:46,050 --> 00:03:50,850
‫and this else statement down here for when it's in the second half.

48
00:03:51,180 --> 00:03:54,210
‫So we'll look at this code and a moment in VZ code.

49
00:03:54,210 --> 00:04:01,830
‫And when we do, we'll create this doubly linked list with four items in it where the value is the same

50
00:04:01,830 --> 00:04:05,070
‫as the index for all four nodes.

51
00:04:05,310 --> 00:04:11,130
‫And then we'll run get at the index of one because we want to make sure that it will return a node in

52
00:04:11,130 --> 00:04:17,370
‫the first half and then we'll run it on the index of two to make sure that it works if a node is in

53
00:04:17,370 --> 00:04:20,160
‫the second half of our linked list.

54
00:04:20,460 --> 00:04:24,270
‫So now let's flip over to VS Code and take a look at this.

55
00:04:25,300 --> 00:04:32,320
‫So there is our get member function there and I'll scroll up and in our main function we're creating

56
00:04:32,320 --> 00:04:36,760
‫this doubly linked list with values of zero through three.

57
00:04:36,760 --> 00:04:42,760
‫And then with this line we will print that out and I'll run this and you can see that we have a doubly

58
00:04:42,760 --> 00:04:46,900
‫linked list with a values of zero, one, two and three.

59
00:04:47,470 --> 00:04:52,900
‫So now I'm going to come up here and replace this line that says Print List.

60
00:04:53,480 --> 00:05:01,670
‫With these two lines and we're running get at the index of one and get at the index of two and remember,

61
00:05:01,670 --> 00:05:03,410
‫get returns the node.

62
00:05:03,410 --> 00:05:09,080
‫So I've added value here because I just want to see the values from those nodes.

63
00:05:09,560 --> 00:05:17,240
‫So I'll run this and this is return the node with the value of one and the node with the value of two.

64
00:05:17,720 --> 00:05:19,970
‫And that is our function.

65
00:05:20,210 --> 00:05:21,320
‫Forget.