Overview / Logistics

The purpose of this lab is to give you practice designing collections. Click here to download the Netbeans starter code for this lab. When you are finished, please upload the file MyArrayList.java to canvas.

Learning Objectives

• Manipulate public and private variables/methods in classes to accomplish information hiding
• Use multiple methods together in concert, including overloaded methods
• Use multiple classes together in concert to accomplish a task
• Gain experience using information hiding and object references to implement a user-friendly collection class.

Background

The ArrayList container class in the java.util package provides a more flexible alternative to the additional array. We can still access elements at particular indices in constant time, but it is much easier to grow the data structure. For instance, if we wanted to add an element to the end of a regular array, we would have to make an entirely new array, copy everything over that was in there before, and then finally put in the new element:

By contrast, if we have an ArrayList, all we have to do is say

The ArrayList has a number of other utilities that make it a much better choice than a regular array for dynamic lists that change their size throughout the program's execution. For instance, one can insert objects within the middle of an array without having to manually move everything after that to the right (like you did in the drill for a regular array), and one can similarly delete elements in the middle without having to move everything after that over to the left. For instance, consider the following code

This will output the following (make sure you understand why as you trace through the code)

You will be implementing some of these utilities in this lab in our own version of a vanilla ArrayList, called MyArrayList.

Flexible resizing algorithm

Behind the scenes, and ArrayList actually has an array of generic items, which we call the "underlying array." This private array is resized and maintained to accommodate the elements that are added to /removed from it.

One possible implementation of an ArrayList is to create a new array every time an element is added to the end, but this is very inefficient. A better strategy is actually to keep an array that's longer than we need, and only to resize it when we run out of room. When it runs out of room, we can double its size. This ensures that the average "time complexity" (amount of time it takes per task) of adding an element to the end of the list is still a constant number of steps on average. Or in more CS language, we have a "constant amortized cost for an add operation." For example, let's say we start with an underlying array of size 10 and we add 100 elements to it. We have to resize at the following places:

• At 10, copying over 10 elements
• At 20, copying over 20 elements
• At 40, copying over 40 elements
• At 80, copying over 80 elements

Otherwise, it's a simple assignment to an array index which takes constant time. So the total number of steps is (100 + 10 + 20 + 40 + 80), or an average of 2.875 operations per add task (and this will never be more than 3 with the doubling scheme).

By the same token, if a lot of items are removed, it's wasteful to keep too large of an array in memory. So if the list is holding fewer than half the capacity of the underlying array after you remove an element, then you should halve the underlying array.

Bearing this in mind, below are the private variables of the MyArrayList class

There are actually two member variables per object: one for the underlying array, and another for storing how many elements have actually been added to it (since the underlying array is usually larger than the number of elements in the ArrayList). By default, the underlying array starts off with a capacity of DEFAULT_CAPCITY, but it is possible to initialize it with an overloaded constructor where this initial capacity is a parameter:

Programming Tasks

Your job will be to fill in methods to add and remove items from the data structure, while maintaining the underlying array. You should not use any methods from the built-in Java ArrayList class. Rather, you will be making your own implementation from scratch that has the same performance characteristics of Java's version.

First, study the provided code in MyArrayList.java. A number of methods have been provided to you already, and numerous hints have been provided in the comments. Below are the methods you should implement. It is recommended that you implement them in the order specified below. A file Tester.java has been provided that compares your method implementations to an actual Java ArrayList object on a random set of many of these operations, so feel free to use that or to write your own code to test it.

• void doubleCapacity(): Double the capacity of the underlying array by creating a new underlying array and copying everything over that was there before up to N. You may want to refer to halveCapacity() as a reference
• void add(Item item): Add an item to the end of the list and update its size. The default implementation throws an exception if the underlying array runs out of space, but you should call your doubleCapacity() method to make space if needed so this doesn't happen.
• void add(int index, Item item): This is an overloaded version of the add method in which an item is added at a specific index in the array. You should move the item that was at that index before, and everything to the right of it, over by one index to accommodate this new item. You should double the capacity of the underlying array if necessary.
• Item remove(int index): Remove an item at a particular index and return it. You should also move everything to the right of this index over one to the left and update the size N. Finally, if the new number of elements being stored is small enough, you should halve the capacity (using the provided halveCapacity() method).
• Item remove(Item item): An overloaded version of the remove method that removes the first occurrence of a particular item in the list if it is present and returns it.