Step 0: Understanding the Specification

Section 12.11 Step 0: Understanding the Specification

With our project environment ready, we begin applying the Design Recipe (See Chapter 1) to implement our DataStructures.ArrayList<T>. As Step 0 is "Understand and Restate the Problem," and our "problem" is defined by the ADTs.ListADT<T> interface specification, our focus here is to deeply understand this specification: what operations must our ArrayList<T> provide, what are their conceptual effects, and what is the underlying model (a dynamic array)?

🔗

Subsection 12.11.1 The Core Task Revisited

Our goal is to create the class DataStructures.ArrayList<T> which implements the ADTs.ListADT<T> interface. This class must use a standard Java array (T[]) internally for storage and must automatically handle dynamic resizing to accommodate a varying number of elements. It must also adhere precisely to the conceptual behavior defined for each method in the ListADT<T> interface (which implies handling various edge cases and error conditions appropriately, as will be detailed by the Javadoc and explored in later Design Recipe steps).

🔗

Subsection 12.11.2 Understanding the Required Operations (The `ListADT` Contract)

The ListADT<T> interface (in src/ADTs/ListADT.java) specifies the methods our class must provide. Let’s understand the core concepts, grouped logically. Consult the Javadoc in the interface file later (especially during Step 2 and 3) for precise details on parameters, return values, and specific error conditions.

🔗

Note 12.11.1. Focus on Javadoc Later.

While the Javadoc comments in ListADT.java contain the full specification details (like exact index bounds and exception types), for Step 0, we focus on the conceptual purpose and effect of each operation group. We’ll refer back to the Javadoc for precision in later steps.

🔗

Subsubsection 12.11.2.1 1. Adding Elements

The primary method for adding is add(int index, T item). Conceptually, this operation increases the list’s size by one and places the new item at the specified index. All elements that were previously at or after this index now occupy the next higher position (index + 1).

🔗

Conceptual State Change for add(1, "X") on list [A, B, C] (size 3) in an array of capacity 5:

🔗

State Before:
  size = 3
  array = [ A | B | C |null|null ] (capacity=5)
Indices:    0   1   2    3    4

Operation: add(1, "X")

State After:
  size = 4
  array = [ A | X | B | C |null ] (capacity=5)
Indices:    0   1   2   3    4

The interface also provides convenience methods built upon this concept:

🔗

addLast(T item): Adds the item to the very end (conceptually, at the position indicated by the current size).

🔗
addFirst(T item): Adds the item to the very beginning (index 0), causing all previous elements to conceptually occupy positions one index higher.

🔗
addAfter(T existing, T item): Conceptually, this finds the existing item and performs an add immediately after its position.

🔗

A key underlying requirement is that the internal array must have enough capacity; if not, resizing must occur conceptually before the addition happens.

🔗

Subsubsection 12.11.2.2 2. Removing Elements

The primary method for removal by position is remove(int index). Conceptually, this operation decreases the list’s size by one and returns the element that was previously at the specified index. All elements that were after the removed element now occupy the next lower position (index - 1).

🔗

Conceptual State Change for remove(1) from list [A, B, C, D] (size 4) in an array of capacity 5:

🔗

State Before:
  size = 4
  array = [ A | B | C | D |null ] (capacity=5)
Indices:    0   1   2   3    4

Operation: remove(1) (Conceptually removes "B")

State After:
  size = 3
  array = [ A | C | D |null|null ] (capacity=5)
Indices:    0   1   2    3    4

Other removal methods build on this:

🔗

removeFirst(): Removes the element at index 0. Assumes the list is not empty.

🔗
removeLast(): Removes the element at index size() - 1. Assumes the list is not empty.

🔗
remove(T item): Finds the first occurrence of item and conceptually performs a remove at that index. Indicates if an item was removed.

🔗
clear(): Removes all elements, resulting in an empty list (size 0).

🔗

🔗

Subsubsection 12.11.2.3 Maintaining Compactness: The "No Gaps" Rule

Notice that the conceptual "State After" diagrams for add(index) and remove(index) show the elements remaining tightly packed together at the start of the array space. This reflects a fundamental design principle for our ArrayList: elements must always occupy the contiguous block of indices from 0 to size - 1. We do not allow null "gaps" within the list’s active range.

🔗

Why enforce this "no gaps" rule? Allowing gaps (e.g., [ A | null | C | D | null ] after removing "B") would severely complicate almost every other list operation. How would size() work reliably? What should get(1) return? How would loops iterate correctly without needing extra checks for internal nulls?

🔗

By deciding that our list elements must always form a contiguous block, we simplify the logic for size(), get(index), iteration, and searching. The necessary consequence of this decision is that insertions and deletions in the middle or at the beginning *require* conceptually shifting subsequent elements to either make space or close a gap. Understanding this design constraint *now* (in Step 0) is key to understanding the required behavior.

🔗

Subsubsection 12.11.2.4 4. Other Operations (Accessing, Querying)

These operations typically read the list’s state without changing the order or size (except for set):

🔗

get(int index): Returns the element currently at index.
🔗

🔗
set(int index, T item): Replaces the element at index with item, returning the element that was replaced.
🔗

🔗
first(): Returns the first element in the list (at index 0) without removing it. Assumes the list is not empty.
🔗

🔗
last(): Returns the last element in the list (at index size() - 1) without removing it. Assumes the list is not empty.
🔗

🔗
isEmpty(): Reports if size is 0.
🔗

🔗
size(): Reports the current number of elements.
🔗

🔗
contains(T item): Checks if the item exists anywhere in the range 0 to size-1 (using equals).
🔗

🔗
indexOf(T item): Finds the index of the first occurrence of item in the range 0 to size-1, or returns -1.
🔗

🔗

🔗

Subsubsection 12.11.2.5 5. Modifying Structure

This operation changes the list’s overall state dramatically:

🔗

clear(): Removes all elements, resulting in an empty list (size 0).
🔗

🔗

🔗

Subsection 12.11.3 The Dynamic Resizing Concept Revisited

The other key conceptual requirement is dynamic resizing, triggered when an add operation occurs and the internal array is already full (size == array.length).

🔗

Conceptual State Change for Adding "D" when internal array [A, B, C] (capacity 3, size 3) is full:

🔗

State Before Add:
  size = 3
  Internal array state = [ A | B | C ]  (capacity=3)

Action: addLast("D") --> Requires more capacity!

State After Add (Conceptually):
  size = 4
  Internal array state = [ A | B | C | D |null|null ] (capacity is now larger, e.g., 6)

Conceptually, the list must behave as if it obtained a larger internal storage space, copied the old elements over, and then performed the addition. The user of the list doesn’t see the resizing happen, only the successful addition and the increased size.

🔗

Subsection 12.11.4 A Quick Look at the `ListADT` Design

As we understand the specification, it’s useful to think critically about its design. You might notice potential redundancy in the ListADT. For example, addLast(T item) has the same effect as add(size(), item), and removeFirst() could likely be implemented by calling remove(0).

🔗

Why include such methods? Often for convenience or to match common ways users think about lists. This highlights that API design involves trade-offs. For this project, our task is simply to implement the interface *as given*, fulfilling the contract for all specified methods. Recognizing these aspects is part of critically understanding a specification.

🔗

With a solid grasp of the required operations’ conceptual effects (including the "no gaps" principle), the dynamic array concept, and the overall task as defined by ListADT, we have completed Step 0. We are now ready to proceed to Design Recipe Step 1: defining the specific data fields needed within our ArrayList<T> class to maintain the list’s state.

🔗

You have attempted of activities on this page.

🔗

Prev Top Next