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
def print_list(node): if node is None: return print(node.data) print_list(node.next)
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
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
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
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.