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
print(node.data)
print_list(node.next)
``````

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
print_list_reverse(node.next)
print(node.data)
``````

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):
prev = None

while curr is not None:
next = curr.next
curr.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 `curr.next` currently references. However, because we are reversing the list, we overwrite the value of `curr.next` 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 = curr.next
curr.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 `curr.next` 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.