I am trying to figure out how I can traverse linked list in Python using Recursion.
I know how to traverse linked-lists using common loops such as:
item_cur = my_linked_list.first
while item_cur is not None:
print(item_cur.item)
item_cur = item_cur.next
I was wondering how I could turn this loop into a recursive step.
Thanks
You could do something like this:
def print_linked_list(item):
# base case
if item == None:
return
# lets print the current node
print(item.item)
# print the next nodes
print_linked_list(item.next)
Try this.
class Node:
def __init__(self,val,nxt):
self.val = val
self.nxt = nxt
def reverse(node):
if not node.nxt:
print node.val
return
reverse(node.nxt)
print node.val
n0 = Node(4,None)
n1 = Node(3,n0)
n2 = Node(2,n1)
n3 = Node(1,n2)
reverse(n3)
It looks like your linked list has two kinds of parts. You have list nodes, with next and item attributes, and a wrapper object which has an attribute pointing to a the first node. To recursively print the list, you'll want to have two functions, one to handle the wrapper and a helper function to do the recursive processing of the nodes.
def print_list(linked_list): # Non-recursive outer function. You might want
_print_list_helper(linked_list.first) # to update it to handle empty lists nicely!
def _print_list_helper(node): # Recursive helper function, gets passed a
if node is not None: # "node", rather than the list wrapper object.
print(node.item)
_print_list_helper(node.next) # Base case, when None is passed, does nothing
print the restneeds to print a linked list. But you've just written a function that knows how to print a linked list. So call that instead ofprint