1 00:00:00,600 --> 00:00:04,084 Much like inserts, removing a node is actually quite fast and 2 00:00:04,084 --> 00:00:05,564 occurs in constant time. 3 00:00:05,564 --> 00:00:09,375 But to actually get to the node that we want to remove and modify the next 4 00:00:09,375 --> 00:00:13,136 connections, we need to traverse the entire list in our worst case. 5 00:00:13,136 --> 00:00:15,726 So in the worst case, this takes linear time. 6 00:00:15,726 --> 00:00:19,249 Let's add this operation to our data structure. 7 00:00:19,249 --> 00:00:22,298 There are two ways we can define remove method. 8 00:00:22,298 --> 00:00:26,103 One, where we provide a key to remove as an argument, and 9 00:00:26,103 --> 00:00:28,180 one where we provide an index. 10 00:00:28,180 --> 00:00:32,364 Now in the former, the key refers to the data the node stores. 11 00:00:32,364 --> 00:00:36,254 So in order to remove that node, we would first need to search for 12 00:00:36,254 --> 00:00:37,922 data then matches the key. 13 00:00:37,922 --> 00:00:41,585 I'm going to implement that first method, which we'll call remove. 14 00:00:41,585 --> 00:00:44,598 And I'll leave it up to you to get some practice in and 15 00:00:44,598 --> 00:00:48,516 implement a remove at index method to complete our data structure. 16 00:00:48,516 --> 00:00:51,375 So I'll add this aft to the insert method right here. 17 00:00:54,449 --> 00:00:58,458 Remove is going to accept a key which we'll need to search for 18 00:00:58,458 --> 00:01:00,350 before we can remove a node. 19 00:01:00,350 --> 00:01:05,579 Earlier, we defined a search method that found a node containing data that matches 20 00:01:05,579 --> 00:01:10,375 a key, but we can't use that method as is for the implementation of remove. 21 00:01:10,375 --> 00:01:14,169 When we remove a node, much like the insert operation, 22 00:01:14,169 --> 00:01:17,168 we need to modify the next node references. 23 00:01:17,168 --> 00:01:20,830 The node before the match needs to point to the node after the match. 24 00:01:20,830 --> 00:01:24,010 If we use the search method we defined earlier, 25 00:01:24,010 --> 00:01:27,358 we get the node we want to remove as a return value. 26 00:01:27,358 --> 00:01:29,939 But because this is a singly linked list, 27 00:01:29,939 --> 00:01:33,128 we can't obtain a reference to the previous node. 28 00:01:33,128 --> 00:01:37,136 Like I said earlier, if this was a doubly linked list, we could use the search 29 00:01:37,136 --> 00:01:40,360 method since we would have a reference to that previous node. 30 00:01:40,360 --> 00:01:45,058 We'll start here by setting a local variable named current to 31 00:01:45,058 --> 00:01:46,510 point to the head. 32 00:01:46,510 --> 00:01:51,414 Well, let's also define a variable named previous that we'll set 33 00:01:51,414 --> 00:01:56,156 to none to keep track of the previous node as we traverse the list. 34 00:01:56,156 --> 00:02:01,380 Finally, let's declare a variable named found that we'll set to False. 35 00:02:01,380 --> 00:02:06,700 Found is going to serve as a stopping condition for the loop that we'll define. 36 00:02:06,700 --> 00:02:11,540 We'll use the loop to keep traversing the linked list as long as found is false, 37 00:02:11,540 --> 00:02:14,900 meaning we haven't found the key that we're looking for. 38 00:02:14,900 --> 00:02:18,620 Once we've found it, we'll set found to true and the loop terminates. 39 00:02:18,620 --> 00:02:19,644 So let's set up our loop. 40 00:02:19,644 --> 00:02:26,074 So I'll say, while current and not found. 41 00:02:26,074 --> 00:02:30,431 Here we're defining a while loop that contains two conditions. 42 00:02:30,431 --> 00:02:36,861 First we tell the loop to keep iterating as long as current does not equal none. 43 00:02:36,861 --> 00:02:38,477 When current equals none, 44 00:02:38,477 --> 00:02:43,280 this means we've gone past the tail node, and the key doesn't exist. 45 00:02:43,280 --> 00:02:44,760 This second condition, 46 00:02:44,760 --> 00:02:49,940 ask the loop to keep evaluating as long as not found equals true. 47 00:02:49,940 --> 00:02:53,400 Now, this may be tricky because it involves a negation here. 48 00:02:53,400 --> 00:02:55,760 Right, now found is set to False. 49 00:02:55,760 --> 00:02:59,670 So not found, not false equals true. 50 00:02:59,670 --> 00:03:01,880 This not operator flips the value. 51 00:03:01,880 --> 00:03:06,362 When we find the key and we set found to true, not true, 52 00:03:06,362 --> 00:03:11,245 not found, we'll equal false then and the loop will stop. 53 00:03:11,245 --> 00:03:14,910 The and in the while loop means that both conditions, 54 00:03:14,910 --> 00:03:20,211 current being a valid node and not found equaling True, both have to be true. 55 00:03:20,211 --> 00:03:24,226 If either one of them evaluates to false, then the loop will terminate but 56 00:03:24,226 --> 00:03:27,745 inside the loop there are three situations that we can run into. 57 00:03:27,745 --> 00:03:31,080 First, the key matches the current nodes data and 58 00:03:31,080 --> 00:03:33,787 current is still at the head of the list. 59 00:03:33,787 --> 00:03:37,807 This is a special case because the head doesn't have a previous node and 60 00:03:37,807 --> 00:03:40,495 its the only node being referenced by the list. 61 00:03:40,495 --> 00:03:42,550 Let's handle this case. 62 00:03:42,550 --> 00:03:48,760 So I'll say if current.data == key and current == self.head, 63 00:03:48,760 --> 00:03:55,760 which you can write out as current == self.head or current is self.head. 64 00:03:55,760 --> 00:03:57,740 Now if we hid this case, 65 00:03:57,740 --> 00:04:02,995 we'll indicate that we found the key by setting found to True. 66 00:04:02,995 --> 00:04:07,781 And then this means that on the next pass, this is going to evaluate 67 00:04:07,781 --> 00:04:12,658 to false cuz not true would be false, and then the loop terminates. 68 00:04:12,658 --> 00:04:17,806 Once we do that, we want to remove the current node and since it's the head node, 69 00:04:17,806 --> 00:04:21,950 all we need to do is point head to the second node in the list. 70 00:04:21,950 --> 00:04:27,371 Which we can get by referencing the next node attribute on current, 71 00:04:27,371 --> 00:04:30,522 self.head = current.next_node. 72 00:04:30,522 --> 00:04:33,985 So when we do this, there's nothing pointing to that first node, so 73 00:04:33,985 --> 00:04:36,210 it's automatically removed. 74 00:04:36,210 --> 00:04:39,900 The next scenario is when the key matches data in the node, and 75 00:04:39,900 --> 00:04:41,640 it's a node that's not the head. 76 00:04:41,640 --> 00:04:47,944 So here I'll say elseif current.data == key. 77 00:04:47,944 --> 00:04:52,706 If the current node contains the key we're looking for, we need to remove it. 78 00:04:52,706 --> 00:04:56,727 To remove the current node, we need to go to the previous node and 79 00:04:56,727 --> 00:05:00,908 modify its next node reference to point to the node after current. 80 00:05:00,908 --> 00:05:06,601 But first, we'll set found to True and then we'll switch out the references. 81 00:05:06,601 --> 00:05:12,081 So previous.next_node = current.next_node. 82 00:05:12,081 --> 00:05:17,060 So far we haven't written any code to keep track of the previous node. 83 00:05:17,060 --> 00:05:20,424 We'll do that in our else case here. 84 00:05:20,424 --> 00:05:25,056 So if we hit the else case, it means that the current node we're evaluating doesn't 85 00:05:25,056 --> 00:05:27,230 contain the data that matches the key. 86 00:05:27,230 --> 00:05:30,390 So in this case, we'll make previous point to current node, and 87 00:05:30,390 --> 00:05:32,430 then set current to the next node. 88 00:05:32,430 --> 00:05:38,010 So previous = current, and current = current.next_node, 89 00:05:38,010 --> 00:05:42,360 and that's it for the implementation of remove. 90 00:05:42,360 --> 00:05:46,490 Now, we're not doing anything at the moment with the node we're removing, but 91 00:05:46,490 --> 00:05:50,148 it's common for remove operations to return the value being removed. 92 00:05:50,148 --> 00:05:57,120 So at the bottom, outside the while loop, let's return current. 93 00:05:57,120 --> 00:06:01,140 And with that, we have a minimal implementation of a link list and 94 00:06:01,140 --> 00:06:03,440 your first custom data structure. 95 00:06:03,440 --> 00:06:04,900 How cool is that? 96 00:06:04,900 --> 00:06:09,355 There's quite a bit we can do here to improve our data structure particularly in 97 00:06:09,355 --> 00:06:10,627 making it easy to use. 98 00:06:10,627 --> 00:06:13,088 But this is a good place to stop. 99 00:06:13,088 --> 00:06:16,601 Before we move on to the next topic, let's document our method. 100 00:06:16,601 --> 00:06:21,234 So the top, another doc string, and here we'll say, 101 00:06:21,234 --> 00:06:26,520 Removes Node containing data that matches the key. 102 00:06:26,520 --> 00:06:33,790 Also, it Returns the node or None if the key doesn't exist. 103 00:06:33,790 --> 00:06:37,960 And finally, This takes linear time because in the worst case scenario, 104 00:06:37,960 --> 00:06:40,900 we need to search the entire list. 105 00:06:40,900 --> 00:06:46,717 If you'd like to get in some additional practice implementing functionality for 106 00:06:46,717 --> 00:06:51,940 link list, two methods you can work on are remove it index and node at index 107 00:06:51,940 --> 00:06:56,850 to allow you to easily delete or read values in a list at a given index. 108 00:06:56,850 --> 00:07:00,802 Now that we have a linked list, let's talk about where you can use them. 109 00:07:00,802 --> 00:07:04,530 The honest answer is, not a lot of places. 110 00:07:04,530 --> 00:07:08,703 Link lists are really useful structures to build for learning purposes. 111 00:07:08,703 --> 00:07:12,910 Because they're relatively simple, and are a good place to start to introduce 112 00:07:12,910 --> 00:07:17,300 the kinds of operations we need to implement for various data structures. 113 00:07:17,300 --> 00:07:21,230 It is quite rare, however, that you will need to implement a link list on your own. 114 00:07:21,230 --> 00:07:23,635 There are typically much better, and 115 00:07:23,635 --> 00:07:27,933 by that I mean much more efficient data structures that you can use. 116 00:07:27,933 --> 00:07:30,471 In addition many languages like Java, for 117 00:07:30,471 --> 00:07:34,285 example, provide an implementation of a linked list already. 118 00:07:34,285 --> 00:07:38,089 Now that we have a custom data structure, let's do something with it. 119 00:07:38,089 --> 00:07:42,957 Let's combine the knowledge we have, and look at how a sorting algorithm can be 120 00:07:42,957 --> 00:07:46,239 implemented across two different data structures.