ArrayList algorithms

Pretty much anything we can do with arrays we can also do with ArrayLists.

But because ArrayLists are more flexible than arrays there are also things specific to ArrayLists.

The primordial for loop over an ArrayList

for (int i = 0; i < list.size(); i++) {
  // code here that uses i, e.g. list.get(i)
}

Enhanced for loop over an ArrayList

for (String s : list) {
  // code here that uses s
}

Use this unless you specifically need to know the index or if you need to modify the list by adding or removing elements in the loop.

Equivalence

for (String s : list) {
  // code here that uses s
}

is basically equivalent to:

for (int i = 0; i < list.size(); i++) {
  String s = list.get(i);
  // code here that uses s
}

Except we don’t have access to i in the enhanced for loop and we’re not allowed to do anything to list that changes its size.

A counting for loop

Count the number of things that match some criteria.

public int countEggs(ArrayList<String> words) {
  int  count = 0;
  for (String word : words) {
    if (word.equals("egg")) {
      count++;
    }
  }
  return count;
}

A summing for loop

Accumulate a total.

public int sum(ArrayList<Integer> ns) {
  int total = 0;
  for (int n : ns) {
    total += n;
  }
  return total;
}

A mapping for loop

Make a new list with one element for each element in the old list.

public ArrayList<Integer> doubled(ArrayList<Integer> ns) {
  ArrayList<Integer> result = new ArrayList<>();
  for (int n : ns) {
    result.add(n * 2);
  }
  return result;
}

A filtering for loop

Keep just elements that meet some criteria.

public ArrayList<String> xWords(ArrayList<String> strings) {
  ArrayList<String> result = new ArrayList<>();
  for (String s : strings) {
    if (startsWithX(s)) {
      result.add(s);
    }
  }
  return result;
}

A finding for loop

Find an element that matches some criteria.

public String findStartsWithX(ArrayList<String> words) {
  for (String word : words) {
    if (startsWithX(word)) {
      return word;
    }
  }
  // need some distinguished value for when not found
  return null;
}

Checking for some

Return true if some element matches our criteria.

public boolean someLong(ArrayList<String> words) {
  for (String word : words) {
    if (word.length() > 10) {
      // Found one
      return true;
    }
  }
  // Didn't find any.
  return false;
}

Checking for all

Return true if all elements match our criteria.

public boolean allLong(ArrayList<String> words) {
  for (String word : words) {
    if (word.length() <= 10) {
      // Found counter example
      return false;
    }
  }
  // No counter examples found.
  return true;
}

Nested for loops

public ArrayList<String> paired(ArrayList<String> words) {
  ArrayList<String> result = new ArrayList<>();
  for (String w1 : words) {
    for (String w2 : words) {
      result.add(w1 + " " + w2);
     }
  }
  return result;
}

Removing in a loop

Suppose we want to remove items matching some criteria from an ArrayList.

We need to check all the elements of the list so that suggests we need a loop.

But we need to be a bit careful about how we iterate through the loop since when we remove an item from a list all the items to the right (at greater indices) shift down one index.

Cannot use an enhanced for loop

First off, we don’t have the index so we don’t know where the item is that we want to remove.

But more important, you aren’t allowed to modify an ArrayList in a way that changes its size (i.e. adding or removing elements) while iterating over it with an enhanced for loop.

for loop to remove things

for (int i = 0; i < strings.size(); i++) {
  if (dontLikeThisOne(strings.get(i))) {
     strings.remove(i);
     // The element that was at i + 1 is now at i,
     // so on the next iteration of the loop we'd
     // end up skipping that element. So we decrement
     // i here so after the i++ we're back to the
     // current value of i.
     i--;
  }
}

A normal for loop except doing a thing that is generally frowned upon, namely modifying the loop variable inside the loop itself. But in this case it’s necessary to compensate.

while loop to remove things

int i = 0;
while (i < strings.size()) {
  if (dontLikeThisOne(strings.get(i))) {
     strings.remove(i);
  } else {
    i++;
  }
}

Similar to the for loop on the previous slide but because we have to update the loop variable in the loop body, we only do it when we actually need to move forward.

Looping backwards

for (int i = strings.size() - 1; i >= 0; i--) {
  if (dontLikeThisOne(strings.get(i))) {
    strings.remove(i);
  }
}

Possibly the cleanest. A canonical backwards for loop and we don’t have to adjust the index because when we remove an element the things at greater indices shift down but we’re moving on to a yet lower index.

Will also do slightly less copying while shifting things down.

Summary

For the AP curriculum this is pretty much all you need to know plus how to use what’s covered here in some standard algorithms, many of which we’ve already discussed in the context of arrays.

Make sure you are clear about the differences and similarities between ArraryLists (a class, can change size, manipulated with methods) and arrays (built into the language, fixed-size, manipulated with special syntax.)

See also

For loop patterns

Counting Loops Summary

For loop templates