ITSC 1213 - Introduction to CS 2 How to Design Programs with Object Oriented Programming

Section 12.12 Step 1: Designing the Data

• To implement get(index) or set(index, item): We clearly need access to the underlying sequence of elements themselves to retrieve or modify the one at a specific position. Information Needed: The stored elements in order.

  🔗
  🔗
• To implement size() or isEmpty(): We need to know the current number of elements actively stored in the list, which might be different from the total storage capacity. Information Needed: The current count of elements.

  🔗
  🔗
• To implement add(index, item) or remove(index): We need the current elements (to shift them) and the current size (to know which elements to shift and where the valid indices end). We also need to know if there’s enough underlying storage capacity. Information Needed: The stored elements, the current count, the storage capacity.

  🔗
  🔗
• To handle dynamic resizing (when adding to a full list): We need access to the current elements (to copy them) and the current storage capacity (to know when it’s full and how much larger the new storage should be). Information Needed: The stored elements, the storage capacity.

  🔗
  🔗
• To implement search operations like contains(item) or indexOf(item): We need the current elements and the current size (to know how many elements to check). Information Needed: The stored elements, the current count.

  🔗
  🔗

1. The sequence of elements: Since we decided in Step 0 to use an array internally, we need an array field to hold the actual list items.

   🔗
   🔗
2. The current number of elements: We need to track how many items are *actually* in the list, as distinct from the total capacity of the internal array. This logical size determines valid indices and when resizing is needed.

   🔗
   🔗

public class ArrayList<T> implements ListADT<T> {

    // 1. An array to store the list elements.
    //    It holds type T (the generic type parameter).
    private T[] buffer;

    // 2. An integer to track the number of elements currently in the list.
    private int size;

    // Constructor and methods will go here...
}

// Inside the ArrayList constructor (preview of Step 5)
private static final int DEFAULT_CAPACITY = 10; // Example capacity

public ArrayList() {
    // Cannot do: this.buffer = new T[DEFAULT_CAPACITY]; // Compile Error!
    // Workaround: Create Object array and cast
    this.buffer = (T[]) new Object[DEFAULT_CAPACITY]; // Requires unchecked cast
    this.size = 0;
}