Module 1: Lists

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