ArrayLists

ArrayList traversals have several important applications in regards to how data is used and analyzed.

These various applications generally belong to a larger subset of applications:

• Mathematical Analysis

  • Determine a minimum or maximum value
  • Compute a sum, average, or mode

• Analyzing Element Properties

  • Determine if at least one element has a particular property
  • Determine if all elements have a particular property
  • Access all consecutive pairs of elements
  • Determine the presence or absence of duplicate elements
  • Determine the number of elements meeting specific criteria

• Reordering Elements

  • Shift or rotate elements left or right
  • Reverse the order of the elements

Each of these subsets uses a distinct algorithm to analyze arrays.

Computing mathematical results, such as the sum of integers in an array or finding the average of each value in an array requires the use of a similar algorithm:

ArrayList<Integer> scores = new ArrayList<Integer>();
//add values to scores

//Initialize value here
int valueToFind = 0;
for (int i = 0; i < scores.size(); i++){
    //Perform calculation on valueToFind
}
//Report results of valueToFind

In each case, the algorithm requires the initialization of a value that will be used to store the result of a given computation outside of the for loop. Inside the loop, the initialized value, valueToFind, will be altered depending on the desired output, and the results will be displayed after the loop has terminated.

For a better understanding of this, consider this implementation of computing a sum:

ArrayList<Integer> scores = new ArrayList<Integer>();
//add values to scores

int sum = 0;
for (int i = 0; i < scores.size(); i++){
    sum += scores.get(i);
}
System.out.println(sum);

The value of sum is changed each iteration through the for loop, adding the current score to the value of sum. This algorithm looks awfully similar to the one used to find the average value of an array:

ArrayList<Integer> scores = new ArrayList<Integer>();
//add values to scores

int sum = 0;
for (int i = 0; i < scores.size(); i++){
    sum += scores.get(i);
}
System.out.println((double) sum / scores.size());

In both cases, the initialized value is declared before the for loop, used in mathematical computations within, and then displayed after its termination.

To determine if an element, or a set of elements in an ArrayList meets a specific criteria or has a specific set of properties, the following general algorithm can be used:

ArrayList<String> grades = new ArrayList<String>();
//add values to grades

//Initialize tracker variable
for (int i = 0; i < grades.size(); i++){
    //Conditionally check properties
}
//Report results here

Similar to mathematical analysis, property analysis sets an initial tracker variable before the start of the for loop, and checks through each iteration if the element at a specific index meets the criteria. It then reports the findings after the loop has terminated.

In the following example, the tracker variable checks how many A’s there are in the grade array:

ArrayList<String> grades = new ArrayList<String>();
//add values to grades

//Initialize tracker variable
int numAs = 0;

for (int i = 0; i < grades.size(); i++){
    //Conditionally check properties
    if (grades.get(i).equals("A")) {
        numAs++;
    }
}

System.out.print("Number of A's: ");
System.out.println(numAs);

In this case, the value of the tracker variable numAs increments if the element at each index is an A. These tracker variables can also be used to store a single value that changes depending on the condition. For example, finding the minimum value of a list looks similar to the previous example, but only stores a single value:

ArrayList<Integer> scores = new ArrayList<Integer>();
//add values to scores

int minIndex = 0;

for (int i = 1; i < scores.size(); i++){
    if (scores.get(i) < scores.get(minIndex) {
        minIndex = i;
    }
}
System.out.println(minIndex);

Rather than increment, this tracker keeps track of the current minimum value in the list. If the value at the current index is less than the existing minimum, then the tracker is changed to reflect that.

Another common ArrayList algorithm involves reordering or reversing our arrays. While this can be done in a few different ways, a common method is to create a new temporary array where a copy of the new order for values is stored. Once the new order is copied into the temporary array, it overwrites the original array with the temporary one:

ArrayList<Integer> numbers = new ArrayList<Integer>();
//add values to scores

ArrayList<Integer> temp = new ArrayList<Integer>();
//add values to scores

//Edge case
temp.add(numbers.get(numbers.size() - 1));

//Loop, but stop at the last element (edge case)
for (int i = 0; i < numbers.size() - 1; i++){
    temp.add(i + 1, numbers.get(i));
}

numbers = temp; //Copy over to the original ArrayList

In this example, the algorithm is shifting the values in the array to the right by one. Rather than move the values in the existing ArrayList, a new ArrayList is created to store the values in the specified order. This removes the possibility that the original ArrayList gets altered accidentally, and that changes to the new ArrayList do not impact the original. Note that the edge case is added before the for loop. This ensures that the ArrayList add method will work, as it can only add values to index values from 0 - size().

Some algorithms require ArrayLists to be traversed simultaneously. One such example would be if you wanted to sum the indices of two ArrayLists:

list1
+

list2
=

summedList

Creating the summedList requires that both list1 and list2 are traversed simultaneously to access and sum the individual values at each index:

ArrayList<Integer> summedList = new ArrayList<Integer>();
for(int index = 0; index < list1.size(); index++)
{
    int sum = list1.get(index) + list2.get(index);
    summedList.add(sum);
}

With Strings, we need to use the equals method to determine if two Strings are the same.

Let’s write an equals method for the ArrayList class that returns true if two ArrayLists are the same, and false if the ArrayLists are not identical. An ArrayList is identical if all of the values at each index are the same.