Traversing a Linked List using recursion - Python Tutorial

- [Instructor] In this chapter we will be learning how to traverse data structures using recursion. Traversing a data structure means systematically visiting each item stored within it. One common use of recursion is to traverse data structures which have a naturally recursive definition. A particularly important case of this is trees which we will cover soon. To get us started, we will look at the simpler example of recursively traversing a linked list. Just before we do though, here are some examples of where recursive traversal is used. So linked lists the basic idea, if you're not familiar with it is we have nodes which have two data fields. So the first data field would be what we call the data cargo. So in the image here you can see the first node has the data cargo of A and then the second field of a node is a pointer to the next node in the list. So you can see in the diagram that node A the pointer field is pointing to B and then for node B the point of field is pointing to C and likewise for D until the end of the list we know we've got there because the point of field points to a null value such as none in Python or just null if you're just doing this conceptually. We also have a head pointer which tells us where the entry point for the list is. And so these ingredients together form a link list. So let's see what this looks like in Python. So you can check out Branch 06_01b, if you're following along with Git or simply open chapter six, video one linked list recursive.py. And let's make a start. So we're using some object oriented programming here, very simple example of it. We're creating a class called node and let's go ahead and define that now. So def_init quite jump automatically put self in there for me data, and then next=None. So if you're not familiar with ROPA tool, what I'm doing here, this is called the constructor. So in Python, the constructor has double underscore in it. And this is the function that gets cool when we create objects from a class. And there's a default argument here and next equals none. So if we don't pass that in, when we create an object, then it will be set to none. And all of this will become clear as we proceed. So I'm going to do self.data= data and I'm going to do self.next= next. Now I should just point out that next is actually a key word in Python. So, it's not actually best practice to do that. But for clarity of explaining the concept, I think it's worth using that and it's not going to be a problem in this instance. So we now have our node class so we can create actual instances. As the basic idea with object on the program if you're not familiar, is we have a class which is a template and then from that template we create instances which are called objects from that class. So item one, it's going to be a node and let's set it some value to "dog." What this does is it calls the constructor and it creates an object called item one and we've passed in dog. So dog will be the nodes data value but the next value will be none because of this default argument in the constructor. Next, just going to put an extra line there to stop by chum, telling me that there's not enough spaces. And then I'm going to do Item2= Node and this time the data is going to be "cat." And then Item3= Node and its data is a "rat." So we've got these three nodes that we don't have a link list at this point because we just have three unconnected nodes. So what we're going to do is connect them together. So let's do Item1.next = Item2 and then Item2.next = Item3. So now we do have a link that's because we've joined these nodes up by setting the next property to other nodes. And we haven't done that for Item3 because Item3 is going to be the end of our list. Just run that, make sure there's no errors. So that's all looking good, no output yet. So let's write a function to traverse this list or to traverse any list. So def_traverse, and it's going to take the head. Now, this is important because we need to know where we're starting our traversal. So head is going to be the first node of our link list. So the base case, this is if_head_is None. Now Python is great like this, it reads a lot like English I could have done equal equals for comparison but when we're using none, we can actually say is. So if that's the case, we return, but if that's not the case, we go into the recursive case. So write that comment Recursive. So what we do here is we actually print because the main point of this particular traversal is to just output the data. You might have different purposes but this is just a basic example. So we're going to print, head.data. So that means printing the current data for the current mode. And then we're going to recursively call traverse and the new head that we're going to pass in is head.next. So if we just go back to our diagram to show you what's happening here. This is going to be fine until we get to the end and then head.next is going to be none. So then we'll know to exit the recursion. So this should work, let's try it. So we traverse and we pass in Item1. So we pass in the first node of our linked list. And you can see, we go dog cat rat which is what you would expect if you think about what we did up here on lines, 13 to 17 we created the nodes and then we link them in such a way that the item one so dog pointed to cat which pointed to rat and rat pointed to none. That's how we knew how to stop. Now, it's probably better practiced just to rearrange this. So I put my function above my main code and bring the matter in these little examples, but it's good to get these habits down from the beginning or from as early on as possible. There's just one more thing I want to show you while we're on the topic of recursive link lists or recursively traversing link lists. So if I just comment out this line for a moment and we're going to now create our linked list just with one line of code. So head = node whose data cargo is dog and whose next property is a Node itself. And the data for that is going to be cat, and the next property is going to be a Node itself and that's going to have the cargo of rat. And the next property for the rat node is a none then if I run that you see we get exactly the same output as we did before. And we defined the whole link list with one line of code. So this is a really, I think an interesting example of recursively defining a link list. It's kind of like at the beginning of the course when we saw those examples of the recursive story with the rubbers in the cave or the idea of a mirror, reflecting its own reflection. So this is a nice example of that same concept. You now know how to create and traverse a link lists using recursion in Python. If you work a lot with link lists, you will need more functionality than what we have covered here for which you can check out other courses in the library. The main goal here was to prepare you for one of the most important applications of recursion and that is tree traversal coming up next.