1
00:00:06,930 --> 00:00:10,770
Another way to store data is by using a linked list.

2
00:00:11,100 --> 00:00:13,320
There are a couple of different linked lists.

3
00:00:13,320 --> 00:00:17,470
We can have a singly linked list and a doubly linked list.

4
00:00:17,520 --> 00:00:23,340
But in this lecture and in this section, we are going to talk about a singly linked list.

5
00:00:23,490 --> 00:00:30,990
Now, unlike an array which requires a fixed size, we can use a singly linked list which can easily

6
00:00:30,990 --> 00:00:36,420
expand the concept around a singly linked list is pretty simple.

7
00:00:36,420 --> 00:00:42,450
But with Russ's ownership and memory system, sometimes it can be a bit more complicated to create a

8
00:00:42,450 --> 00:00:45,000
linked list in Russ than in other languages.

9
00:00:46,110 --> 00:00:52,830
So let's take a minute to try and understand what a linked list is.

10
00:00:53,190 --> 00:01:00,870
So we'll say we have a node and we'll say it is Node one and we'll just give it a circle.

11
00:01:00,870 --> 00:01:03,810
That way we know it's a node and we'll label it as a node.

12
00:01:04,980 --> 00:01:13,170
So inside of a node, we're going to have two pieces of data at least so we can represent this as a

13
00:01:13,170 --> 00:01:18,300
struct and we will say the name of the struct is Node.

14
00:01:19,650 --> 00:01:22,800
And then inside of here we're going to have our piece of data.

15
00:01:23,460 --> 00:01:25,950
So in this case, our data is going to be one.

16
00:01:26,430 --> 00:01:31,920
And then we're also going to have something that is called next.

17
00:01:33,330 --> 00:01:38,550
So what next is is next is going to store the information.

18
00:01:38,550 --> 00:01:41,770
So the memory address to another node.

19
00:01:41,790 --> 00:01:44,370
So we'll say we have Node two.

20
00:01:46,990 --> 00:01:52,510
And we'll say Node one's memory address.

21
00:01:55,700 --> 00:01:58,640
Memory adder is 100 to keep it simple.

22
00:01:59,840 --> 00:02:06,830
This link right here is represented by the next value and our node struct.

23
00:02:07,070 --> 00:02:09,830
And then we will say our memory address.

24
00:02:12,610 --> 00:02:15,790
For Node two is 200.

25
00:02:16,180 --> 00:02:21,730
So next is going to point to this memory address of 200.

26
00:02:22,540 --> 00:02:28,930
And we know at that memory address is going to be this node that stores the value, too.

27
00:02:29,560 --> 00:02:32,020
So now we can point this node.

28
00:02:32,650 --> 00:02:37,000
It's next value to Node three.

29
00:02:39,680 --> 00:02:45,110
And then we can point this node's value to another node for.

30
00:02:48,830 --> 00:02:53,420
And then we have one more piece that we can point for, too.

31
00:02:53,450 --> 00:02:55,100
So let's just go ahead and fill this out.

32
00:02:55,100 --> 00:03:01,700
So we'll say this is our next link and we'll say this is memory address 300 and this is memory address

33
00:03:01,700 --> 00:03:02,690
400.

34
00:03:03,110 --> 00:03:14,390
So currently what we have for Node one, if we looked inside of it, struck its data is equal to one.

35
00:03:14,990 --> 00:03:17,720
Next is equal to.

36
00:03:18,480 --> 00:03:28,710
200, which this points to Node two whose data is equal to two next.

37
00:03:30,510 --> 00:03:33,420
Next equals 300.

38
00:03:33,930 --> 00:03:39,870
And this is Node three, whose data is equal to three.

39
00:03:40,020 --> 00:03:47,880
Next equals 400, who now we point to Node four.

40
00:03:50,710 --> 00:03:54,340
Who's data equals four.

41
00:03:54,790 --> 00:03:56,010
And who's next?

42
00:03:56,020 --> 00:03:57,070
Equals.

43
00:03:58,490 --> 00:04:06,340
So if Node four isn't pointing to another node, which it's currently not, what would its next be?

44
00:04:07,000 --> 00:04:15,460
Well, in other languages you would typically point this to something like NULL to denote that, hey,

45
00:04:15,460 --> 00:04:19,080
this is the head of the list.

46
00:04:19,090 --> 00:04:27,910
So in rust we don't have null, but what we can do is we can point it to none because we can create

47
00:04:27,910 --> 00:04:32,200
an option inside and it can either be some or none.

48
00:04:32,200 --> 00:04:36,160
So we can have it denote it as none.

49
00:04:36,880 --> 00:04:41,200
But now you heard me say that Node four is the head.

50
00:04:41,590 --> 00:04:48,790
So we want to know where the head is in the link list because this is going to be the top of the linked

51
00:04:48,790 --> 00:04:59,610
list, which is going to be important for us when we want to add elements or or remove elements.

52
00:04:59,620 --> 00:05:09,520
So Node four is also going to have another struc or excuse me, there's going to be another struct.

53
00:05:12,060 --> 00:05:17,670
And what we're going to have in this struct and we'll just call this link is going to be the head,

54
00:05:18,720 --> 00:05:21,390
which then will point to.

55
00:05:24,660 --> 00:05:25,500
A link.

56
00:05:26,920 --> 00:05:31,630
And we'll see this and this will be much clearer when we look at the code.

57
00:05:32,890 --> 00:05:39,910
But what this head is going to do is it's going to point to the top element in our leaked list.

58
00:05:40,390 --> 00:05:46,450
So now that we have a general idea of how linked lists works, let's begin setting up our own linked

59
00:05:46,450 --> 00:05:46,970
list.

60
00:05:46,990 --> 00:05:55,600
That way we can begin to see how the code starts to form, and we begin doing that in the next lecture.