Preview
Video Player
00:00
00:00
What Is a Linked List?
13:18Despite having powerful collection types built in to most languages we often have a need for custom data structures that store data in different ways. In this video let's take a look at what a linked list is
[MUSIC]
0:00
[SOUND] Over the next few videos, we're
going to build a data structure that you
0:04
may have worked with before,
a linked list.
0:09
Before we get into what a linked list is,
let's talk about why we build data
0:11
structures instead of just using the ones
that come built in to our languages.
0:15
Each data structure solves
a particular problem.
0:19
We just went over the basics
of the array data structure.
0:23
And looked at the cost of common
operations that we carry out on arrays.
0:26
We found that arrays were
particularly good at accessing,
0:30
reading values happens in constant time.
0:33
But arrays are pretty bad at inserting and
deleting,
0:36
both of which run in linear time.
0:39
Linked lists, on the hand,
are somewhat better at this,
0:41
although there are some caveats.
0:44
And if we're trying to solve a problem
that involves far more inserts and
0:46
deletes than accessing, a linked list
can be a better tool than an array.
0:50
So what is a linked list?
0:55
A linked list is a linear data structure
where each element in the list is
0:56
contained in a separate
object called a node.
1:01
A node models two pieces of information,
an individual
1:05
item of the data that we want to store and
a reference to the next node in the list.
1:08
The first node in the linked list
is called the head of the list,
1:13
while the last node is called the tail.
1:17
The head and the tail nodes are special.
1:20
The list only maintains a reference to the
head, although in some implementations,
1:22
it keeps a reference to the tail as well.
1:26
This aspect of linked
lists is very important.
1:29
And as you'll see, most of the operations
on the list need to be implemented
1:32
quite differently compared to an array.
1:36
The opposite of the head, the tail,
denotes the end of the list.
1:38
Every node other than the tail points
to the next node in the list, but
1:42
tail doesn't point to anything.
1:47
This is basically how we know
it's the end of the list.
1:49
Nodes are what are called
self referential objects.
1:52
The definition of a node
includes a link to another node.
1:56
And self referential here
means the definition of node
2:00
includes the node itself.
2:03
Linked lists often come in two forms.
2:05
A singly linked list,
2:07
where each node stores a reference
to the next node in the list.
2:08
Or a doubly linked list,
2:12
where each node stores a reference
to both the node before and after.
2:13
If an array is a train with
a bunch of cars in order,
2:18
then a linked list is
like a treasure hunt.
2:21
When you start the hunt,
2:25
you have a piece of paper with
a location of the first treasure.
2:26
You go to that location and
you find an item,
2:29
along with a location to
the next item of treasure.
2:32
When you finally find an item that
doesn't also include a location,
2:35
you know that the hunt has ended.
2:39
Now that we have a high level view of what
a linked list is, let's jump into code and
2:41
build one together.
2:46
We'll focus on building a singly
linked list for this course.
2:47
There are advantages to having
a doubly linked list, but
2:51
we don't want to get ahead of ourselves.
2:54
Let's start here by creating a new file
where we're going to put all our code for
2:57
our linked list, so
we'll call this linked_list.py.
3:04
And first, we're going to create
a class to represent a node.
3:10
Say, class Node.
3:15
Now, Node is a simple object,
in that it won't model much.
3:17
So, first we'll add a data variable.
3:22
oS an instance variable here called data,
and
3:26
we'll assign the value None, initially.
3:28
And then we'll add one more,
we'll call this next_node.
3:31
And to this, we'll assign None as well.
3:34
So we've created two instance variables.
3:36
data, to hold onto the data
that we're storing.
3:39
And next_node to point to
the next node in the list.
3:42
Now we need to add a constructor
to make this class easy to create.
3:46
So we'll add an __init__ method here that
takes self and some data to start off.
3:51
And all we're going to do is assign data
to that instance variable we created.
3:57
So that's all we need to model Node.
4:02
Before we do anything else though,
let's document this.
4:05
So, right after the class definition,
let's create a doc string.
4:08
So """.
4:12
Next line, and we'll say, An object for
4:14
storing a single node of a linked list.
4:19
And then on the next line,
we'll say, Models two attributes,
4:23
data and
the link to the next node in the list.
4:30
And then we'll close this doc string
off with three more quotation marks.
4:33
Okay, using the Node class
is fairly straightforward.
4:41
So we can create a new instance
of Node with some data to store.
4:46
Now the way we're going to do this is
we're going to bring up the console and
4:49
we're going to type out, like we've been
typing out before, python, followed by
4:54
the name of the script that we wrote,
which is linked list linked_list.py.
4:59
But before we do that we're going to
pass an argument to the python command,
5:04
we're gonna say -i and then the name
of the script, linked_list.py.
5:09
So what this does is this is
going to run the python repel,
5:13
the read evaluate print
loop in the console, but
5:17
it's gonna load the contents of our
file into that so that we can use it.
5:20
So I'll hit Enter, and
we have a new instance going.
5:25
And now we can use the Node in here.
5:28
So we can say N1 = Node.
5:31
And since we defined that constructor,
we can pass it some data.
5:33
So we'll say 10 here.
5:37
Now, if we try to inspect this object, the
representation returned isn't very useful,
5:39
which will make things really
hard to debug as our code grows.
5:44
So for example, if I type out N1, you'll
see that we have a valid instance here,
5:48
but it's not very helpful
the way it's printed out.
5:52
So we can customize this by adding
a representation of the object using
5:55
the repr function.
6:00
Now in the terminal still,
we'll type out exist,
6:01
like that, hit Enter to exit the console.
6:05
And then down here,
let's add in some room.
6:08
Okay, and here we'll say,
def __repr, another set of __,
6:13
and then this function
takes the argument self.
6:18
And in here, we can provide a string
representation of what we want printed
6:22
to the console when we inspect that object
inside of it, inside of the console.
6:28
So here we'll say return, again,
this is a string representation.
6:34
So inside quotes we'll say, <Node>,
so this represents a Node instance.
6:38
And the data it contains, it will say %s.
6:43
Which is a Python way of substituting
something into a string,
6:47
string interpolation.
6:52
And outside of the string we can say,
%, again and
6:54
here we're saying we want to
replace this %s with self.data.
6:58
Okay, let's hit Save.
7:03
And before we move on,
let's verify that this works.
7:05
So I'm gonna come in here,
type clear to get rid of everything.
7:08
And then we'll do what we did again.
7:12
And you can just hit the up arrow
a couple of times to get that command.
7:14
All right, so hit Enter.
7:18
And now, just so you know, every time
you run this you start off from scratch.
7:19
So N1 that we created earlier,
not there anymore.
7:24
So it's going to create it, N1 = Node(10).
7:27
And we can type N1 again and
hit Enter, and
7:31
you have a much better representation now.
7:34
So we can see that we have a Node and
it contains the data, 10.
7:37
We can also create another one.
7:41
N2 = Node, that contains the data, 20.
7:44
And now we can say N1.next_node = N2.
7:46
So N1 now points to N2.
7:50
And if we say N1.next_node,
you'll see that it points to that Node.
7:53
The node contained 20.
7:58
Nodes are the building blocks for a list.
8:00
And now that we have a Node object, we can
use it to create a singly linked list.
8:03
So again, I'm gonna exit out of this and
then go back to the text editor.
8:08
And here, we'll create a new class.
8:14
So, class LinkedList:.
8:16
The LinkedList class is
going to define a head.
8:18
And this attribute models the only
node that the list is going to have
8:23
a reference to.
8:27
So here we'll say, head, and
we'll assign None, initially.
8:28
And then, like we did earlier,
let's create a constructor.
8:31
So __init__, this takes self.
8:36
And then inside, like before,
we'll say, self.head = None.
8:41
This is the same as doing this, so
8:45
we can actually get rid of that and
just use the constructor.
8:48
Okay, so again,
8:53
this head attribute models the only node
that the list will have a reference to.
8:54
Since every node points to the next node,
to find a particular node,
9:00
we can go from one node to the next
in a process called list traversal.
9:04
So in the class constructor here, we'll
have set the default value of head to None
9:09
so that new lists created
are always empty.
9:13
Again, you'll notice here, that I didn't
explicitly declare the head attribute at
9:16
the top of the class definition, and
don't worry, that's not an oversight.
9:20
The self.head in the initializer
means that it's still created.
9:25
Okay, so, that's all there is
to modeling a linked list.
9:29
Now, we can add methods that make it
easier to use this data structure.
9:32
First, a really simple doc string
to provide some information.
9:36
So here, we'll create a doc string,
""", and
9:40
then we'll say Singly linked list,
and then close it off.
9:44
A common operation carried out on data
structures is checking whether it
9:49
contains any data or whether it's empty.
9:54
At the moment,
to check if a list is empty,
9:56
we would need to query these instance
variables, head and so on, every time.
9:59
Ideally, we would like to not expose
the inner workings of our data
10:04
structure to code that uses it.
10:09
Instead, let's make this operation
more explicit by defining a method.
10:11
So, we'll say, def is_empty, and
this method takes itself as an argument.
10:16
And here we'll say it
return self.head == None.
10:21
All we're doing here is checking
to see if head is None.
10:25
If it is, this condition evaluates to
true, which indicates the list is empty.
10:29
Now, before we end this video,
10:35
let's add one more convenience method
to calculate the size of our list.
10:36
The name convenience method indicates
that what this method is doing,
10:41
is not providing any additional
functionality that our data structure
10:45
can't handle right now, but instead making
existing functionality easier to use.
10:48
We could calculate the size of our linked
list by traversing it every time using
10:54
a loop until we hit a tail node, but
doing that every time is a hassle.
10:58
Okay, so we'll call this method size,
and as always, it takes (self).
11:04
Unlike calling len on a Python list, not
to be confused with a linked list, which
11:10
is a constant time operation, our size
operation is going to run in linear time.
11:15
The only way we can count how many
items we have is to visit each node and
11:20
call next until we hit the the tail node.
11:25
So we'll start by getting a reference to
the head, we'll say current = self.head.
11:28
Let's also define a local variable
named count with an initial
11:34
value of 0 that will increment
every time we visit a node.
11:38
Once we hit the tail,
count will reflect the size of that list.
11:43
Next, we'll define a while loop that will
keep going until there are no more nodes.
11:47
So we'll say, while current.
11:52
While current is the same as writing
out while current != None, but
11:54
it's more succinct, so
we'll go with this former.
11:59
If the latter is more precise for
you, you can go with that.
12:03
Now inside this loop,
we'll increment the count value.
12:07
So count + = 1.
12:10
+=, if you haven't encountered it before,
is the same as writing count = count + 1.
12:12
So if count is 0 initially,
so it's 0 + 1 is 1, and
12:17
then we'll assign that back to count.
12:21
Okay, so count + = 1.
12:23
Next we're going to assign the next
node in the list to current.
12:26
So current = current.next_node.
12:31
This way, once we get to the tail and
call next_node,
12:34
current will equal None and
the while loop terminates.
12:39
So at the end we can return count.
12:44
As you can see, we need to visit
every node to determine the size,
12:46
meaning our algorithm runs in linear time.
12:52
So let's document this.
12:55
Up in our document string,
which we'll add now to size,
12:57
we'll say,
Returns the number of nodes in the list.
13:02
Take linear time.
13:06
Let's take a break here.
13:08
We can now create lists,
check if they're empty and check the size.
13:09
In the next video, let's start
implementing some common operations.
13:13