# IC312: Data Structures (FA16)

Home Policy Calendar Units Assignments Resources

# HW 3: Recursive Linked List

## Solution

You can find the solution here

## Overview

In this homework, you are will write programs using recursion over linked lists. The goal is to familiarize yourself with recursion, which will become ever more important in later data structures.

### Due Date

This homework is due Wednesday, September 7th at 2359

This assignment is graded out of 100 points.

• 80 points: 20 points each for `max()`, `duplicate()`, `remove()`, and `toStringReverse()`
• 20 points : proper recursive implementations

### Submission and Starter Code

All starter code for this homework can be obtained via the `~aviv/bin/ic312-up` and submission will occur via `~aviv/bin/ic312-submit`.

You must submit the following file(s):

• `LinkedList.java`
• `README` : containing any attribution or notes for grading.
• Any testing files you'd like us to look at and consider during grading.

## Description

In this assignment, you will be provided with a basic `LinkedList` implementation of the `List` interface we used in HW 1. You get all that code for free, and you should review it because it can be a guide for completing this assignment. One item of note is that the generic types for our `LinkedList` requires that the type stored implements the `Comparable` interface.

```import ic312.List;

// This fancy generic says that the LinkedList must store elelents whose
// type T is comparable to other elements at type T
//                              |
//                       .______|____________.
//                      /                     \
public class LinkedList<T extends Comparable<T> > implements List<T>{
//...
}
```

If you are unfamiliar with the `Comparable` interface, read the documentation online.

Your task for this homework is to complete the following additional methods, and you must do so using recursion.

```/**
* Return the maximum element in the list using compareTo() method
* of Comparable
*
* @return maximum element of the list
**/
public T max(){
//TODO: complete this method recursively (maybe need a helper?)
return null;
}

/**
* Remove all elements that match e using the equal() operator
* to determine a match
*
* @param e The element that should be removed
**/
public void remove(T e){
//TODO: complete this method recursively (maybe need a helper?)
return;
}

/**
* Duplicate each element of the list
*
* For example, the list [ 0 1 2 ] duplicated becomes [ 0 0 1 1 2 2 ]
**/
public void duplicate(){
//TODO: complete this method recursively (maybe need a helper?)
return;
}

/**
* Return a string representation of the list with elements in revese order.
*
* For example, for a list l of strings with the follwing sequence of operations
*
*
* toString() ->  "[ a b ]"
* toStringReverse() - >  "[ b a ]"
*
* @return the string representation of the items in reverse
**/
public String toStringReverse(){
//TODO: complete this method recursively (maybe need a helper?)
return "";
}
```

If you're not comfortable with recursion, do not sit on this assignment. Get started right away so you can ask questions.

To help you're testing and development, the `LinkedList` file contains a `main()` method with some simple tests. Note that I will test your program on many, many, many more tests then these, so feel free to expand these tests well beyond the ones I provided. For example, perhaps using `Integer` objects could help with testing some things?