6.2 Traversing Linked Lists#

The final example in the previous section ended with the sequence of expressions linky._first.item, linky._first.next.item, and linky._first.next.next.item to access the linked list’s first, second, and third elements, respectively. This is, of course, a very cumbersome way of accessing list elements! In this section, we’ll study how to traverse a linked list: that is, how to write code that visits each element of a linked list one at a time, regardless of how long that linked list actually is. The basic structure of this code is quite general, so we will apply it to a bunch of different methods. This may seem repetitive, but linked list code is one of the most technically challenging and important parts of the course, so spend the time to master it!

Before we write code to traverse a linked list, let’s remember how traversal might look for a built-in list, manually using an index variable i to keep track of where we are in the list.[1]

i = 0
while i < len(my_list):
    ... do something with my_list[i] ...
    i = i + 1

This code segment consists of four parts:

  1. Initialize the index variable i (0 refers to the start of the list).

  2. Check if we’ve reached the end of the list.

  3. Do something with the current element my_list[i].

  4. Increment the index.

This method takes advantage of the fact that Python already gives us a way to access elements of a built-in list by index (using square brackets). In a linked list, we don’t have this luxury, and so the major difference to this pattern is that we now keep a variable that refers to which _Node object we’re on in the loop. Traversing a linked list consists of the exact same steps, except that the temporary variable now refers to a particular _Node object rather than an index. Other than this change, the steps are exactly the same!

curr = my_linked_list._first   # 1. Initialize curr to the start of the list
while curr is not None:        # 2. curr is None if we've reached the end of the list.
    ... curr.item ...          # 3. Do something with the current *element* curr.item.
    curr = curr.next           # 4. "Increment" curr, setting it to refer to the next node.

For example, here is a LinkedList method that prints out every item in a linked list.

class LinkedList:
    def print_items(self) -> None:
        """Print out each item in this linked list."""
        curr = self._first
        while curr is not None:
            print(curr.item)      # Note: this is the only line we needed to fill in!
            curr = curr.next

And here is a LinkedList method that’s a bit more complicated but uses the same traversal template. The goal of this method is to convert a linked list into a built-in Python list, in a non-mutating fashion (i.e., by returning a Python list without changing the original list).

    def to_list(self) -> list:
        """Return a (built-in) list that contains the same elements as this list.
        """
        items = []
        curr = self._first
        while curr is not None:
            items.append(curr.item)
            curr = curr.next

        return items

Our philosophy for “code templates”#

You might be surprised about our presentation of a code template for traversing a linked list. After all, aren’t templates bad—we shouldn’t just copy-and-paste code, right?

But in fact, over the next few weeks of the course, we’ll encourage you to use certain code templates to help get started writing and organizing your code. The difference between these code templates and just regular copy-and-pasting of code is that these templates are meant only to provide an overall code structure, and not replace the hard work of actually thinking about how to write code. In other words, we use templates to make it easier to get started writing code.

Consider again our template for iterating through a linked list:

curr = my_linked_list._first
while curr is not None:
    ... curr.item ...
    curr = curr.next

Whenever you’re starting to write code to iterate through a linked list, your first step should be to copy-and-paste this template into your code. But that’s the easy part; the next part involves the thinking required to fill in the ellipsis (...) and modify the template to suit your particular needs. In the following weeks of this course, you’ll get lots of practice with that. 😀