Homework 3

due: Thursday March 6 at 11:59pm (submit on Gradescope here).

Goals:

Implement your own version of an ArrayList.
Consult Oracle's documentation of an ArrayList.

In this assignment, you will implement your own version of an ArrayList, so please review the notes from Lecture 3W for the concepts we used to design a DIYList.

Instead of parametrizing our version of an ArrayList in terms of any type of stored item, we'll only store Strings. So we will call this class DIYArrayListString and we will not use generics in this assignment.

The initial template is quite minimal (download here) and only sets up the DIYArrayListString with the items and size fields, as well as the capacity() method. Your job is to implement the methods listed below which should match the descriptions in the official ArrayList documentation. You don't need to implement all the methods defined for an official ArrayList, just the ones listed below.

Although the capacity() method is not specified in the official ArrayList documentation, we're adding it to our version since it may be useful for testing (and the Gradescope tests will also check the capacity).

Also, the official ArrayList implementation is supposed to throw exceptions if an index is out of bounds. We haven't talked about exceptions so you don't need to check the bounds of the indices passed to certain methods. The Gradescope tests will always pass valid indices (0 <= index < size()).

Here are the methods you need to implement. The description you need to follow is linked in each method name below.

public DIYArrayListString(): This is the default constructor with no parameters. The initial capacity should be set to 2 in our version, as we did in class, even though the documentation says the default initial capacity should be 10.
public DIYArrayListString(int initialCapacity). Constructs a DIYArrayListString and allocates initialCapacity slots as the initial capacity.
public boolean add(String item): Note that this method always returns true. Remember to check if you need more space. As we did in class, when you need more space, double the capacity. You might want to first write the ensureCapacity method (below) and then come back to the add method.
public void clear(): No need to null-ify all the items - the Gradescope checks will only check the size() after a call to clear().
public void ensureCapacity(int minCapacity): Creates an array with minCapacity slots. Copies items from the previous items array into the new one. Assume minCapacity is always greater than the current capacity.
public String get(int index): Assume the index is valid, i.e. 0 <= index < size().
public int indexOf(String item): Make sure to treat the case when item is not in the list. This should return the index of the first occurrence of item in the list.
public boolean isEmpty(): Determines whether there are any items stored in the list.
public String remove(int index): No need to update the capacity after removing.
public String set(int index, String element): Note that this method also returns whatever was previously stored at index.
public int size(): Returns the number of items.
public void trimToSize(): Reduces the capacity to be equal to the current size.

Please test your methods within a public static void main method of your DIYArrayListString class - don't rely on Gradescope to test your code. You should call some of your DIYArrayListString methods within this PSVM to make sure everything is working. For example,

DIYArrayListString list = new DIYArrayListString();
System.out.println(list.size());
System.out.println(list.capacity());

list.add("apple");
System.out.println(list.size());
System.out.println(list.capacity());

// ... and so on ...

The Gradescope tests will look for a PSVM in your DIYArrayListString class.

Submission

You only need to submit DIYArrayListString.java to Gradescope (here) (unlimited attempts). The grading team will now check the style of your submission, so please review the notes from this lecture (slide 3). Style will be worth 1 point (out of 20) for this homework. Note that (in VS Code), you can right-click on your source code and select Format Document.

You should also add documentation to your methods (which will be included in the 1 point given for style). To create a javadoc documentation comment, type /** right above one of your methods and then hit the Enter (or return) key. VS Code should autofill a javadoc-style documentation as in the animation below:

The documentation you add for each method should include three main components: (1) a short sentence describing what the function does, (2) a brief description of each parameter using @param and (3) what the method returns using @return. When describing each @param, it's also good practice to describe any limitations on the parameters.