1
00:00:00,450 --> 00:00:03,030
‫So now we're going to look at linked lists.

2
00:00:03,060 --> 00:00:07,110
‫Big Oh, so I'm going to bring up a linked list like this.

3
00:00:07,110 --> 00:00:11,550
‫And in this video, we're going to look at all of the different things that we're going to do with a

4
00:00:11,550 --> 00:00:17,010
‫linked list and talk about with a big oh for all of those things would be.

5
00:00:17,520 --> 00:00:21,690
‫So we're going to start out by adding a node to the end of the length list.

6
00:00:21,810 --> 00:00:27,750
‫In order to do this, we'll have the last node point to the new node and have tail point to the new

7
00:00:27,750 --> 00:00:31,380
‫node, and that adds that into the length list.

8
00:00:31,680 --> 00:00:38,040
‫So for Big O in this case, N is going to be the number of nodes in the linked list.

9
00:00:38,310 --> 00:00:44,790
‫And it doesn't matter if this linked list had four items in it or if it had a million items in it.

10
00:00:44,970 --> 00:00:52,710
‫It's going to be the same number of operations to add a node to the end, which means that this is constant

11
00:00:52,710 --> 00:00:56,370
‫time and constant time is o of one.

12
00:00:56,910 --> 00:01:01,230
‫So now let's look at removing an item from the end of the length list.

13
00:01:01,380 --> 00:01:03,780
‫And this is actually much more complicated.

14
00:01:03,780 --> 00:01:09,990
‫It looks like it would be simple that you would just remove the node, move tail back to the previous

15
00:01:09,990 --> 00:01:12,270
‫node, and that would be it.

16
00:01:12,690 --> 00:01:18,630
‫But it is actually more complicated than that because in order to have this pointer point to that seven

17
00:01:18,630 --> 00:01:25,620
‫node, we have to set it equal to another pointer that is pointing at the seven node.

18
00:01:26,130 --> 00:01:31,350
‫Now there's only one pointer that is pointing at that node and that is this pointer.

19
00:01:31,740 --> 00:01:35,730
‫So we have to set tail to be equal to that pointer.

20
00:01:36,150 --> 00:01:39,120
‫So I'm going to move tail back over a space.

21
00:01:39,540 --> 00:01:46,470
‫And in order to have tail point to that seven node, we have to start at the head and then iterate through

22
00:01:46,470 --> 00:01:54,810
‫the length list until we get to this pointer here and then set tail equal to that pointer.

23
00:01:55,140 --> 00:02:01,050
‫And because we have to iterate through the entire length list that makes this O of NW.

24
00:02:01,380 --> 00:02:06,060
‫So now let's look at adding and removing an item from the other end of the length list.

25
00:02:06,060 --> 00:02:07,830
‫We'll start with adding an item.

26
00:02:08,070 --> 00:02:14,640
‫So in order to point that four node at the 11 node, we can set that pointer from the four node to be

27
00:02:14,640 --> 00:02:22,410
‫equal to head and that will point it at that 11 node and that we move head over to the new node.

28
00:02:22,410 --> 00:02:25,140
‫And that adds that end to the length list.

29
00:02:25,440 --> 00:02:30,810
‫And this will be the same number of operations regardless of the number of nodes that are already in

30
00:02:30,810 --> 00:02:34,200
‫the linked list, which means this is o of one.

31
00:02:35,820 --> 00:02:42,450
‫And to remove that item, we'll start by moving head over to the node to the right and we'll do that

32
00:02:42,450 --> 00:02:51,450
‫by setting it equal to head dot next and that moves head over and then we'll remove this node and return

33
00:02:51,480 --> 00:02:51,930
‫it.

34
00:02:52,320 --> 00:02:57,780
‫And once again, this is going to be the same number of operations regardless of the number of nodes

35
00:02:57,780 --> 00:03:01,770
‫in the linked list, which means that is o of one.

36
00:03:02,190 --> 00:03:08,010
‫So adding and removing from the beginning of the length list is o of one.

37
00:03:08,490 --> 00:03:12,390
‫So now let's look at adding a node somewhere in the middle.

38
00:03:12,420 --> 00:03:17,310
‫Let's say we're going to add this four node right after the 23 node.

39
00:03:17,850 --> 00:03:24,120
‫In order to get to that node, we have to start at the head and iterate through the length list until

40
00:03:24,120 --> 00:03:25,950
‫we get to the 23 node.

41
00:03:26,370 --> 00:03:32,970
‫So the first thing we'll do is have the four node point to the same node that the 23 is pointing to.

42
00:03:33,330 --> 00:03:40,380
‫And we'll do that by taking this pointer and setting the pointer from the four node equal to it, and

43
00:03:40,380 --> 00:03:43,380
‫now the four node is pointing to the seven node.

44
00:03:44,010 --> 00:03:49,950
‫Then we'll have the 23 node point to the four node, and that adds that into the length list.

45
00:03:50,400 --> 00:03:55,440
‫But because we had to iterate through the length list, this is O of NW.

46
00:03:56,010 --> 00:04:03,330
‫So now if we're going to remove that same node, that four node, in order to get to that node, once

47
00:04:03,330 --> 00:04:08,850
‫again, we have to start at the head and iterate through the length list to get to the node that we're

48
00:04:08,850 --> 00:04:10,560
‫going to remove.

49
00:04:11,270 --> 00:04:14,090
‫And I'm going to take this and just drop it down here.

50
00:04:14,600 --> 00:04:22,550
‫So now we'll set the pointer from the 23 node to be equal to the pointer from the fore node like this.

51
00:04:22,550 --> 00:04:29,090
‫And that'll point that 23 node over and then we can remove the four node and return it.

52
00:04:29,090 --> 00:04:34,820
‫But once again, because we had to iterate through the list, this is going to be O of NW.

53
00:04:35,510 --> 00:04:43,010
‫So another scenario to look at is what if we want to return the value of the node at the index of two?

54
00:04:43,370 --> 00:04:48,500
‫So link lists don't actually have indexes built into these nodes.

55
00:04:48,500 --> 00:04:57,290
‫In order to get to the index of two, we have to start at the head and go 012 and then we can return

56
00:04:57,290 --> 00:04:58,460
‫that value.

57
00:04:58,670 --> 00:05:03,290
‫But we do have to iterate through to get to a particular index.

58
00:05:03,710 --> 00:05:09,860
‫Likewise, if we're going to look to see if a value is in the link list, let's say instead of looking

59
00:05:09,860 --> 00:05:15,230
‫up by index, we wanted to look for the value of 23 to see if it's in there.

60
00:05:15,470 --> 00:05:23,120
‫We would have to assert the head check to see if that's a 23 and so on until we finally get to the node

61
00:05:23,120 --> 00:05:26,300
‫that contains the 23 and then we could return.

62
00:05:26,300 --> 00:05:36,470
‫True, but with a linked list it is o of n whether we are looking up by index or by value.

63
00:05:36,890 --> 00:05:43,400
‫So I'm going to remove the linked list and I'm going to bring in this table that compares a linked list

64
00:05:43,400 --> 00:05:50,450
‫to a vector, and everything in gray is going to be the same big oh for linked lists or vectors.

65
00:05:50,690 --> 00:05:57,740
‫But there are a couple of things that vectors do better, which is removing the last item and then also

66
00:05:57,740 --> 00:05:59,810
‫looking up by index.

67
00:06:00,110 --> 00:06:06,140
‫And then there are a couple of things that linked lists do better which are adding or removing from

68
00:06:06,140 --> 00:06:07,250
‫the beginning.

69
00:06:07,910 --> 00:06:14,510
‫So I get a lot of questions from students about what data structure is the best one to use for a particular

70
00:06:14,510 --> 00:06:15,530
‫situation.

71
00:06:15,860 --> 00:06:20,600
‫And the answer to that is almost always going to be based on Big O.

72
00:06:21,140 --> 00:06:27,920
‫If you're choosing between a linked list and a vector, and what you need to do is be able to add or

73
00:06:27,920 --> 00:06:33,380
‫remove from the end of the data structure or to be able to look up by index.

74
00:06:33,380 --> 00:06:40,370
‫You would want to use a vector, but what if you have a situation where you want to do a lot of adding

75
00:06:40,370 --> 00:06:41,870
‫and removing from the beginning?

76
00:06:41,870 --> 00:06:45,080
‫In that case, a linked list is going to be better.

77
00:06:45,440 --> 00:06:50,420
‫So this is why understanding the big O is so important.

78
00:06:50,990 --> 00:06:58,100
‫So you can't really understand what data structure to use and what situation unless you understand what

79
00:06:58,100 --> 00:07:01,190
‫the big O is of those data structures.

80
00:07:01,830 --> 00:07:11,430
‫So I will be attaching this table as a PDF to this video and that is our overview of length lists.

81
00:07:12,090 --> 00:07:13,170
‫Big O.