1 Recursion and Linked Lists

"Traversal" refers to visiting every piece of data in a data structure. Here's linked list traversal with iteration:

1
2
3
4
5

def traverse(self):
    curnode = self.head
    while curnode is not None:
        # DO SOMETHING HERE
        curnode = curnode.nextNode

and here it is with recursion:

1
2
3
4
5
6
7
8
9
10
11

def traverse(self) :
    self._traverse(self.head)
 
# Helper method so no user has to know or care about nodes.
def _traverse(self, curnode):
    if curnode is None:
        # base case: nothing left to do
        return
    else:
        # DO SOMETHING HERE
        self._traverse(curnode.nextNode)

Make sure you understand how this works. Soon, there will be data structures where the iterative version is pages long, and the recursive version is five lines. You want to know and understand how this works.

In class, we wrote two other methods, one of which counted the number of 5's in a linked list:

1
2
3
4
5
6
7
8
9
10
11
12
13

def count_fives(self):
    return self._count_fives(self.head)
 
def _count_fives(self, curnode):
    if curnode is None:
        # base case, no more fives left
        return 0
    elif curnode.data == 5:
        # found a 5
        return 1 + self._count_fives(curnode.nextNode)
    else:
        # no 5 here, but we still count the rest
        return self._count_fives(curnode.nextNode)

The other method we wrote adds a 4 before the first 5 it comes to. For example, if we have a linked list holding the integers 1,3,5, then after running add_before_five(4), we would have a linked list with the integers 1,3,4,5.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def add_before_five(self, item):
    self.head = self._add_before_five(item, self.head)
 
def _add_before_five(self, item, curnode):
    if curnode is None:
        # guess there was no five to add before
        raise RuntimeError("No five to add before")
    elif curnode.data == 5:
        # insert a new node with this item, before curnode
        newnode = Node(item)
        newnode.nextNode = curnode
        return newnode
    else:
        # keep on looking for a five
        curnode.nextNode = self._add_before_five(item, curnode.nextNode)
        return curnode

Make some examples to try the above on, and understand why it works!

2 The Assignment

The work for lab is going to be very similar to Lab 2, except that you cannot use any loops to implement these methods. Pretty much all of your methods should be recursive except for the simple \(O(1)\) methods such as add_front.

Start with this starter code (download and save as linkedlist.py) and fill in all of the methods. Specifically, you need to write the following methods without using any loops:

• __init__: No different from Lab 2.
• add_front(item): No different from Lab 2.
• print_forward(): Print the list elements in order, one per line
• print_reverse(): Do the same, but the elements should print in reverse order.
• contains(needle): Search for the needle within the list.
• get(index): Return the list item at the given index.
• insert(index, item): Insert the item at the given index, without removing anything.
• add_ordered(item): Same as Lab 2, except now you have to get to use recursion.
• remove(index): Remove the item at the given index from the list
• size(): No explanation necessary I hope!

Test as you go.