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
In the previous video we created the outlines of a linked list but without the ability to add nodes it's not really a list. Let's define an add operation to prepend nodes
Code Snippet for repr Function:
def __repr__(self):
"""
Returns a string representation of the list.
Takes O(n) time
"""
nodes = []
current = self.head
while current:
if current is self.head:
nodes.append("[Head: %s]" % current.data)
elif current.next_node is None:
nodes.append("[Tail: %s]" % current.data)
else:
nodes.append("[%s]" % current.data)
current = current.next_node
return '-> '.join(nodes)
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
At the moment, we can create
an empty list, but nothing else.
0:00
Let's define a method to
add data to our list.
0:03
Technically speaking, there are three
ways we can add data to a list.
0:06
We can add nodes at the head of the list,
0:09
which means that the most recent
node we created will be the head.
0:12
And the first node we created will be
the tail or we could flip that around.
0:16
Most recent nodes
are the tail of the list and
0:20
the first node to be added is the head.
0:22
I mentioned that one of the advantages
of linked lists over arrays
0:25
is that inserting data into the list is
much more efficient than to the array.
0:28
This is only true if we're
inserting at the head or the tail.
0:32
Technically speaking,
this isn't an insert, and
0:36
you'll often see this method called add
prepend if the data is added to the head
0:39
or append if it's added to the tail.
0:43
A true insert is where you can insert
the data at any point in the list,
0:46
which is our third way of adding data.
0:50
We're gonna circle back on that if
we wanted to insert at the tail,
0:52
then the list needs
a reference to the tail node.
0:56
Otherwise, we would have
to start at the head and
0:59
walk down the length of the list or
traverse it to find the tail.
1:02
Since our list only keeps
a reference to the head,
1:05
we're going to add new items
at the head of the list.
1:09
Now before we add our new method, I
forgot that I didn't show you in the last
1:13
video how to actually use
the code we just added and
1:17
how to check every time when we add new
code that it works correctly Directly.
1:20
So like before,
we're going to bring up the console and
1:25
here we're gonna say
python -i linked_list.py,
1:29
which should load it,
load the contents of our file.
1:34
And now we'll start here by creating
a linked list, so l =LinkedList(),
1:38
and then we'll use a node, so
N1 = Node with the value 10.
1:44
And now we can assign N1 to the nodes or
to the LinkedList's head attribute.
1:49
So l1.head = N1.
1:55
And then,
we can see if size works correctly.
1:58
So if we call l1.size and
since this is a method,
2:02
we need a set of parenthesis at the end.
2:05
Enter.
2:07
You'll see that get that one correctly.
2:08
Okay, so it works!
2:10
Now, let's add our new method,
which we're going to call add.
2:11
Add is going to accept some data and
add to the list inside of the node.
2:18
So we'll say def add().
2:24
And every python method
takes self as an argument.
2:26
And then, we want to add some data to
this node, so we're gonna say data for
2:29
the second argument.
2:34
Inside the method, first, we'll create
a new node to hold on to the data.
2:35
So new_node = Node(data).
2:39
Before we set the new node
as the head of the list.
2:44
We need to point the new
node's next property
2:47
at whatever node is currently at Head.
2:50
This way when we set the new
node as the Head of the list
2:54
we don't lose a reference to the old Head.
2:56
So new_node.next node = self.head.
2:59
Now, if there was no node at head this
correctly sets next node to none.
3:06
Now we can set the new node
as the head of the node.
3:12
So say self.head = new_node.
3:16
Because the insert operation is
simply a reassignment of the head and
3:19
next node properties,
this is a constant time operation.
3:25
So let's add that in as a down string.
3:30
First, what the method does.
3:34
So it adds a new node containing
data at the head of the list.
3:37
This operation takes constant time
which is our best case scenario.
3:46
Okay, let's test this out.
3:52
So we're gonna bring the console back up.
3:54
We'll exit out of our current level and
3:56
we'll load the contents of the file again,
and
4:01
now we don't need to create
a node like we did earlier.
4:05
So we can say l = LinkedList.
4:08
l.add(1).
4:11
Okay, let's see if this works.
4:13
We'll call size.
4:15
And if it worked, then linked
list should now have a size of 1.
4:17
There we go.
4:23
You can also do l.add(2),
l.add(3) and l.size should now be 3.
4:24
There we go.
4:30
If I were to type l and
4:32
just hit print, again,
what we get in the repl is nothing useful.
4:33
So like before we'll implement
the repr function for our linked list.
4:39
Now, I'm just going to copy paste
this in and we'll walk through it.
4:44
Okay, so this is what our
implementation of repr looks like for
4:49
the linked list object.
4:53
You can grab this code from
the note section of this video.
4:55
Okay, so at the top you'll see a doc
string where it says it returns a string
4:59
representation of the list.
5:02
And like everything we need to do with
a link list we need to traverse it.
5:04
So this is going to take linear time.
5:08
We start by creating an empty list.
5:10
Now, I need to distinguish this
is python list not linked list.
5:12
So we create an empty list called nodes,
and to nodes we're going to add strings
5:16
that have a description,
that provide a description of each node.
5:21
But we're not going to use the description
that we implemented in the node class,
5:25
because we're gonna
customize it a bit here.
5:29
Next, we stand by signing
self.head to current.
5:32
So we sort have a point to the head node.
5:35
As long as current doesn't equal non,
5:39
which mean we not added the tail we
are going to implement some logic.
5:41
So in the first scenario, if the node
assign to current is the same as the head.
5:45
Then we're going to append
this string to our nodes list.
5:50
And the string is simply going to
say that hey, this is a head node.
5:54
And it contains some data,
which we'll extract using current.data.
5:59
The next scenario is if the node
assigned to current next node is none,
6:04
meaning we're at the tail node, then
we'll assign a different kind of string.
6:08
So it's the same as over there
except we're saying tail here.
6:13
And then finally, in any other scenario
which means we're not at the head or
6:16
not at the tail we'll simply
print the nodes value inside.
6:20
And again,
we'll extract it using current.data.
6:23
With every iteration of the loop
will move current forward by calling
6:26
current.next_node and reassigning it.
6:30
And then in the very end when we're done,
we'll join all the strings
6:32
that are inside the nodes list
together using the python join method.
6:37
And we'll say that with every join.
6:41
So when you join these two strings
together to make one string,
6:44
you need to put this set of
characters in between, all right?
6:47
So let's see what this looks like.
6:51
So I'm going to come down here,
exit out of the console again,
6:52
clear it out, load the contents of
the file again, and let's try that.
6:55
So we'll say l = LinkedList.
7:00
All right, so l.add1, l.add2, l.add(3).
7:04
That seems enough.
7:10
And then now if I type our l and
hit enter,
7:11
we get a nice string
representation of the list.
7:14
So you can see that we add
every new node to the head.
7:17
So we added one first.
7:20
One ends up being the tail,
because it keeps getting pushed out.
7:22
Then 2, and then finally 3,
so 3 is at the head.
7:25
So far we've only implemented
a single method which
7:29
functions much like the append
method on a python list or an array,
7:33
except it adds it to
the start of the length list.
7:38
It prepends it.
7:41
Like a pen, this happens in constant time.
7:43
In the next video, let's add
the ability to search through our list.
7:47
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