4.10 - Implementing ArrayList Algorithms

ArrayList shares basically the same standard algorithm patterns as arrays: min/max, sum/average, “at least one,” “all,” counting, consecutive pairs, duplicates, shifting/rotating, reversing, plus two new ones since ArrayList can change size: inserting and deleting elements.


ArrayList<Integer> nums = new ArrayList<Integer>();
nums.add(4);
nums.add(8);
nums.add(15);

// sum
int sum = 0;
for (int n : nums) {
    sum += n;
}
System.out.println(sum); // 27

// inserting an element in the middle
nums.add(1, 100); // [4, 100, 8, 15]

// deleting an element
nums.remove(1);   // removes index 1 (the 100): [4, 8, 15]

Maximum, minimum, and average work just like the array versions, using get(i) in place of [i] and size() in place of length:


// nums is [4, 8, 15]
int max = nums.get(0);
int total = 0;
for (int i = 0; i < nums.size(); i++) {
    if (nums.get(i) > max) {
        max = nums.get(i);
    }
    total += nums.get(i);
}
double avg = (double) total / nums.size();
System.out.println(max); // 15
System.out.println(avg); // 9.0

So do at least one, all, counting, consecutive pairs, and duplicates (see 4.5).

Inserting in order: to keep a sorted list sorted, move forward until you reach the first element that’s bigger than the new value, then add the new value at that index.


// nums is [4, 8, 15], sorted from smallest to largest
int value = 10;
int index = 0;
while (index < nums.size() && nums.get(index) < value) {
    index++;
}
nums.add(index, value); // [4, 8, 10, 15]

The index < nums.size() check comes first on purpose. If the new value is bigger than everything, index reaches size(), and short-circuiting stops Java from calling get with a bad index. Adding at index size() just puts the value at the end.

Deleting every element that matches: traverse backward (or use the i-- trick from 4.9) so nothing gets skipped.


// nums is [3, 8, 6, 5], remove every even number
for (int i = nums.size() - 1; i >= 0; i--) {
    if (nums.get(i) % 2 == 0) {
        nums.remove(i);
    }
}
// nums is [3, 5]

Rotating is easier than with an array, since remove and add do the shifting for you:


// nums is [4, 8, 15]
int first = nums.remove(0); // takes 4 off the front: [8, 15]
nums.add(first);            // puts it on the end: [8, 15, 4]

Reversing uses the same swap idea as an array, with get and set:


// nums is [4, 8, 15, 16]
for (int i = 0; i < nums.size() / 2; i++) {
    int temp = nums.get(i);
    nums.set(i, nums.get(nums.size() - 1 - i));
    nums.set(nums.size() - 1 - i, temp);
}
// nums is [16, 15, 8, 4]

Some algorithms need you to traverse multiple collections at the same time, like comparing two ArrayLists element by element.


ArrayList<String> list1 = new ArrayList<String>();
ArrayList<String> list2 = new ArrayList<String>();
// ... assume both are filled with the same number of elements

for (int i = 0; i < list1.size(); i++) {
    System.out.println(list1.get(i) + " vs " + list2.get(i));
}

The collections don’t have to be the same kind. For example, grading a quiz means going through an answer key (an array) and a student’s answers (an ArrayList) at the same time, using the same index for both:


String[] key = {"A", "C", "B", "D"};
ArrayList<String> answers = new ArrayList<String>();
answers.add("A");
answers.add("B");
answers.add("B");
answers.add("D");

int correct = 0;
for (int i = 0; i < key.length; i++) {
    if (key[i].equals(answers.get(i))) {
        correct++;
    }
}
System.out.println(correct); // 3

If the collections can have different lengths, only loop as far as the shorter one, or you’ll go out of bounds on the other.

Back Next