Linked lists walkthrough

- [Instructor] Let's walk through a coding example of a linked list implementation. So here in VS Code I'm going to open up the linkedlist_start.py file, and that's in my LinkedList folder inside the Data Structures Chapter. And you can see here that I already have some code in the starting point. So, at the top of the file is the class that implements the node type that will be stored in the linked list. It's just a simple class that stores a single data field which is named val here, and you can see that there's only one single next field, so that indicates that this is a singly linked list.

And there are methods in this class for getting and setting both the data field, and the next field pointer. So the linked list class itself is next, and there are already fields for the head. This is the head reference right here, as well as a count field that keeps track of how many nodes they're in list. There's a utility function that prints the contents of the list, that's named dump_list down here. And what we're going to do is fill in the insert, find, and delete at functions.

So for simplicity, we're only going to insert items at the head of the list. So, I have a line of code that creates a new node right here, and we just need to insert that new node into the list. So I'll write new_node.set_next, and that's going to be the current head of this list. Then, I'll tell the head to point to the new node.

And then I'll update the count. The find function is also relatively simple to implement. So the code starts at the head of the list, and then we just need to iterate over the nodes until we found the first one that has the matching data argument. So we're going to be searching for the node that contains this value. So I've already got the starting point which is equal to the head, and I'll say while item is not None, what we're going to do is if the item get data function returns with the value that we're looking for, then we're going to return that item.

Otherwise, we're going to get the next item. And we do that by writing item.get_next. Alright, so, let's go ahead, and try out what we already have, and if we scroll all the way down, you can see that we have some code here that creates a new linked list and then inserts some items into that list, prints out the list using the dump list function, and then uses the get count and find functions to find some data in the list.

So we know that 13 is in the list, 'cause it's right there, and then we're going to try to find an item that we know doesn't exist. So let's go ahead and run this, and to run this I'll just go out to the terminal, and I'm going to cd into my Chapter Two folder, and I'm going to run this by typing python three, and this is called linkedlist_start. Okay, so we can see that we printed out the contents of the list after all the inserts, and then here we printed out the item count which is four.

And then when we go to find the number 13, we can see that it's there, comes back with this Node object. And then when we try to find the 78, that comes back with the result of None, because that's not currently in the list. Okay, so let's implement the delete at method. So I'll clear this, and let's scroll back up to delete at. So the function will delete the node that is at the given index. We're not going to be looking for a value here, we'll just simply say, at this index go ahead and delete whatever that one is.

So the current code checks to make sure that the index is within the number of existing nodes in the list. So if we give it an index that's more than what we currently have, we just simply return. So we need to add the logic to actually do the deletion. So first, we'll check to see if we're deleting the head node, because if we are, then we just need to set the new head node to whatever the current head node is pointing at. So let's write if index is zero, then self.head is equal to self.head.get_next.

Otherwise, we have to advance to the node that is just before the one we want to delete. So I'll write else, and we'll have a temp index counter, and we'll start off at zero, and we'll have a temporary variable named node, and we'll start that off at the head. And now we're going to advance down the list until we get to, alright, while temp index is less than idx minus one.

Now we want the node that's right before the one we're deleting, because that's the one whose next pointer we have to fix. So I'll write node is equal to node.get_next, and I'll increase the temp index variable. But once we found the previous node to the one we want to get rid of, we just set its next field to point to the node that's after the one we want to delete.

So I'll write node.set_next, and we're going to write node.get_next().get_next, and then of course finally we have to decrement the count to reflect the fact that we've gotten rid of a node. Alright, so let's go ahead down here, and let's comment out the previous example.

And I'll uncomment these lines here. So we create a list, we insert four items, we print out the lists content, and then we're going to delete the item at index three. So that's the last item in the list, and then we're going to print out the item count after we do the deletion, and then we're going to try to find the item that's, has the value of 38. So remember that because we insert the 38 first, and we keep inserting at the head that means that by the time we get to this point in the code, the 38 will be the last in line.

So that guy should be gone when we do the deletion. So let's go ahead and save, and once again, let's go back to the terminal. And in the terminal, I'll write python3 linklist_start. And you can see that now we print out the list after all the insertions, then we do the deletion so the count is now at three, and we try to find the 38, and it's not there anymore, and we dump the list, and you can see, sure enough, it's not there.