Recursive List MINI-LAB

---

In this lab, you will complete the methods for a class that implements a list using a recursive data structure and recursive methods to navigate the list.

Defining a Recursive List

A recursive definition of a list is that it is either:

• An empty list; or
• A list element followed by a list (the "rest of the list").

A recursive list is similar to a linked list, in that it consists of linked nodes, but without the outer "shell" of a list class. Each node in a recursive list is considered the head of a new list composed of the data, or element in the node, and a link to a sub-list that makes up the rest of the list.

In this lab, you will complete a K_RecList class that provides the same methods as the K_SimpleLL class, but implemented differently. The test driver will also be similar, but dealing with K_RecList objects rather than K_SimpleLL objects.

Understanding K_RecList

• Download and read over the K_RecList class. Without looking at the bodies of the methods, just looking at the instance variables and the method signatures, how does it compare to K_SimpleLL and K_LLNode?
• Read over the methods that have been provided for you to see how they navigate the list structure to add new elements and get elements from the list. In particular, the get method provides an example of how to navigate through a recursive list. With recursive functions, it is important to check for the base case(s) first, before getting into a potentially infinite recursion. The get method has two base cases.
  • Is the current list (which might be either the starting list or a tail sublist) an empty list? That takes special handling.
  • If not, does it have the element we're looking for? If so, that takes specific handling.
  • If neither base case is true, we recurse through the list.
• Make a copy of the K_SimpleLLTester test driver, calling it K_RecListTester.java. Edit it to create and use K_RecList objects rather than objects to add to a linked list. Don't forget to change the name of the class as well, since the class name and filename must agree.
• Test the provided version of the code. Does it behave as you expected? Why or why not?

Implementation

• Complete the incomplete addLast and set methods. The set method is structurally very similar to the get method. The addLast method is simpler as it has only 1 base case, an empty list. Test each method as you complete it.

• Complete and test the remove method in K_RecList class.

  How: You could recurse until you get to the node BEFORE the node you want to remove, as you did for K_SimpleLL, but there is another approach that is simpler to implement. For this method, recurse to the node whose element should be removed and "remove" it by copying the contents of the next node into it. The node that used to be the next node will eventually get garbage-collected. Since you're changing the node that held the removed element rather than the node before the removed element, you don't have to treat removing the first node as a special case.

  This approach is structurally similar to get and set methods, although the handling when you find the element you're looking for is different.

• Go through K_SimpleLL and determine what other methods are missing. Implement and test them.

Clean and Refactor

Follow this link to clean and refactor your comments and code.

Submission

Submit your completed program through Kit, under Recursive List Mini-Lab.

Have fun! And if you have any questions remember my email, my office hours, and the Collaboration Center are here for you!