Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated:
1
1
00:00:00,076 --> 00:00:02,393
(gentle music)
2
2
00:00:02,393 --> 00:00:05,220
(keys clacking)
3
3
00:00:05,220 --> 00:00:06,053
In this video,
4
4
00:00:06,053 --> 00:00:08,750
we're going to begin our look at linked lists.
5
5
00:00:08,750 --> 00:00:11,040
A linked list is a data structure.
6
6
00:00:11,040 --> 00:00:13,420
It's a sequential list of objects,
7
7
00:00:13,420 --> 00:00:16,260
but this time, arrays aren't involved.
8
8
00:00:16,260 --> 00:00:18,930
In a linked list, each item in the list
9
9
00:00:18,930 --> 00:00:22,200
is aware of another item in the list,
10
10
00:00:22,200 --> 00:00:23,740
because each item in the list
11
11
00:00:23,740 --> 00:00:27,360
contains a link to the next item in the list.
12
12
00:00:27,360 --> 00:00:29,500
Now this is different from arrays
13
13
00:00:29,500 --> 00:00:32,320
and lists that are backed by arrays.
14
14
00:00:32,320 --> 00:00:36,100
With an array, each item in the list is completely unaware
15
15
00:00:36,100 --> 00:00:39,930
of other items in the array, but items in a linked list
16
16
00:00:39,930 --> 00:00:42,200
know which item comes after them,
17
17
00:00:42,200 --> 00:00:44,070
and that means that we have to store
18
18
00:00:44,070 --> 00:00:46,780
some extra information with each item.
19
19
00:00:46,780 --> 00:00:48,910
When we have an array of integers,
20
20
00:00:48,910 --> 00:00:52,460
we just have to store the integer value in each position,
21
21
00:00:52,460 --> 00:00:54,430
but when it comes to a linked list,
22
22
00:00:54,430 --> 00:00:56,780
we have to store the integer value
23
23
00:00:56,780 --> 00:00:58,640
and we have to store a reference
24
24
00:00:58,640 --> 00:01:01,200
to the next integer in the list.
25
25
00:01:01,200 --> 00:01:02,780
So when we get to the implementation,
26
26
00:01:02,780 --> 00:01:05,190
I'm going to use the employee class we used
27
27
00:01:05,190 --> 00:01:06,790
when we looked at array lists,
28
28
00:01:06,790 --> 00:01:10,340
and so on the screen here, I have a linked list,
29
29
00:01:10,340 --> 00:01:14,230
and this would be Jane, John, Mary, and Mike.
30
30
00:01:14,230 --> 00:01:16,740
And as we can see, this blue block
31
31
00:01:16,740 --> 00:01:18,850
would be the employee object,
32
32
00:01:18,850 --> 00:01:20,560
and then there'll be a field
33
33
00:01:20,560 --> 00:01:24,050
that contains a reference to the next item in the list.
34
34
00:01:24,050 --> 00:01:27,650
Each of these items is referred to as a node,
35
35
00:01:27,650 --> 00:01:31,470
and the first item in the list is the head of the list,
36
36
00:01:31,470 --> 00:01:34,350
and the last item in the list always points to null,
37
37
00:01:34,350 --> 00:01:36,430
because nothing comes after it.
38
38
00:01:36,430 --> 00:01:39,610
And so what we'll have is a node class
39
39
00:01:39,610 --> 00:01:41,850
that contains a field for
40
40
00:01:41,850 --> 00:01:43,640
whatever data you're holding in the node.
41
41
00:01:43,640 --> 00:01:46,110
In our case, we'll have an employee field.
42
42
00:01:46,110 --> 00:01:48,380
And then we'll have a next field,
43
43
00:01:48,380 --> 00:01:51,130
and that next field will be of type node,
44
44
00:01:51,130 --> 00:01:55,900
because each node points to the node that comes after it.
45
45
00:01:55,900 --> 00:01:57,700
Now I'm going to insert a spoiler here.
46
46
00:01:57,700 --> 00:02:00,410
In Java, you wouldn't implement a linked list yourself.
47
47
00:02:00,410 --> 00:02:03,680
There's a linked list class, but to help us understand
48
48
00:02:03,680 --> 00:02:05,950
what a linked list is and what its advantages are,
49
49
00:02:05,950 --> 00:02:08,240
we will code a simple implementation.
50
50
00:02:08,240 --> 00:02:10,650
So as I said, when it comes to a linked list,
51
51
00:02:10,650 --> 00:02:13,060
there will be a head field,
52
52
00:02:13,060 --> 00:02:16,320
and the head will point to the first item in the list.
53
53
00:02:16,320 --> 00:02:19,240
So if you have a reference to the head,
54
54
00:02:19,240 --> 00:02:21,090
you can traverse the entire list.
55
55
00:02:21,090 --> 00:02:22,530
You would start at the head
56
56
00:02:22,530 --> 00:02:24,650
and then you'd go to head.next,
57
57
00:02:24,650 --> 00:02:27,840
and then you'd go to that next field, that next one,
58
58
00:02:27,840 --> 00:02:29,200
until you hit null.
59
59
00:02:29,200 --> 00:02:32,700
So for a linked list, the only thing you have to store
60
60
00:02:32,700 --> 00:02:36,260
is a reference to the head or the first node in the list.
61
61
00:02:36,260 --> 00:02:39,950
And from that, you can get to every item in the list.
62
62
00:02:39,950 --> 00:02:41,850
So let's talk about what we'd have to do
63
63
00:02:41,850 --> 00:02:44,440
to insert an item into this list.
64
64
00:02:44,440 --> 00:02:47,160
So let's say we wanted to insert Bill.
65
65
00:02:47,160 --> 00:02:48,840
Well, the first thing we're gonna have to do
66
66
00:02:48,840 --> 00:02:51,380
is create a new node for Bill.
67
67
00:02:51,380 --> 00:02:54,750
So we'd have a box somewhere that has Bill in it.
68
68
00:02:54,750 --> 00:02:56,870
When it comes to linked lists,
69
69
00:02:56,870 --> 00:03:01,060
you always insert a new element at the front of the list.
70
70
00:03:01,060 --> 00:03:02,850
And you can understand why.
71
71
00:03:02,850 --> 00:03:06,260
We only ever store a reference to the first element,
72
72
00:03:06,260 --> 00:03:08,490
and so if we wanted to insert an item
73
73
00:03:08,490 --> 00:03:10,010
anywhere other than the front,
74
74
00:03:10,010 --> 00:03:12,550
then we'd have to traverse the list to get there.
75
75
00:03:12,550 --> 00:03:15,460
And one of the advantages of using a linked list
76
76
00:03:15,460 --> 00:03:18,820
is that if you insert items at the front of the list,
77
77
00:03:18,820 --> 00:03:21,760
you can do it in constant time complexity,
78
78
00:03:21,760 --> 00:03:23,450
because the steps you have to do
79
79
00:03:23,450 --> 00:03:26,230
don't depend on the number of items in the list.
80
80
00:03:26,230 --> 00:03:28,510
You're always gonna do the same number of steps.
81
81
00:03:28,510 --> 00:03:30,900
So we create a new node for Bill,
82
82
00:03:30,900 --> 00:03:34,620
and we're gonna wanna put Bill here, or up here in front.
83
83
00:03:34,620 --> 00:03:36,860
Bill is gonna wanna point to Jane.
84
84
00:03:36,860 --> 00:03:38,660
So after we've created the new node,
85
85
00:03:38,660 --> 00:03:41,560
we'll assign the next field Jane,
86
86
00:03:41,560 --> 00:03:44,120
and then we're gonna assign head to Bill,
87
87
00:03:44,120 --> 00:03:46,960
because Bill will be the new head of the list,
88
88
00:03:46,960 --> 00:03:49,670
and so that's all we have to do to insert a node.
89
89
00:03:49,670 --> 00:03:52,150
We create the actual node instance.
90
90
00:03:52,150 --> 00:03:55,240
We point the next field at the current head of the list
91
91
00:03:55,240 --> 00:03:57,980
because the new node is gonna become the new head,
92
92
00:03:57,980 --> 00:04:00,750
and then we point the head field at the new node.
93
93
00:04:00,750 --> 00:04:03,810
And that's gonna always be constant time complexity,
94
94
00:04:03,810 --> 00:04:04,730
because it doesn't matter.
95
95
00:04:04,730 --> 00:04:06,630
You could have three items in the list
96
96
00:04:06,630 --> 00:04:08,510
or a million items in the list,
97
97
00:04:08,510 --> 00:04:10,640
and you're just gonna do the same number of steps,
98
98
00:04:10,640 --> 00:04:13,430
as long as you're inserting at the front of the list.
99
99
00:04:13,430 --> 00:04:14,910
And so after the insertion,
100
100
00:04:14,910 --> 00:04:16,520
this is what the list would look like.
101
101
00:04:16,520 --> 00:04:18,740
Bill's next field points to Jane,
102
102
00:04:18,740 --> 00:04:21,240
and the head field now points to Bill
103
103
00:04:21,240 --> 00:04:23,000
because he's at the front of the list.
104
104
00:04:23,000 --> 00:04:24,380
So how about deleting?
105
105
00:04:24,380 --> 00:04:26,480
Now what if we wanted to pull Bill off?
106
106
00:04:26,480 --> 00:04:28,320
And once again, we'll want to delete
107
107
00:04:28,320 --> 00:04:29,420
from the front of the list.
108
108
00:04:29,420 --> 00:04:31,350
Otherwise, we're gonna have to traverse the list
109
109
00:04:31,350 --> 00:04:34,260
looking for the node we want to delete.
110
110
00:04:34,260 --> 00:04:36,270
Now in the implementation, I'll show you,
111
111
00:04:36,270 --> 00:04:39,440
when we do a deletion, we return the node that we deleted.
112
112
00:04:39,440 --> 00:04:42,310
So we're first gonna assign Bill to a temporary variable
113
113
00:04:42,310 --> 00:04:45,210
called removedNode, and then what do we wanna do?
114
114
00:04:45,210 --> 00:04:48,740
Well, all we're gonna do is move the head to Jane,
115
115
00:04:48,740 --> 00:04:51,890
because that effectively removes Bill from the list.
116
116
00:04:51,890 --> 00:04:55,210
Because for a linked list, the only sort of information
117
117
00:04:55,210 --> 00:04:57,280
that we're holding is this head field.
118
118
00:04:57,280 --> 00:05:00,450
And so if we break this link to Bill
119
119
00:05:00,450 --> 00:05:03,460
and we change heads so it's pointing to Jane,
120
120
00:05:03,460 --> 00:05:05,790
Bill has effectively been removed from the list.
121
121
00:05:05,790 --> 00:05:08,500
There's no way we can get from head to Bill.
122
122
00:05:08,500 --> 00:05:11,570
And then at that point, we would return the removedNode,
123
123
00:05:11,570 --> 00:05:14,590
which we previously stored Bill into that field.
124
124
00:05:14,590 --> 00:05:17,100
And that's all we have to do to delete a node
125
125
00:05:17,100 --> 00:05:18,100
from the front of the list.
126
126
00:05:18,100 --> 00:05:20,970
Once again, this will be constant time complexity,
127
127
00:05:20,970 --> 00:05:23,350
because it doesn't matter how many items are in the list.
128
128
00:05:23,350 --> 00:05:25,630
You're gonna do the same number of steps.
129
129
00:05:25,630 --> 00:05:28,810
So after we've deleted Bill, this is the situation.
130
130
00:05:28,810 --> 00:05:31,210
We have, Bill will be hanging off here.
131
131
00:05:31,210 --> 00:05:32,930
He'll still be pointing to Jane,
132
132
00:05:32,930 --> 00:05:35,820
but there's no way for us to reach him
133
133
00:05:35,820 --> 00:05:37,100
from the head of the list.
134
134
00:05:37,100 --> 00:05:38,640
And if we wanted to do clean out,
135
135
00:05:38,640 --> 00:05:42,400
we could set Bill's next field to null if we wanted to.
136
136
00:05:42,400 --> 00:05:46,000
And so that's it for sort of the theory for linked lists.
137
137
00:05:46,000 --> 00:05:48,470
They're not that complicated.
138
138
00:05:48,470 --> 00:05:50,570
They're the second data structure we've looked at,
139
139
00:05:50,570 --> 00:05:52,410
the first one being arrays,
140
140
00:05:52,410 --> 00:05:55,240
and they differ from arrays in that,
141
141
00:05:55,240 --> 00:05:57,080
as long as you're inserting and deleting
142
142
00:05:57,080 --> 00:05:58,320
from the front of the list,
143
143
00:05:58,320 --> 00:06:01,910
the insertions and deletions are done in constant time,
144
144
00:06:01,910 --> 00:06:04,830
and that's because there's no shifting involved.
145
145
00:06:04,830 --> 00:06:08,540
And this type of list is called a singly linked list
146
146
00:06:08,540 --> 00:06:12,730
because we have one link between every node.
147
147
00:06:12,730 --> 00:06:14,740
In a little while, we're going to look at a list
148
148
00:06:14,740 --> 00:06:16,500
that's called a doubly linked list.
149
149
00:06:16,500 --> 00:06:18,780
But we're starting out with a singly linked list,
150
150
00:06:18,780 --> 00:06:21,150
and when you're working with a singly linked list,
151
151
00:06:21,150 --> 00:06:24,620
you want to insert and delete items at the front of the list
152
152
00:06:24,620 --> 00:06:28,310
because you only have a reference to the head of the list,
153
153
00:06:28,310 --> 00:06:31,090
and so if you want to insert and delete items anywhere else,
154
154
00:06:31,090 --> 00:06:32,150
you'd have to start at head
155
155
00:06:32,150 --> 00:06:34,070
and you've got to traverse the entire list
156
156
00:06:34,070 --> 00:06:35,630
to find what you're looking for.
157
157
00:06:35,630 --> 00:06:37,350
All right, so now that we know a little bit
158
158
00:06:37,350 --> 00:06:39,400
about singly linked lists, let's implement one.
159
159
00:06:39,400 --> 00:06:40,950
I'll see you in the next video.
14135
Can't find what you're looking for?
Get subtitles in any language from opensubtitles.com, and translate them here.