Worked Example: ArrayLists

Section 13.15 Worked Example: ArrayLists - Find Value

Subgoals for Evaluating ArrayLists.

Declaring and initialization of an ArrayList
🔗
1. Set up a one-dimensional dynamic list (initially empty or with a specified initial capacity)
  🔗
  
  🔗
2. Upon instantiation, an ArrayList contains zero elements initially, but elements can be added dynamically using add(). Elements not yet added do not exist until explicitly inserted.
  🔗
  
  🔗
🔗
🔗
Determine access or change of element, or action on entire ArrayList object, and update elements as needed (remembering assignment subgoals)
🔗

🔗
Accessing an ArrayList element
🔗
1. Evaluate expression within get(index) which will be the index for the element to be accessed
  🔗
  
  🔗
2. arrayListName.get(index) returns the value stored at that index
  🔗
  
  🔗
3. index must be between 0 and arrayListName.size() - 1, inclusive; otherwise IndexOutOfBoundsException occurs
  🔗
  
  🔗
🔗
🔗
Changing value of an ArrayList element
🔗
1. Evaluate expression within set(index, value) which will be the index for the element to be replaced
  🔗
  
  🔗
2. arrayListName.set(index, value) replaces the element at index with the specified value
  🔗
  
  🔗
3. (remember the assignment subgoals for verifying data types and evaluating expressions)
  🔗
  
  🔗
4. (remember rules for index values)
  🔗
  
  🔗
🔗
🔗
Whole ArrayList actions
🔗
1. Passing as argument - a copy of the reference to the instantiated ArrayList is passed to the method. This means that any changes made to the elements inside the method persist outside the method. The exception is if the argument is assigned to reference a different ArrayList inside the method.
  🔗
  
  🔗
2. Assignment - changes the reference to point to the ArrayList on the right-hand side of the assignment operator.
  🔗
  
  🔗
🔗
🔗

Subsection 13.15.1

Problem: Assume that the Integer ArrayList alpha has been properly declared and initialized with non-default values, and that the variable target is an int. What does this code accomplish? How would you describe the value in loc?

🔗

int loc = -1;
boolean found = false;
for (int i = 0; i < alpha.size() && !found; i++) {
    if (alpha.get(i) == target)   {
        loc = i;
        found = true;
    }
}

🔗

Subsection 13.15.2 SG1: Declaring and initialization of ArrayList

There is no explicit declaration or initialization of an ArrayList within the code. However, within the code there are .get() method calls, so we know we are accessing an ArrayList.

🔗

alpha is an ArrayList of Integers and has values, but we don’t know what those values are
🔗

🔗
however, we can still diagram a representation of this ArrayList
🔗

🔗
notice that the largest index is size - 1
🔗

🔗

🔗

Subsection 13.15.3 SG2: Determine access or action

Within the loop, we are accessing ArrayList elements.

🔗

Subsection 13.15.4 Evaluating code

int loc = -1;
boolean found = false;

The first two lines are declaring an integer variable (loc) and assigning it a value of -1. This variable will represent the "location" of the target variable, if found. A second variable, found, is declared and given an initial value of false. This variable represents whether or not we have located the target within the ArrayList.

🔗

for (int i = 0; i < alpha.size() && !found; i++) {
    if (alpha.get(i) == target)   {
        loc = i;
        found = true;
    }
}

This loop has index i go from 0 to size - 1 (<size()) by increments of 1.
🔗

🔗
Then the value at alpha.get(i) is compared to the int value of target.
🔗

🔗
If the value at alpha.get(i) is equal to target, then the value i is copied into loc.
🔗

🔗
All indexes into the ArrayList are valid, and all assignments are valid.
🔗

🔗

🔗

Let us trace with a sample ArrayList and assume the value of target is 15.

🔗

The first statement, int loc = -1; gives loc a value that is not a valid index for any ArrayList, and we have not yet found the target within the ArrayList.

🔗

Then a for-loop is used to traverse the ArrayList and compare each element to target. The chart below uses one line to represent the memory and comparisons during each iteration of the loop, starting when i has a value of zero.

🔗

When we find the target value in the ArrayList, we store the index of where the value was found into the variable loc.

🔗

When i is 4, the for loop continuation condition is evaluated:

🔗

i < alpha.size() && !found;

and i (value of 4) is less than alpha.size() (which is 5 in this case) however the variable found is now true, so !found is false. true && false is false, so the loop body is not executed.

🔗

Some questions to consider:

🔗

What would happen if the target value is not in the ArrayList?
Answer.

Then the selection statement is never true, and loc is never changed from its initial value of -1.
🔗

🔗

🔗

🔗
Why is -1 a good initial value for loc?
Answer.

It is not a valid index for any ArrayList. You or another programmer using this algorithm could check the value of loc to make a decision (selection!) for how the program will behave when the target value is found or not found at a valid ArrayList index.
🔗

🔗

🔗

🔗
What would happen if there were 2 occurrences of the target value in the ArrayList?
Answer.

The loop does not end when the target value is found, so no additional occurrences would be evaluated. If the ( && !found) were not included in the code, then any additional occurences of target being found in the ArrayList would overwrite the value of loc with the last occurence.
🔗

🔗

🔗

🔗

🔗

What does this code accomplish?

🔗

Answer.

loc contains the index of the first occurrence of target in the ArrayList alpha or -1 if target is not in the ArrayList.

🔗

Subsection 13.15.5 Practice Pages

ArrayLists-WE7-P1

🔗

🔗

You have attempted 1 of 1 activities on this page.

🔗

Prev Top Next