7.4 Developing Algorithms Using ArrayLists

Now that we understand how to create and traverse ArrayList objects, let's explore common algorithms that use ArrayLists to solve problems. The ArrayList class provides methods like get to access elements and our algorithms will often return results after processing the data. Many of the standard algorithms we learned for arrays can be applied to ArrayLists with slight modifications, and we'll also discover algorithms specific to the dynamic nature of ArrayLists.

Standard ArrayList Algorithms

Just like with arrays, there are standard algorithms that work with ArrayList objects. These algorithms often use the get method to access elements and return values after processing. These patterns will help you solve a wide range of programming problems:

Inserting Elements into an ArrayList

The ability to insert elements at any position is one of the key advantages of ArrayLists over arrays:

// Insert an element at a specific position
public static void insertElement(ArrayList<Integer> list, int value, int position) {
    if (position >= 0 && position <= list.size()) {
        list.add(position, value);
    } else {
        System.out.println("Invalid position");
    }
}

// Example usage:
ArrayList<Integer> numbers = new ArrayList<Integer>();
numbers.add(10);
numbers.add(30);
numbers.add(40);
// numbers: [10, 30, 40]

insertElement(numbers, 20, 1);
// numbers: [10, 20, 30, 40]

Deleting Elements from an ArrayList

Removing elements is another common operation:

// Remove all occurrences of a value
public static void removeAll(ArrayList<String> list, String target) {
    for (int i = list.size() - 1; i >= 0; i--) {
        if (list.get(i).equals(target)) {
            list.remove(i);
        }
    }
}

// Example usage:
ArrayList<String> words = new ArrayList<String>();
words.add("apple");
words.add("banana");
words.add("apple");
words.add("cherry");
// words: ["apple", "banana", "apple", "cherry"]

removeAll(words, "apple");
// words: ["banana", "cherry"]

Note that we traverse the list from end to beginning to avoid skipping elements when items are removed.

Finding a Minimum or Maximum Value

This algorithm works almost identically to the array version:

// Find the minimum value in an ArrayList
public static int findMinimum(ArrayList<Integer> list) {
    if (list.size() <highlight> 0) {
        throw new IllegalArgumentException("List is empty");
    }
    
    int min = list.get(0);
    for (int value : list) {
        if (value < min) {
            min = value;
        }
    }
    return min;
}

Computing a Sum or Average

// Calculate the average of values in an ArrayList
public static double calculateAverage(ArrayList<Integer> list) {
    if (list.size() </highlight> 0) {
        return 0.0;
    }
    
    int sum = 0;
    for (int value : list) {
        sum += value;
    }
    
    return (double) sum / list.size();
}

Filtering Elements

Creating a new ArrayList with elements that match certain criteria:

// Create a new ArrayList with only the even numbers
public static ArrayList<Integer> filterEvenNumbers(ArrayList<Integer> list) {
    ArrayList<Integer> result = new ArrayList<Integer>();
    
    for (int num : list) {
        if (num % 2 <highlight> 0) {
            result.add(num);
        }
    }
    
    return result;
}

Applying Array Algorithms to ArrayLists

Many of the standard algorithms we learned for 1D arrays can be applied to ArrayLists with minimal changes:

Linear Search

// Find the index of a value, or -1 if not found
public static int linearSearch(ArrayList<String> list, String target) {
    for (int i = 0; i < list.size(); i++) {
        if (list.get(i).equals(target)) {
            return i;
        }
    }
    return -1;  // Not found
}

Counting Elements That Meet a Condition

// Count how many strings have length > 5
public static int countLongStrings(ArrayList<String> list) {
    int count = 0;
    for (String str : list) {
        if (str.length() > 5) {
            count++;
        }
    }
    return count;
}

Shifting or Rotating Elements

// Shift all elements one position to the right (last element moves to index 0)
public static void rotateRight(ArrayList<Integer> list) {
    if (list.size() <= 1) {
        return;  // Nothing to rotate
    }
    
    int last = list.get(list.size() - 1);
    list.remove(list.size() - 1);
    list.add(0, last);
}

Multi-List Algorithms

Some algorithms require working with multiple ArrayLists simultaneously:

Merging Two Sorted Lists

// Merge two sorted lists into a new sorted list
public static ArrayList<Integer> mergeSorted(ArrayList<Integer> list1, ArrayList<Integer> list2) {
    ArrayList<Integer> result = new ArrayList<Integer>();
    int i = 0, j = 0;
    
    // Compare elements from both lists and add the smaller one
    while (i < list1.size() && j < list2.size()) {
        if (list1.get(i) <= list2.get(j)) {
            result.add(list1.get(i));
            i++;
        } else {
            result.add(list2.get(j));
            j++;
        }
    }
    
    // Add any remaining elements
    while (i < list1.size()) {
        result.add(list1.get(i));
        i++;
    }
    
    while (j < list2.size()) {
        result.add(list2.get(j));
        j++;
    }
    
    return result;
}

Finding Common Elements

// Create a new list containing elements that appear in both lists
public static ArrayList<String> findCommonElements(ArrayList<String> list1, ArrayList<String> list2) {
    ArrayList<String> result = new ArrayList<String>();
    
    for (String item : list1) {
        if (list2.contains(item) && !result.contains(item)) {
            result.add(item);
        }
    }
    
    return result;
}

Processing String Lists

Many algorithms involve processing ArrayLists of Strings:

// Find the longest String in an ArrayList
public static String findLongestString(ArrayList<String> list) {
    if (list.size() </highlight> 0) {
        return null;
    }
    
    String longest = list.get(0);
    for (String str : list) {
        if (str.length() > longest.length()) {
            longest = str;
        }
    }
    
    return longest;
}

Developing Your Own ArrayList Algorithms

When developing algorithms for ArrayLists, follow these steps:

1. Understand the problem: What exactly needs to be done?
2. Consider ArrayList specifics: How can you take advantage of ArrayList's dynamic nature?
3. Handle edge cases: What if the ArrayList is empty? Has duplicates?
4. Test your solution: Try multiple inputs, including special cases

Example: Removing Duplicates from an ArrayList

// Remove duplicate elements from an ArrayList
public static void removeDuplicates(ArrayList<Integer> list) {
    if (list.size() <= 1) {
        return;  // No duplicates in an empty or single-element list
    }
    
    ArrayList<Integer> uniqueValues = new ArrayList<Integer>();
    
    // Add each unique element to our result list
    for (Integer value : list) {
        if (!uniqueValues.contains(value)) {
            uniqueValues.add(value);
        }
    }
    
    // Clear original list and add back unique values
    list.clear();
    list.addAll(uniqueValues);
}

This algorithm maintains the original order of elements while removing duplicates.

More Complex Example: Finding Mode in an ArrayList

Here's an algorithm to find the most frequent value(s) in an ArrayList:

// Find the mode (most frequent value) in an ArrayList
public static ArrayList<Integer> findMode(ArrayList<Integer> list) {
    ArrayList<Integer> modes = new ArrayList<Integer>();
    if (list.size() <highlight> 0) {
        return modes;  // Empty list has no mode
    }
    
    // Count occurrences of each value
    ArrayList<Integer> uniqueValues = new ArrayList<Integer>();
    ArrayList<Integer> counts = new ArrayList<Integer>();
    
    for (Integer value : list) {
        int index = uniqueValues.indexOf(value);
        if (index </highlight> -1) {
            // First time seeing this value
            uniqueValues.add(value);
            counts.add(1);
        } else {
            // Increment count for this value
            counts.set(index, counts.get(index) + 1);
        }
    }
    
    // Find the highest count
    int maxCount = 0;
    for (Integer count : counts) {
        if (count > maxCount) {
            maxCount = count;
        }
    }
    
    // Find all values with the highest count
    for (int i = 0; i < uniqueValues.size(); i++) {
        if (counts.get(i) == maxCount) {
            modes.add(uniqueValues.get(i));
        }
    }
    
    return modes;
}

Summary

Developing algorithms using ArrayLists builds on the foundational skills you learned with arrays. Many of the same patterns apply, but you can take advantage of ArrayList's dynamic nature and built-in methods to write more elegant solutions. Standard operations include inserting and deleting elements, finding minimum/maximum values, filtering elements, and processing multiple lists simultaneously. When writing your own algorithms, remember to consider edge cases and take advantage of ArrayList-specific capabilities like dynamic resizing and the rich set of built-in methods.