As discussed in class, Java already provides an interface called List that defines all the methods that an array list should have, as well as an AbstractList abstract class that implements some of the basic functionality of the List interface (that could be shared by other types of lists that are not backed by an array). This is similar to how Lab 2 provided a Player interface that defined all the methods a player in the Go Fish game should have, and you created an AbstractPlayer abstract class that defined the shared functionality of different kinds of players.
You’ll be using generics for your implementation so that it can store any type of data as elements of your array list. To aid in this process, the List and AbstractList also support generics.
Full documentation of what an array list might include can be found in Java’s ArrayList documentation.
ReadMe
Terminology: To avoid confusion in the remainder of the lab, we are going to be talking often about two counts that are related but different from one another.
size, which refers to the number of items actually in the array list at the current time.length value of the underlying array.We should never have the case where size > length because we only have room for length items. But we will often have the case where size < length since the array list will not be full. Sometimes size == length, meaning that the array list is full and we need to resize the underlying array before we can add a new element.
Inside your GitHub repository, you will find a file called MyArrayList.java. Open this file in Visual Studio Code by either using the “File” > “Open” dialog box, or double click on the MyArrayList.java file on the left side of your IDE in the “Explorer” area. Within this file, you should create a new class called MyArrayList<T> that inherits from Java’s AbstractList<T>. Here, we include the prefix My in your class name so we can separate it from Java’s own ArrayList implementation. The <T> suffix tells Java that this class uses T as the generic reference to the type of object stored in MyArrayList.
The MyArrayList<T> class should have two private instance variables:
/** An array storing the items contained within the ArrayList. */
private T[] items;
/** The current number of items stored in the ArrayList. */
private int size;
We also want to include two constructors, using polymorphism to allow programmers multiple ways of creating new MyArrayList collections. The first constructor public MyArrayList (int startLength) should take as an argument the starting length of the underlying array.
Hint
Note: while any number could be passed in as a parameter for the startLength argument, we want to make sure that the length of the array is always a power of 2 to make sure our resizing works efficiently. So we will round up the startLength argument to the nearest power of 2 and use that as the initial length. (To do so, you can create a new variable length that starts with the value of 2 and keep doubling it with a while loop until it is no longer smaller than startLength).
The constructor should assign appropriate default values to the two instance variables: this.size should start with a value of 0 (since nothing is actually stored in the array list, yet), and this.items should start as an empty array of length startLength.
ReadMe
Unfortunately, Java does not allow us to directly create an array without knowing exactly its type. That means we cannot create a new array of T using new T[length] since T is a generic type that might change across different programs that use different array lists. Instead, since every type (no matter what we ultimately store in the array list) inherits from the fundamental type Object in Java, we can create an Object array and convert it to a T array using the code:
this.items = (T[]) new Object[length];
Since this is a complicated activity, the Visual Studio Code IDE will warn you that this might cause a problem if not done correctly (no worries – we are doing it correctly, but the IDE cannot tell the difference). The compiler will also give you a warning for the same reason. We can make those warnings go away by adding a special marker in the source code to suppress the warning. Write:
@SuppressWarnings("unchecked")
above the method header (i.e., outside the function body).
The second constructor public MyArrayList() should take no arguments, but instead it will make a default choice of size for the programmer. This constructor should start with a startLength of 2 since every array list should be able to store at least two items (else a collection isn’t needed in the first place). Rather than duplicating the code from your first constructor, your second can simply call the first and tell it to start with a startLength of 2 by containing only the line:
this(2);
The last thing we are going to do in this first part of the lab is fill in the public int size() method required of all List classes. This method should simply return the current size (not length) of your MyArrayList.
ReadMe
You probably noticed that we overloaded the meaning of the name size to be both an instance variable and a method. This is an example of polymorphism from Object-Oriented Programming at work and is not supported by all programming languages (e.g., Python would not allow this).
It is good practice to frequently test what you have implemented so far, instead of trying to implement an entire class before doing any debugging. Although we haven’t implemented a lot of our MyArrayList class yet, we can still do some testing before moving on.
ReadMe
However, there is one more thing we need to do before we can compile our MyArrayList.java file. Recall that we had our MyArrayList<T> class extend AbstractList<T>. There is one more abstract method in AbstractList that needs to be implemented in order to compile our class. For the purposes of testing our progress so far, we do not need to actually fill in this method; instead, we can simply include a stub that we will fill in later. To do so, add this to your code for now:
public T get(int index) {
// TODO: we will fill this in soon
return null;
}
which satisfies the requirements of the get method signature but doesn’t actually do anything for now.
We can test that our constructors and size method are working properly by:
Creating a public static void main(String[] args) method that:
MyArrayList<Integer> objects by calling both constructorsSystem.out.println to print out what is returned by calling the size method on both instances of MyArrayListAdd a System.out.println statement to your first constructor that prints the length of the items instance variable and make sure it is the nearest power of 2 (equal to or above) whatever you passed in as the startLength argument. This should be 2 when you call the second constructor that takes no argument. Note: you’ll want to delete this print statement after you know the constructor is working properly.
Don’t forget to frequently save your progress periodically to GitHub using the add, commit, and push commands with git.