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
To conclude our list of operations let's add the ability to delete data from a linked list
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
Much like inserts,
removing a node is actually quite fast and
0:00
occurs in constant time.
0:04
But to actually get to the node that
we want to remove and modify the next
0:05
connections, we need to traverse
the entire list in our worst case.
0:09
So in the worst case,
this takes linear time.
0:13
Let's add this operation
to our data structure.
0:15
There are two ways we can
define remove method.
0:19
One, where we provide a key
to remove as an argument, and
0:22
one where we provide an index.
0:26
Now in the former, the key refers
to the data the node stores.
0:28
So in order to remove that node,
we would first need to search for
0:32
data then matches the key.
0:36
I'm going to implement that first method,
which we'll call remove.
0:37
And I'll leave it up to you
to get some practice in and
0:41
implement a remove at index method
to complete our data structure.
0:44
So I'll add this aft to
the insert method right here.
0:48
Remove is going to accept a key
which we'll need to search for
0:54
before we can remove a node.
0:58
Earlier, we defined a search method that
found a node containing data that matches
1:00
a key, but we can't use that method as
is for the implementation of remove.
1:05
When we remove a node,
much like the insert operation,
1:10
we need to modify
the next node references.
1:14
The node before the match needs to
point to the node after the match.
1:17
If we use the search
method we defined earlier,
1:20
we get the node we want to
remove as a return value.
1:24
But because this is a singly linked list,
1:27
we can't obtain a reference
to the previous node.
1:29
Like I said earlier, if this was a doubly
linked list, we could use the search
1:33
method since we would have
a reference to that previous node.
1:37
We'll start here by setting
a local variable named current to
1:40
point to the head.
1:45
Well, let's also define a variable
named previous that we'll set
1:46
to none to keep track of the previous
node as we traverse the list.
1:51
Finally, let's declare a variable
named found that we'll set to False.
1:56
Found is going to serve as a stopping
condition for the loop that we'll define.
2:01
We'll use the loop to keep traversing
the linked list as long as found is false,
2:06
meaning we haven't found
the key that we're looking for.
2:11
Once we've found it, we'll set found
to true and the loop terminates.
2:14
So let's set up our loop.
2:18
So I'll say, while current and not found.
2:19
Here we're defining a while loop
that contains two conditions.
2:26
First we tell the loop to keep iterating
as long as current does not equal none.
2:30
When current equals none,
2:36
this means we've gone past the tail node,
and the key doesn't exist.
2:38
This second condition,
2:43
ask the loop to keep evaluating
as long as not found equals true.
2:44
Now, this may be tricky because
it involves a negation here.
2:49
Right, now found is set to False.
2:53
So not found, not false equals true.
2:55
This not operator flips the value.
2:59
When we find the key and
we set found to true, not true,
3:01
not found, we'll equal false then and
the loop will stop.
3:06
The and in the while loop
means that both conditions,
3:11
current being a valid node and not found
equaling True, both have to be true.
3:14
If either one of them evaluates to false,
then the loop will terminate but
3:20
inside the loop there are three
situations that we can run into.
3:24
First, the key matches
the current nodes data and
3:27
current is still at the head of the list.
3:31
This is a special case because the head
doesn't have a previous node and
3:33
its the only node being
referenced by the list.
3:37
Let's handle this case.
3:40
So I'll say if current.data == key and
current == self.head,
3:42
which you can write out as current ==
self.head or current is self.head.
3:48
Now if we hid this case,
3:55
we'll indicate that we found
the key by setting found to True.
3:57
And then this means that on the next pass,
this is going to evaluate
4:02
to false cuz not true would be false,
and then the loop terminates.
4:07
Once we do that, we want to remove the
current node and since it's the head node,
4:12
all we need to do is point head
to the second node in the list.
4:17
Which we can get by referencing
the next node attribute on current,
4:21
self.head = current.next_node.
4:27
So when we do this, there's nothing
pointing to that first node, so
4:30
it's automatically removed.
4:33
The next scenario is when the key
matches data in the node, and
4:36
it's a node that's not the head.
4:39
So here I'll say elseif
current.data == key.
4:41
If the current node contains the key
we're looking for, we need to remove it.
4:47
To remove the current node,
we need to go to the previous node and
4:52
modify its next node reference to
point to the node after current.
4:56
But first, we'll set found to True and
then we'll switch out the references.
5:00
So previous.next_node = current.next_node.
5:06
So far we haven't written any code
to keep track of the previous node.
5:12
We'll do that in our else case here.
5:17
So if we hit the else case, it means that
the current node we're evaluating doesn't
5:20
contain the data that matches the key.
5:25
So in this case, we'll make
previous point to current node, and
5:27
then set current to the next node.
5:30
So previous = current, and
current = current.next_node,
5:32
and that's it for
the implementation of remove.
5:38
Now, we're not doing anything at the
moment with the node we're removing, but
5:42
it's common for remove operations
to return the value being removed.
5:46
So at the bottom, outside the while loop,
let's return current.
5:50
And with that, we have a minimal
implementation of a link list and
5:57
your first custom data structure.
6:01
How cool is that?
6:03
There's quite a bit we can do here to
improve our data structure particularly in
6:04
making it easy to use.
6:09
But this is a good place to stop.
6:10
Before we move on to the next topic,
let's document our method.
6:13
So the top, another doc string,
and here we'll say,
6:16
Removes Node containing
data that matches the key.
6:21
Also, it Returns the node or
None if the key doesn't exist.
6:26
And finally, This takes linear time
because in the worst case scenario,
6:33
we need to search the entire list.
6:37
If you'd like to get in some additional
practice implementing functionality for
6:40
link list, two methods you can work on
are remove it index and node at index
6:46
to allow you to easily delete or
read values in a list at a given index.
6:51
Now that we have a linked list,
let's talk about where you can use them.
6:56
The honest answer is, not a lot of places.
7:00
Link lists are really useful structures
to build for learning purposes.
7:04
Because they're relatively simple, and
are a good place to start to introduce
7:08
the kinds of operations we need to
implement for various data structures.
7:12
It is quite rare, however, that you will
need to implement a link list on your own.
7:17
There are typically much better, and
7:21
by that I mean much more efficient
data structures that you can use.
7:23
In addition many languages like Java, for
7:27
example, provide an implementation
of a linked list already.
7:30
Now that we have a custom data structure,
let's do something with it.
7:34
Let's combine the knowledge we have, and
look at how a sorting algorithm can be
7:38
implemented across two
different data structures.
7:42
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