1 Overview

For this HW, you will implement the same List interface as in HW01, but using a linked list and recursion instead of an array and loops.

You will also implement a few extra functions in your LinkedList class, as detailed below.

Again, we emphasize that none of your code for this HW should use loops. It’s perfectly fine in practice to use a for or while loop to do things with linked lists, but the purpose of this assignment (in part) is to get you comfortable writing recursive methods with nodes. That skill will be crucial in a week or so when we get to trees. So you will receive zero credit for any method you implement using loops.

2 Starter code

• List.java
• LinkedList.java

You can get all these files at once by downloading the file hw03.tar.gz and running tar xzvf hw03.tar.gz

The List.java interface is the same as your previous HW, and LinkedList.java is the implementation you need to fill in. Besides all the methods in the List interface, you also need 2 more:

/** Removes ALL elements matching the given one using .equals().
 *
 * @param element The element that should be removed
 */
public void removeAll(T element);

/** Gets the 2nd-to-last element.
 *
 * @return The data in the second-to-last node in the list (if any)
 * @throws NoSuchElementException if the list size is less than 2
 */
public T penultimate() throws NoSuchElementException;

3 What you need to do

First you will want to make a Node class, which should be a private inner class inside LinkedList. As usual, each node should store a single element’s data and a pointer to the next Node.

Remember that all methods must be implemented using recursion rather than loops. Of course, some methods may not require a loop or recursion, and that’s okay too. But any of your O(n)-time methods should be recursive.

Typically what that means is you will create a recursive helper method that takes a Node cur argument or something like that, and then the public method you are implementing just calls the helper method once.

4 Testing

As usual, you are expected to thoroughly test your own code before submitting. Thinking about testing and edge cases is an important part of this course!

When you submit, you should see your pass/fail results for about 5 test cases. But remember, each of these is actually a JUnit test program that contains lots of small tests. So look at the output for each failing test to get some hints about what exactly has gone wrong.

For this assignment, we are hiding the actual JUnit test files from you (except for a few Sanity tests), but not the output and test results. So you might be able to see, for example, that your code doesn’t pass a test called removeMiddle() from TestNormalUse.java, but we aren’t showing you the details of the TestNormalUse.java program itself until after the deadline. We hope this gives you a hint of what to work on, without totally absolving you of the need to test and debug your own code independently. If you are having any trouble, please don’t hesitate to ask your instructor or MGSP for help!

5 Bonus: Iterable

As with the previous coding HW, you will get +5% on this assignment if your LinkedList class successfully implements Iterable<T>.

If you get this working, you should be able to loop through the elements in your list with a for-each loop like this. Cool!

LinkedList<String> lst = new LinkedList<>();
// put some stuff in your lst ...
for (String s : lst) {
  System.out.println(s);
}