CS 206 - Introduction to Data Structures

Homework 6

A recursive-only linked list implementation

Due Friday, March 26 prior to 4:59PM

(note time and date)

This assignment has two parts:
  1. Adapt a linked list implementation to use only recursion.
  2. Write a set of tests that show that the recursive implementation does exactly the same thing as the provided iterative implementation. This set of tests should be contained within -- or at least called from -- a main method.

The code to be adapted is available at:
It is also available here

The tests should be modelled on the tests for stack and queue that were discussed in class. You will certainly need more tests than in those examples, if only because there are more public methods. Generally, every public method should have sufficient tests to demonstate that it works correctly. For some methods a single test case will suffice. For other methods, you might need many more test cases. For example, consider addFirst. You will at least need a test case to handle each of the return points from this function (i.e., if the linked list is empty and if the linked list is not empty). (Background: There are programmers whose entire job is to come up with a set of cases that are sufficient to verify that things work correctly. There is a whole software development approach called test-driven design that starts by defining (and writing) test cases along with the correct output. Then software is developed to satisfy those cases.)

As to the other part of the assignment, for most of the methods which use iteration, replacing that iteration with recursion will require a private recursive method. In some cases, that recursive method will naturally be over the entire iterative method. In other cases, you should consider writing a recursive method that only does the small, iterative part of the original method. Hint: you can find all of the iteration that needs to be replaced by searching for for and while.

Electronic Submissions

Your program will be graded based on how it runs on the department’s Linux server, not how it runs on your computer. DO NOT INCLUDE:
Data files that are read from the class site.

The following steps for submission assume you created a folder named AssignmentN in the directory /home/YOU/cs206/ and that folder contains all of your code.

  1. For this assignment N=6
  2. Put the README file into the project directory (/home/YOU/cs206/AssignmentN)
  3. Go to the directory /home/YOU/cs206
  4. Enter submit -c 206 -p N -d AssignmentN

For more on using the submit script click here