Traversing a Linked List

So far, we have written algorithms to build linked lists, which have only operated at the beginning or the end of a linked list. However, many algorithms require us to iterate over (or traverse) an entire sequential data structure. So how is that done with linked lists?

Printing an LLString

For a first example of traversing a list, let's see how we could use iteration to print an LLString:

As shown in the video, this method of traversing a list is a common programming pattern. Here's a template that you can use:

    def traversal(self):
        trav = self.head
        while trav is not None:
            # ... do something here
            trav = trav.next

Recursively printing an LLString

Linked lists are a naturally recursive data structure, since each linked list is either:

  • Empty
  • A single node, followed by a linked list

For this reason, it is often easier to write recursive functions to operate on linked lists. For example, watch the following video to see how to recursively print a linked list:

Finding the length of a list

Your turn: either iteratively or recursively, write a method length() that returns the length of the linked list. If the list is empty, the function should return 0.


Click to reveal the answer.

Here's the iterative version:

def length(self):
    trav = self.head
    count = 0
    while trav is not None:
        count += 1
        trav = trav.next
    return count

And here's the recursive version:

def length(self):
    return self.__length(self.head)

def __length(self, node):
    if node is None:
        return 0
    else:
        return 1 + self.__length(node.next)