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:
- a data value
- 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):
curr = 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.