Homework 4: My Linked List

Due October 22 25 @ 8:00pm on Autolab

• 1. Introduction
• 2. The New Methods
• 3. Note on Efficiency
• 4. Bonus Method
• 5. Grading and Submission
  • 5.1. Testcases
  • 5.2. Style
  • 5.3. How to Submit
• 6. Restrictions
• 7. Important Notes

1. Introduction

In this assignment, you’ll be adding more methods to the MyLinkedList class we developed in class. When you’re done, you’ll have a pretty good start on a fully-fledged generic linked list class!

Download a pre-prepared Eclipse Project hw4.zip and import it into Eclipse using these instructions. You will make all of your changes inside of the Java files in this project.

2. The New Methods

The new methods you need to write are as follows:

• DataType remove(int index)
  This method removes the node at the position in the list specified by index, if such a position is in the list and returns the data value that was at that location. Throws the appropriate exception if index is out of range.

• DataType set(int index, DataType newValue)
  This method replaces the data in the node at position index with newValue, if such a position is in the list and returns the previous (old) value that was at that location. Throws the appropriate exception if index is out of range.

• int lastIndexOf(DataType value)
  Returns the index of the node that contains the last occurrence of target in the list. Consistent with Java indexing, the first node is at position 0. Returns -1 if target is not in the list.

• void add(int index, DataType value)
  This method adds a node containing value at the position in the list specified by index, if such a position is in the list. Throws the appropriate exception if index is out of range.

• void add(ArrayList<DataType> arr)
  This method adds all the elements in the ArrayList arr to the end of the list, e.g., if the list contained “Susie”, “Fred”, “Mark” and arr contained “Roly”, “Joe”, after executing this method, the list should now contain “Susie”, “Fred”, “Mark”, “Roly”, “Joe”.
  This method must run in _linear_ time or you will lose points!

• boolean removeLastOccurrence(DataType target)
  This method removes the node containing the last occurrence of the value target in the list. Returns true if the list contained the target; false otherwise.

• void removeAll(DataType value)
  This method removes every node that contains target in the list. Realize that the target can occur multiple times and anywhere in the list! This method does nothing if target is not in the list.
  This method must run in _linear_ time or you will lose points!

• MyLinkedList<DataType> clone()
  Returns a new list that is a (shallow) copy of this list. A shallow copy means that you create a new MyLinkedList containing new ListNodes that contain the same data as the original list.
  This method must run in _linear_ time or you will lose points!

3. Note on Efficiency

Three of the methods listed above have efficiency requirements. The Autograder will test the efficiency of those methods in order to ensure your implementation is \(O(N)\).

To test your complexity, we time how long the method takes to run on a list with 200,000 elements. Next, we time and run it again with a list twice the size. We then divide the two times to get your speed ratio. If your method is \(O(N)\) then your speed ratio should be \(\approx 2\). (Because if we double the input, the time to run should double as well.) If your speed ratio is 3 or less, the Autograder will accept your efficiency.

This method of determining your speed ratio is not an exact science, and your speed ratio will vary a little bit between two runs, even if your code hasn’t changed. If you fail the testcase with a speed ratio close to 3 (such as 3.2), consider resubmitting so that Autolab will try again. It might be below 3 the next time. (If your ratio is much higher than 3, or the testcase times out, then you’ll need to rework your implementation.)

If you code is much slower than \(O(N)\), such as \(O(N^2)\), then the time to complete an operation on a 200,000 item list will be very high. As such, the testcase will simply timeout after 10 seconds and you’ll see a message indicating that a timeout occurred. This means your solution is not efficienct enough.

4. Bonus Method

This assignment includes one bonus method worth up-to three points. It will be manually graded.

void reverseInPlace()
This recursive method modifies the contents of the original list. It does not add new values to the list, but it does change their position. The first value should become the last one; the second value becomes the next to the last one, etc. until the last value in the original list becomes the first one in the modified list. It does nothing if the list is empty. You cannot create any new nodes when writing this method, nor modify any data fields of existing nodes (but you can declare as many local variables as you want that store references to nodes); you can only manipulate references to nodes.

This will be manually graded, meaning Autolab will not provide you feedback about this method. In addition, we did not include a placeholder for it in the skeleton code. You need to properly place it, name it, etc. In order to receive the bonus points:

1. Your solution must be substantially recursive.
2. You must include a testcase for it.

5. Grading and Submission

There are four parts to the grading of this assignment:

1. 70 points will be auto-graded on Autolab.
2. 10 points will be graded based on your adherence to the style guide.
3. 10 points will be graded based on our manual assessment of the quality, efficiency, and readability of your implementation.
4. 10 points will be graded based on your testcases.

5.1. Testcases

In this homework we are not providing any testcases for the new methods. We do, however, provide some basic testcases for the methods written in class.

You need to write at least two testcases for each of the new methods listed above. (This is a total of 16 test cases you write.) One of those testcases should test basic functionality, and the other should test an error condition of some sort. All of your testcases should be in the MyLinkedListTester class included with the skeleton code. You must follow the model of our testcases (meaning you print when you start, print when you finish, etc.) Additionally, you must comment each testcase with a note describing what it tests.

5.2. Style

In this homework you will be strictly graded according to the style guide. A style checker has been incorporated with Autolab and will assign these style points automatically. You can see your style score and feedback as part of the Autolab output.

5.3. How to Submit

You will submit your program to Autolab. Login to the system and you will see the homework.

You’ll need to submit a zip file containing your code. Lucky for you, however, Eclipse can create this zip file for you. Check out these instructions. On Autolab, you’ll submit that exported zip file. On the page that follows your submission you will see your live score. It may take up to a few minutes for your score to appear; during that time just hit refresh in your browser. If you receive a lower score than you expect, you can click on the score to see the feedback from the autograder.

6. Restrictions

You may only use the following Java libraries in this assignment:

java.util.ArrayList

7. Important Notes

• If you have questions, please post to Piazza. The course staff, including the instructor, monitor and answer questions there.
• When posting to Piazza, if you include any code make sure your question is posted privately to the instructors, and not to the entire class.
• Do not change the names of any of the provided methods or files.
• After you submit to Autolab, make sure you check your score. If you aren’t sure how to do this, then ask.
• There is no partial credit on Autolab testcases. Your Autolab score is your Autolab score.
• Read the last bullet point again. Seriously, we won’t go back later and increase your Autolab score for any reason. Even if you worked really hard and it was only a minor error…
• You can submit to Autolab multiple times. So, after you submit you should check your score. If you lose points you can keep working and resubmit.