Heads up! To view this whole video, sign in with your Courses account or enroll in your free 7-day trial. Sign In Enroll
Well done!
You have completed Introduction to Data Structures!
You have completed Introduction to Data Structures!
Preview
Despite 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
Resources
Related Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign upRelated Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign up
[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
You need to sign up for Treehouse in order to download course files.
Sign upYou need to sign up for Treehouse in order to set up Workspace
Sign up