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
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