Lab 1 Building an ArrayList

Overview · Learning Goals · Files · How an ArrayList Works · Tasks · Testing · Checkpoint · Submission

Overview

In this lab you will build a simplified version of Java's ArrayList. An ArrayList stores elements in an underlying array, but unlike an ordinary array, it can grow when more space is needed.

Java already provides an ArrayList, but implementing the data structure yourself provides insights into how an array-backed list actually works.

It is not enough to just get the code to "work." It is more important that you understand why the code is designed the way it is and what is happening inside the data structure when an element is added, retrieved, replaced, or removed.

Why are we building our own ArrayList? Building the data structure ourselves lets us examine the relationship between the public methods of an ArrayList and the underlying array that makes those methods possible.
This ArrayList will be used in Project 1. Your Hand and Deck classes will depend on the ArrayList you build today. Take the time to make each operation work correctly before moving on.

Learning Goals

By completing this lab, you should become more comfortable with:

Files Provided

Download the provided files and place them in a folder named Lab1.

Download ArrayList.java Download ArrayListTester.java

You will write your code in ArrayList.java. Look for TODO comments throughout the file. Some TODOs contain hints, but you are responsible for writing the implementation.

ArrayListTester.java is provided to help you test your work incrementally. Do not modify the tester.

One method has been provided for you. The initializeArray method creates the underlying array. It uses Java syntax involving generic arrays and Object that we have not covered yet, so the complete method has been provided. You do not need to modify it.

How an ArrayList Works

Our ArrayList keeps track of two important pieces of information:

Suppose an ArrayList currently contains the values 8, 3, and 6: 

index       0       1       2       3       4
         +-------+-------+-------+-------+-------+
arr      |   8   |   3   |   6   | null  | null  |
         +-------+-------+-------+-------+-------+

size = 3
capacity = 5

The size is 3 because the list contains three elements. The capacity is 5 because the underlying array has five available positions.

Size and capacity are not the same thing. Your loops should usually process only the elements that are actually part of the list, not every position that happens to exist in the underlying array.

Lab Tasks

Task 1 — Create Instance Variables and Constant

Begin by identifying the information that every ArrayList needs to keep track of. The declaration for the underlying generic array, arr, has been provided for you.

Complete the TODOs that declare:

Choose the appropriate access. If you don't know how to declare a constant, raise your hand!

Task 2 — Constructors and Size

Begin by completing both constructors and the size() method. 

public ArrayList()
public ArrayList(int initialCapacity)
public int size()

A newly constructed ArrayList should be empty, regardless of the capacity of its underlying array.

Avoid duplicate initialization code. In the default constructor, use the this operator to call the one-argument constructor using the DEFAULT_CAPACITY constant.
Size and capacity are not the same thing. Capacity describes how much room the underlying array has. size describes how many elements are currently in the list. Make sure you understand this distinction and can explain it in your own words.

Notice that size() is, in fact, a getter. Sometimes get can be dropped from a getter's name when the method name is unambiguous.

Task 3 — Add Elements and Grow the Array

Complete:

public void add(T item)
private void changeCapacity(int newCapacity)

add places a new item at the end of the list. If there is no room left in the underlying array, the ArrayList must create a larger array before storing the new item.

Think about the order of operations. Before adding an item, determine whether the underlying array is full. If it is full, increase its capacity. Then store the item in the next available position and update size.

The provided initializeArray method creates an empty underlying array. When changeCapacity creates a new array, your existing elements must not disappear.

Task 4 — Get and Set Elements

Complete:

public T get(int index)
public void set(int index, T item)

get returns the element currently stored at an index. set replaces the element at an existing index.

For example, if the list contains:

[10, 20, 30]

then:

get(1)       → 20
set(1, 99)   → list becomes [10, 99, 30]
Important: set is a destructive operation: it overwrites the element currently stored at the specified index. The previous element at that index is replaced. set does not add another element, so the size of the list should not change.

Task 5 — Remove an Element

Complete:

public T remove(int index)

Removing an element from an array-backed list requires more work than simply clearing one array position.

Consider:

index       0       1       2       3
         +-------+-------+-------+-------+
before   |   A   |   B   |   C   |   D   |
         +-------+-------+-------+-------+

remove(1)

         +-------+-------+-------+-------+
after    |   A   |   C   |   D   | null  |
         +-------+-------+-------+-------+

The method must return the element that was removed. The elements after that position must shift one position to the left, and the size of the list must decrease. After the shift and size change, set the old location of the last element to null.

Do not rush through this task. Work out the movement on paper first. Ask yourself where the loop should begin, where it should stop, and which array position should be copied into which other position.

Task 6 — Create a String Representation

Complete:

public String toString()

Your method should return a String showing the elements in order, enclosed in square brackets and separated by commas and spaces. 

empty list        → []
one element       → [4]
three elements    → [4, 7, 2]
Think about the punctuation. The comma belongs between elements. Make sure your result does not contain an unnecessary comma after the final element.

Test as You Work

Do not wait until the end of the lab to test everything at once. Complete one task, compile your files, run the tester, and then move to the next task. 

javac ArrayList.java ArrayListTester.java
java ArrayListTester
The tester is designed for incremental progress. It checks your work in task order. If a task is not yet complete, the tester stops there so that you can focus on the methods you are currently developing rather than seeing failures from later tasks.

Tasks 1 and 2 are special cases. Declarations cannot be verified through normal ArrayList behavior, and a newly constructed ArrayList should have size 0 while the unfinished skeleton's placeholder size() also returns 0. Before moving on, ask the instructor or a TA to review your code for Tasks 1 and 2. The tester begins its behavioral checks with Task 3.

As you progress, the tester will report results such as: 

PASS: Added value can be retrieved
PASS: Several adds update size correctly
FAIL: ArrayList grows beyond its initial capacity
      expected=8, got=2

Task result: 2/3 tests passed
TASK NOT YET COMPLETE
Use FAIL as feedback. Read the description of the failed test and compare the expected value with the value produced by your code. Fix the current task, compile again, and rerun the tester.
The tester is a tool, not the specification. Passing all of the tests means that you are ready for the checkpoint. It does not mean that you have completed or passed the checkpoint. You should be able to explain the behavior of the methods you wrote, especially how resizing and removal work.

Lab Checkpoint

Checkpoint required for Lab 1 credit. Before asking for your checkpoint, make sure that ArrayListTester.java passes all of its automated tests. Then demonstrate the passing tester to a TA or instructor.

The tester checks whether your ArrayList behaves correctly. The checkpoint also checks whether you understand the code you wrote. Be prepared to answer questions about your implementation. A TA or instructor may choose a couple of questions such as:

  1. What is the difference between size and capacity? Where is each represented in your implementation?
  2. What happens when add is called and the underlying array is full? Explain how your code increases the capacity without losing the elements already stored in the list.
  3. What happens inside the underlying array when an element is removed? Explain why elements need to shift and why the old location of the last element is set to null.
  4. How is set different from add? Explain why set is a destructive operation and why it does not change the size of the list.
  5. Why does the default constructor call the one-argument constructor? Explain what using this(...) accomplishes and why it is preferable to duplicating the initialization code.
You do not need to memorize an answer. You should be able to look at your own code and explain, in your own words, how it works and why it is designed that way.

After You Pass the Checkpoint

If you finish the ArrayList and pass the checkpoint, begin working on Project 1.

Submission

It is your responsibility to upload your lab files before the end of the lab period.

  1. Navigate to your personal course Google Drive folder.
  2. Open your projects folder.
  3. Create a new folder named Lab1.
  4. Place your completed ArrayList.java file in that folder.
Before you leave: passing the checkpoint and uploading your files are both your responsibility. Make sure your work is in your Google Drive folder before the lab period ends.