Traversing a linked list in Python
Introduction
There are a number of operations we might want to carry out on a linked list. These include counting the number of items in a list, printing the data out and searching for a data item. Each of these operations involve traversing the list, or starting at the beginning and moving along the list, one node at a time. You must always start at the head of a linked list. You then go from the head to the next node, as determined by the pointer. You keep following pointers in each node until you get to the null pointer, which signals that the end of the list has been reached. This is how this kind of data structure is designed to work. You can't just jump to a particular node.
Counting the data items in a linked list.
Add the following method to your linkedList class:
To count the number of data items, we assign current to the node that the head is pointing to and set a counter to be zero. While we haven't reached the null pointer, we increase the counter by one and then get the next pointer. Finally, we return the value of counter to the main program.
Printing out the data items in a linked list
Add the following method to your linkedList class:
To printout the data items, we assign current to the node that the head is pointing to. While we haven't reached the null pointer, we print the data in the current node and then follow the pointer to the next node.
Searching for a data item in a linked list
Add the following code to your linkedList class:
To search for a data item, we start at the first node (as pointed to by the head). We continue looking until either we get to the null pointer (the end of the list) or we find the data item. If we find the data item, we return True. If the item isn't in the list, we return False.
Testing your linked list
Once you have added the above methods to your linkedList class, you can test them out by adding some extra code. For example:
Use a visualiser
If you are struggling to see what is happening, use a Python visualiser such as www.pythontutor.com to help you. Copy and paste the code into the visualiser and step through it, one line at a time.