HW11 Part 3: Your Own List Implementation

This is the final part of HW11.

  1. Create a new file ArrayListImplementation.java, and create a class ArrayListImplementation inside it, implementing the List interface. The first few lines of your file should be as follows:

    import java.util.Iterator;
/** 
* An array-based implementation of the List ADT.
* 
* @param <T> The type of data that the list stores.
* 
* @author YOUR_NAME_HERE
*/
public class ArrayListImplementation<T> implements List<T> {

    Note that you need to import the Iterator interface even if you're not planning on implementing the method iterator(), because you still need to write this method's signature, which uses the Iterator type.

  2. Copy over, from List.java, the signatures for all the methods that you'll have to implement. Give each one an empty body, and for those methods that have a return value, return some dummy value (like always returning false from a method that returns boolean, or returning null from things that return reference types).

    Also create a public default constructor for your class, but just leave the method body blank.

    If you're not planning to implement the iterator() method, just put this in as its body:

    throw new UnsupportedOperationException();

    At this point, your code should compile, even though it doesn't actually do anything.

  3. Change your code in ListTest.java to use your implementation class instead of the mystery implementation. It should compile and run, but either crash quickly or fail most tests.

  4. Now go through and implement each method one-by-one. After you implement each method, you should be able to compile your code and re-run your test code. Make sure that your methods implement the behaviors described in the interface. This means not just that your methods must have the correct signatures, but also that their behavior must be correctly described by the comments in the interface. The comments in the interface are part of the (unenforced) contract between you and the user of your implementation. Remember that your user needs to be able to think of their list just as a List, not as your particular implementation type.

    You may find it helpful to define the following private helper methods:

    • boolean indexOutOfBounds()
    • void ensureCapacity()

    I recommend implementing the methods in this order:

    1. Constructor
    2. add() (just the one-argument version)
    3. at() and replace()
    4. length(), clear(), and isEmpty()
    5. toArray()
    6. The two-argument version of add()
    7. remove()
  5. If you'd like to implement iterator(), check out these notes on implementing the Iterable interface.

The magical incantation for creating generic-type arrays

If your class uses the keyword T to represent the generic type that your structure stores, and you want to create an array of length n that can store T objects, here's how you do it:

// ... other code goes here ...
@SuppressWarnings("unchecked")
  T[] arr = (T[]) new Object[n];
// ... more code here ...

If you want to allocate this array and store it in a variable whose name has already been declared (like, say, a data member of your class), then you still have to declare and initialize a separate variable, as above — I would call it tmp in this case:

// ... a_big_t_array is already declared as T[] ...
@SuppressWarnings("unchecked")
  T[] tmp = (T[]) new Object[n];
a_big_t_array = tmp;
// ... more code here ...

The reason this is necessary is related to the reason why toArray() can't return an array of Ts — it's a consequence of the way that generics are implemented under the hood in the Java virtual machine. I wish this weren't necessary, but it is.

I recommend following the same style as above: the @SuppressWarnings("unchecked") should go on its own line, at the same indentation level as the surrounding lines of code. The actual declaration and initialization of the array should go on the next line, indented by two spaces.