Heads up! To view this whole video, sign in with your Courses account or enroll in your free 7-day trial. Sign In Enroll
Preview
Start a free Courses trial
to watch this video
A common operation on every data structure is the ability to search for data stored. In this video let's add a search method that let's us search for a particular item of data.
This video doesn't have any notes.
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
For the search operation we're going to
define a method that takes a value to
0:00
search for and returns either
the node containing the value,
0:04
if the value is found or none if it isn't.
0:08
So right after, actually you know what
we'll make sure repr is the last function,
0:10
or last method in our class,
so we'll add it above it.
0:17
So here we'll say def search self and
then key.
0:21
In the last video,
0:26
we implemented the repr method to provide
a string representation of the list.
0:26
So we're going to use similar logic
here to implement the search function.
0:31
We'll start by setting a local variable
current to point to the head of the list.
0:36
While the value assigned to current is
a valid node, that is, it isn't none,
0:42
we'll check if the data on that node
matches the key that we're searching for.
0:47
So while current we'll say if current.data
0:53
is the key then we'll return current.
0:58
If it does match, we'll go ahead and
return it like we've done here.
1:02
But if it doesn't, we'll assign the next
node in the list to current and
1:06
check again.
1:11
So we'll say, else,
1:12
current = current.next_node.
1:15
Once we hit the tail node and
haven't found the key,
1:20
current gets set to none and
the while loop exits.
1:23
At this point we know the list
doesn't contain the key so
1:27
we can return none, okay?
1:31
That completes the body of our method.
1:33
Let's add a doc string to document this.
1:36
So up at the top, we'll say, search for
1:39
the first node containing
data that matches the key.
1:44
Now this is important because if our
linked list contains more than one node
1:51
with the same value it doesn't matter.
1:55
We're going to return the first
one with this implementation.
1:58
We'll also say here that it returns
the node or 'None' if not found.
2:01
In the worst case scenario, we'll need to
check every single node in the list before
2:09
we find the key or fail, and as a result
this operation runs in linear time.
2:13
So I'll say, takes 0(n) or linear time.
2:19
So far we haven't seen anything
that indicates this data structure
2:26
has any advantage over an array or
a python list, but we knew that.
2:30
I mentioned, the strength of
linked lists comes in inserts and
2:35
deletes at specific positions.
2:39
We'll check that out in the next video,
but
2:40
as always, before we end this one,
let's make sure everything works.
2:43
So we'll load the contents
of the file again.
2:48
l = LinkedList().
2:54
And then we'll say l.add(10),
1.add 20, 2, doesn't matter.
2:57
l.add(45), and one more.
3:04
l.add(15).
3:08
Now, we can say l.search, and we need
to give it a value, so we'll say 45.
3:10
And this returns a node or none, so
we'll say n =, and then we'll hit Enter.
3:15
If this works, n should be a node.
3:22
Okay, weirdly, n does not work here,
at least, it says it's not a node,
3:26
which means I made a mistake
in typing out our code.
3:30
And looking at it immediately,
it's fairly obvious.
3:34
So this return None needs to
be outside of the while loop.
3:36
Okay, so I'm gonna hit save now.
3:41
So make sure it's on
the same indentation here,
3:42
which means it's outside the while loop.
3:45
And then we'll run through this again.
3:47
Okay, so l = linked list, l.add(10),
3:51
l.add(2), l.add 45 and
what was the last one we did?
3:56
I believe it was 15.
4:03
And now we should be able to say l.search.
4:06
Remember we're assigning this to a node,
to a variable.
4:09
So l.search(45).
4:12
And there you go.
4:17
We get that node back and we can hit l.
4:18
And we'll see
a representation of our list.
4:21
Okay, so again, in the next video,
inserts and deletes at specific positions.
4:24
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