For the past week at RC I have been doing some more work with linked lists. Linked lists as a concept are simple enough; it consists of a collection of nodes that have two attributes:

  1. a data value
  2. a reference to the next node in the list

I came across some other ways to manipulate linked lists and I thought I would share some insights, specifically about recursively and iteratively traversing and reversing the lists.

Let’s start with something simple - printing the list recursively. Why? based on where the print excecution occurs in relation to the next recursive call, the list can be printed in order or reverse order. Walking through the stack traces for the following two code examples makes this point. Let’s start with printing the list in order:

def print_list(node):
    if node is None: return

Calling print(..) before the recursive recurse_print(..) call means the order of the linked list is preserved when printing to the console.

However, simply swapping print(..) and the recursive call prints the list in reverse:

def print_list_reverse(node):
    if node is None: return

Why is this? print(..) is not going to execute until the recursive print_list_reverse(..)finishes executing. In other words, the current stack frame needs to pop off the stack before previous recursive call’s print execution can execute.

Moving forward, let’s look at reversing a linked list iteratively:

def iter_reverse(head):
    curr = head
    prev = None

    while curr is not None:
        next = = prev
        prev = curr
        curr = next

    return prev

The purpose of the while-loop above is to iterate over the nodes in the linked list until it reaches a None node. next keeps a reference to the node to the right of the current node, which currently references. However, because we are reversing the list, we overwrite the value of with the previous node (prev). The last line in the while-loop simply updates curr to the stored next value to keep iterating.

def rec_reverse(curr, prev):
    if curr is None: return prev
    next = = prev
    return rec_reverse(next, curr)

Above is the recursive reverse version. The base case occurs when curr is None and returns the prev value. Otherwise next keeps a reference to the current node’s reference to its right-most node. We then overwrite with the previous value because again, we are reversing the list.

It’s important to note we are returning the recursive calls; it’s important mainly for the the initial call to the function. When the first rec_reverse call is taken off the call stack, we need save the updated, reversed list to a variable for use. The other returns don’t really matter in this sense because they are upward in the rec_reserve’s call stack and not used within the function itself.