Implementing Search4:28 with Pasan Premaratne
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.
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 up