Module 1: Lists

Module Overview

Learn about ArrayList and how to maintain ordered collections of objects in Java.

Learning Objectives

Implement code to iterate over the elements of a List to perform an operation on each element
Implement code to add an object to a List
Implement code to remove an object from a List
Explain why accessing a value by index from an ArrayList runs in constant O(1) time
Explain why inserting or removing a value by index in an ArrayList runs in linear O(n) time

Detailed Explanations

Working with ArrayLists

ArrayLists are a flexible implementation of the List interface that use arrays internally to store elements. Unlike arrays, they don't require a fixed size and can grow dynamically.

Adding Elements to a List

You can add elements to an ArrayList using the add() method in two ways:

// Adding to the end of the list
ArrayList<String> coffeeOrders = new ArrayList<String>();
coffeeOrders.add("small coffee");

// Adding at a specific index
coffeeOrders.add(5, "large latte");

When adding at a specific index, all elements at that index and beyond are shifted right, making this an O(n) operation in the worst case.

Removing Elements from a List

The remove() method allows you to remove elements by index:

// Remove element at index 10
coffeeOrders.remove(10);

After removal, all elements beyond the removed index shift left to fill the gap, making this an O(n) operation.

Iterating Over a List

You can iterate through all elements in an ArrayList to perform operations on each item:

// Using a standard for loop
for (int i = 0; i < coffeeOrders.size(); i++) {
    System.out.println(coffeeOrders.get(i));
}

// Using enhanced for loop (for-each)
for (String order : coffeeOrders) {
    System.out.println(order);
}

Performance Characteristics

Understanding the performance of ArrayList operations is crucial:

get(index): O(1) - Constant time because ArrayLists provide direct access to elements via their underlying array
add(element): Amortized O(1) - Usually constant time, but occasionally O(n) when internal array needs resizing
add(index, element): O(n) - Linear time due to shifting elements to make room
remove(index): O(n) - Linear time due to shifting elements to fill the gap
contains(element): O(n) - Linear time as it may need to check each element

Guided Projects

ATA String Builder

To start this project, you will need to create a copy of this:

Google Sheet

Project Instructions:

On this sheet you will find a "Storage Chest" containing various Colors and an ArrayList colorList.

You will be responsible for performing actions on colorList with the items in the Storage Chest.

The Javadoc for ArrayList can be found at: https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html

Tasks:

Task 0: Prepare documents
- Create a copy of the provided Google Sheet.
- Open your copy of this document.
Task 1: Add at the end
- Start with these items in the array, in this order: black, green, white, blue, salmon.
- Execute this code: colorList.add(purple);
- Record the number of each operation required.
- What is the worst case for the number of operations this could take? The best case?
Task 2: Add at an index
- Your array should now look like: black, green, white, blue, salmon, purple.
- Execute this code: colorList.add(0, red);
- Record the number of each operation required. Hint: Adding at an index which has a value will require that you move the existing item at the index, and all elements after, one spot down the line.
- What is the worst case for the number of operations this could take? The best case?
- If you needed to populate an ArrayList with many items, would you add each item to the end or to the start?
Task 3: Remove a piece from an index
- Your array should now look like: red, black, green, white, blue, salmon, purple.
- Execute this code: colorList.remove(3);
- Record the number of each operation required.
- What is the worst case for the number of operations this could take? The best case?
Task 4: Remove a piece if it exists
- Your array should now look like: red, black, green, blue, salmon, purple.
- Execute this code: colorList.remove(salmon);
- Record the number of each operation required.
- What is the worst case for the number of operations this could take? The best case?
- What happens if the piece doesn't exist?
Extension - Task 5: Put a piece
- Your array should now look like: red, black, green, blue, purple.
- Execute this code: colorList.set(0, yellow);
- Record the number of each operation required.
- What is the worst case for the number of operations this could take? The best case?
Extension - Task 6: Check for a piece
- Your array should now look like: yellow, black, green, blue, purple.
- Execute this code: colorList.contains(green);
- Record the number of each operation required.
- What is the worst case for the number of operations this could take? The best case?