1
00:00:00,400 --> 00:00:05,320
‫So now we're going to get into our first data structure, which is linked lists.

2
00:00:05,830 --> 00:00:13,480
‫So the data structure that a linked list is most commonly compared to would be an array or a vector.

3
00:00:14,050 --> 00:00:20,590
‫A vector is actually a better comparison because both vectors and linked lists are dynamic and length

4
00:00:20,590 --> 00:00:22,930
‫and an array is fixed in length.

5
00:00:23,590 --> 00:00:29,980
‫So I'm going to start out by making changes to this and turn it into a linked list.

6
00:00:30,490 --> 00:00:37,120
‫So the first thing is that a vector has these indexes where you can go directly to an index, and that's

7
00:00:37,120 --> 00:00:39,670
‫something that a linked list is not going to have.

8
00:00:39,670 --> 00:00:41,440
‫So I'm going to remove those.

9
00:00:41,920 --> 00:00:48,430
‫Another thing that is different with a linked list is that these items are spread in different places

10
00:00:48,430 --> 00:00:52,180
‫in memory instead of being in a contiguous location.

11
00:00:52,570 --> 00:00:58,990
‫So one of the things I also like to do when we move to a new data structure is represented visually

12
00:00:58,990 --> 00:01:03,730
‫in a different way, and it makes it easier to differentiate one from another.

13
00:01:04,060 --> 00:01:09,670
‫So I represented vectors and arrays as green squares.

14
00:01:10,030 --> 00:01:15,160
‫I'm going to represent the nodes in a linked list as purple circles.

15
00:01:15,700 --> 00:01:20,860
‫So another thing that a linked list is going to have is a variable that points to the first node called

16
00:01:20,860 --> 00:01:21,520
‫head.

17
00:01:22,000 --> 00:01:28,240
‫We'll have another variable that points to the last node called tail, and then each node will point

18
00:01:28,240 --> 00:01:31,630
‫to the next, to the next to the next.

19
00:01:32,080 --> 00:01:37,780
‫And then the last node, it's pointer is going to point to the null pointer, which means it doesn't

20
00:01:37,780 --> 00:01:39,370
‫point to anything.

21
00:01:39,730 --> 00:01:44,970
‫So I'm going to bring in something that represents a memory space like this with a linked list.

22
00:01:44,980 --> 00:01:47,290
‫This is going to be all over memory.

23
00:01:47,500 --> 00:01:56,380
‫These just have to point one to the next versus with an array or a vector where all of these are going

24
00:01:56,380 --> 00:01:59,050
‫to be in a contiguous place in memory.

25
00:01:59,620 --> 00:02:06,730
‫And that is why we can have these indexes with a vector or an array where we can go directly to one

26
00:02:06,730 --> 00:02:09,820
‫of these indexes as an o of one operation.

27
00:02:09,820 --> 00:02:14,440
‫It is because these are all and a contiguous place in memory.

28
00:02:14,980 --> 00:02:20,140
‫And that is our quick overview of comparing linked lists.

29
00:02:20,940 --> 00:02:21,960
‫Two vectors.