Type: Individual Assignment

Due: by 9:30 PM on Tuesday, October 23, 2018

This assignment is worth 15 points. This is an individual assignment–you must turn in your own code for the assignment, and cannot turn in code that someone else has written. You may discuss ideas for the problems at a high level with classmates but cannot write code together.

Goals

The goal of this assignment is to get more practice with recursion. You will also get to cement your knowledge of linked lists and interfaces.

The Comparable Interface

The Comparable Interface is an interface in Java that allows for there to be a total ordering of the objects in each class that implements it. In particular, any class that implements the Comparable interface, must implement a compareTo method. Here is a description of how the compareTo method should work.

Method Return Type Description
compareTo(E obj) int This method will compare the object calling the method to the object passed as a parameter. Returns a negative integer, zero, or a positive integer if this object is less than, equal to, or greater than the given object.

A few examples of classes we have seen that implement the comparable interface are: String, Integer, and Double. Consider the following snippet of code:

Integer one = new Integer(1);
Integer two = new Integer(2);
int comp = one.compareTo(two);
System.out.println(comp);

This would print a negative number (-1) since 1 is less than 2. Similarly, consider the following snippet of code:

String one = "one";
String two = "two"
int comp = two.compareTo(one);
System.out.println(comp);

This will print a positive number (5) since “two” comes later alphabetically (hence is greater) than “one”.

Starter Code

I’ve provided you with a class called RecursiveLinkedList.java that implements the List ADT using a LinkedList structure. This code only works with items that implement that Comparable interface. You should spend some time just looking through this code. In addition to public methods, there are a number of private helper methods included. Take note of how these helper methods can make some of the code for other methods (e.g. public E remove(int index)) much cleaner and easier to understand. Much of this code is taken straight from your textbook, but it’s nice to see it all in once place.

Your Task

Your task with this assignment will be to write the code to add the following three methods to this class. To receive full credit, you must implement each of these methods using recursion and your implementation of each must run in O(n) time, where n is the number of elements in the list.

/**
 * Return the maximum element in the list using
 * compareTo() method of Comparable.
 *
 * @return maximum element of the list
 **/
public E max()
{
    // YOUR CODE WILL GO HERE
    // You will likely want to use a helper method
    return null;
}

/**
 * Remove all elements that match element using the 
 * equals() operator to determine a match. 
 * (Don't use ==).
 *
 * @param element The element that should be removed
 **/
public void removeAll(E element)
{
    // YOUR CODE WILL GO HERE
    // You will likely want to use a helper method
}

/**
 * Duplicate each element of the list
 *
 * For example, the list [ 0 1 2 ] duplicated becomes 
 * [ 0 0 1 1 2 2 ]
 **/
public void duplicate()
{
    // YOUR CODE WILL GO HERE
    // You will likely want to use a helper method!
}

You should also be sure to include a main() method that tests out the methods you have written. Be sure to consider difficult cases!

Hints

  • I suggest you take my suggestion about using a helper method seriously. The key thing here will be to think about how to define the signature of that method.
  • You will likely want to define helper methods that either take a Node object as a parameter or return a Node object. If you do this, you should make sure that your method declaration (the first line that says what you return and the parameter types) always uses Node<E>. For example, you might define the following method that returns a Node and takes in a Node as a parameter:
public Node helperFunction(Node aNode)
  • It’s totally fine if all the recursion is done in your helper methods, rather than the specific methods I am asking you to implement.

Submission and Grading

Submit your modified version of RecursiveLinkedList.java and place it in the assignment6 directory on the courses drive. This assignment is worth 15 points. Each of the three functions you will implement is worth 4 points. To get the full points, it needs to be implemented recursively (no loops!) and it needs to run in O(n). The more elegant your code, the better. Your code will also be evaluated for general style guideline (are you using good variable names, using proper indentation, etc). This will be worth 2 points. Finally, implementing a main() method that properly tests your methods will be worth 1 point.

Start early, ask lots of questions, and have fun! The instructor, the course staff, and the prefect are all here to help you succeed - don’t hesitate to ask for help if you’re struggling!