ArrayList traversals

Section 10.3 `ArrayList` traversals

We traverse an ArrayList when we use a loop to access its elements in order. Traversing an ArrayList is very similar to traversing an array; we use the same kinds of loops and just have to swap the length property of arrays for the size() method of ArrayList and use get and set methods instead of array access expressions with [].

🔗

Similarly, all the algorithms we learned about in Section 5.3 Basic loop algorithms can be used with an ArrayList. Additionally we can write algorithms that remove elements from an ArrayList while we loop over it though as we’ll see we do need to exercise some care.

🔗

Subsection 10.3.1 The canonical `for` loop over an `ArrayList`

Recall the structure of the canonical for loop that runs n times:

🔗

for (int i = 0; i < n; i++) {
  // whatever
}

When we used that canonical structure to loop over an array we replaced n with array.legnth and in the body of the loop used array[i] to access the individual elements of the array.

🔗

for (int i = 0; i < array.length; i++) {
  // whatever with array[i]
}

Now we can apply the same pattern to loop over an ArrayList using list.size() in the loop condition list.get(i) and list.set(i, value) in the body of the loop to access the individual elements of the ArrayList.

🔗

for (int i = 0; i < list.size(); i++) {
  // whatever with list.get(i) and list.set(i, value)
}

Note that even though an ArrayList can grow and shrink via the add and remove methods, the get and set methods still require a valid index, i.e. greater than or equal to 0 and less than the size of the ArrayList. So if we try to use an index that is outside that range, the code will throw an IndexOutOfBoundsException, similar to the ArrayIndexOutOfBoundsException thrown if we use an invalid index in an array access expression..

🔗

Activity 10.3.1.

The following code will throw an IndexOutOfBoundsException. Can you fix it?

🔗

Subsection 10.3.2 Enhanced `for` loop

Also as with arrays, we can use an enhanced for loop to traverse all of the items in an ArrayList when we only care about the values in the list and not their indexes. The type of the loop variable needs to be the same as the type parameter of the ArrayList but if the type parameter is a wrapper class like Integer we can (and usually should) use the primitive type for the loop variable and let auto-unboxing take care of it for us.

🔗

ArrayList<String> strings = new ArrayList<>();
ArrayList<Integer> numbers = new ArrayList<>();

// Loop variable is a String, the element type of strings
for (String s : strings) {
  // do stuff with s
}

// Loop variable is an int, the unboxed version of the element type
for (int n : numbers) {
  // do stuff with n
}

// Less stylish but this also works. n will probably be unboxed as needed in the body
for (Integer n : numbers) {
  // do stuff with n
}

Activity 10.3.2.

What does the following code do? Guess before you run it. Then, add another enhanced for each loop that computes the product of all the elements in numbers by multiplying them. Print out the product after the new loop.

🔗

import java.util.*; // import all classes in this package.

public class Test1
{
    public static void main(String[] args)
    {
        ArrayList<Integer> numbers = new ArrayList<>();
        numbers.add(50);
        numbers.add(30);
        numbers.add(20);

int total = 0;
        for (int value : numbers) {
            total += value;
        }
        System.out.println("Sum of all elements: " + total);

// Write a for-each loop that computes the product
        // of all the elements in numbers and print out the product.

}
}
====

import static org.junit.Assert.*;

import org.junit.*;

import java.io.*;

public class RunestoneTests extends CodeTestHelper
{
    @Test
    public void testExpected() throws IOException
    {
        String output = getMethodOutput("main");
        String expect = "100";
        boolean passed = output.contains(expect);
        getResults(expect, output, "Prints out sum", passed);
        assertTrue(passed);
    }

@Test
    public void testProduct() throws IOException
    {
        String output = getMethodOutput("main");
        String expect = "30000";
        boolean passed = output.contains(expect);
        getResults(expect, output, "Prints out product", passed);
        assertTrue(passed);
    }

@Test
    public void countForLoops()
    {
        String code = removeSpaces(getCode());
        int count = countOccurences(code, "for(int");
        boolean passed = count >= 2;
        getResults("2", count + "", "Number of for each loops", passed);
        assertTrue(passed);
    }
}

🔗

One thing to watch out for with the enhanced for loop is that we can’t add or remove items from an ArrayList while we loop over it. We’ll see in a later section how to write loops that remove items from an ArrayList using a regular for loop, but with an enhanced for loop if the size of an ArrayList changes in any way, such as by a call to add or remove, while it is being looped over, the loop will immediately throw a ConcurrentModificationException.

🔗

Note 10.3.1.

If you’ve been paying very close attention you might wonder how it can be that ArrayList can be a regular class that we could have written ourselves yet it can be used with the special enhanced for loop syntax. The full resolution to that mystery is well beyond the scope of the AP curriculum but it happens that the way the enhanced for loop is defined in terms of an interface that any class can implement and ArrayList is one of the classes that does. So if you wanted to write your own class that you could loop over with an enhanced for loop, you could.

🔗

Activity 10.3.3.

The following has the correct code for the method getScore plus at least one extra unneeded code statement. This method will calculate and return the score for a word game. The code should loop through all of the elements in wordList and if the length of the current word is 3 it should add one to the score, if the length of the word is 4 it should add 2 to the score, and if the length is greater than 4 it should add 3 to the score. The method should return the score. Drag the needed blocks from the left into the correct order on the right. Check your solution by clicking on the Check button. You will be told if any of the blocks are in the wrong order or if you need to remove one or more blocks. There is one extra block that is not needed in a correct solution.

🔗

public static int getScore(ArrayList<String>
                            wordList)
{
---
  int score = 0;
  for (String word : wordList)
  {
---
    if (word.length() == 3)
---
    {
      score++;
    }
---
    else if (word.length() == 4)
    {
      score = score + 2;
    }
---
    else if (word.length() > 4)
    {
      score = score + 3;
    }
---
  } // end for
---
  return score;
} // end method
---
if (word.length == 3) #distractor

🔗

Subsection 10.3.3 `while` loop

And of course we can use a while loop to traverse an ArrayList. If we want to go element by element we’ll have to manage an index variable separately at which point a for loop might make more sense, but if we want to repeatedly modify an ArrayList until some condition is met a while loop can be just the thing. For example this code uses a while loop to remove all the elements from the beginning of an ArrayList, numbers, that are less than 100.

🔗

// numbers is an ArrayList<Integer>

// Loop as long as there are elements in teh list and element 0 is < 100
while (numbers.size() > 0 && numbers.get(0) < 100) {
  // Remove element 0
  numbers.remove(0);
}

After this code runs the list numbers is either empty or starts with a number greater than or equal to 100. There may be numbers less than 100 later in the list but all the ones at the start will have been removed.

🔗

Activity 10.3.4.

The code in this activity demonstrates using while loop and an object-oriented approach where the list is a field of the current object and an instance method rather than a class (static) method loops through the list.

🔗

The code removes all instances of a name from a list. Set the found variable to the appropriate true or false values at line 13 and line 20 to make the code work.

🔗

import java.util.*;
public class ListWorker
{
   private ArrayList<String> nameList;

public ListWorker(ArrayList<String> nameList)
   {
       this.nameList = nameList;
   }

public boolean removeName(String name)
   {
       boolean found =   // true or false?
       int index = 0;
       while (index < nameList.size())
       {
           if (name.equals(nameList.get(index)))
           {
               nameList.remove(index);
               found =    // true or false?
           }
           else
           {
               index++;
           }
       }
       return found;
    }

public static void main(String[] args)
    {
        ArrayList<String> myList = new ArrayList<>();
        myList.add("Amun");
        myList.add("Ethan");
        myList.add("Donnie");
        myList.add("Ethan");
        ListWorker listWorker = new ListWorker(myList);
        System.out.println(listWorker.nameList);
        listWorker.removeName("Ethan");
        System.out.println("After removing Ethan: "
                  + listWorker.nameList);
    }
}
====
import static org.junit.Assert.*;

import org.junit.*;

import java.io.*;

public class RunestoneTests extends CodeTestHelper
{
    @Test
    public void testMain() throws IOException
    {
        String output = getMethodOutput("main");
        String expect = "[Amun, Ethan, Donnie, Ethan]\nAfter removing Ethan: [Amun, Donnie]";
        boolean passed = getResults(expect, output, "Expected output from main");
        assertTrue(passed);
    }
}

🔗

Be careful when you remove items from a list as you loop through it. Notice how the method above only increments the index if an item was not removed from the list. This is because removing an item from a list will shift the remaining items to the left and if you increment the index in all cases you will skip the elements immediately after each element you remove. To see why, consider that those elements will be shifted into the position of the just removed element and if you increment the index, it will move to the next position, skipping the element that used to be at that position. Leaving the index unchanged after a remove allows the shifted-down element to be processed on the next time through the loop.

🔗

Activity 10.3.5.

Assume that nums has been created as an ArrayList object and it initially contains the following Integer values [0, 0, 4, 2, 5, 0, 3, 0]. What will nums contain as a result of executing numQuest?

🔗

ArrayList<Integer> list1 = new ArrayList<>();
private ArrayList<Integer> nums;

// precondition: nums.size() > 0;
// nums contains Integer objects
public void numQuest()
{
   int k = 0;
   Integer zero = new Integer(0);
   while (k < nums.size())
   {
      if (nums.get(k).equals(zero))
         nums.remove(k);
      k++;
   }
}

[0, 4, 2, 5, 3]
Incrementing the index each time through the loop will miss when there are two zeros in a row.
[3, 5, 2, 4, 0, 0, 0, 0]
This would be true if the code moved the zeros to the end, but that is not what it does.
[0, 0, 0, 0, 4, 2, 5, 3]
This would be true if the code moved the zeros to the font, but that is not what it does.
[4, 2, 5, 3]
This would be correct if k was only incremented when an item was not removed from the list.

🔗

You can step through the code above by clicking on the following Example.

🔗

Activity 10.3.6.

The following has the correct code for a method called insertInOrder plus at least one extra unneeded code statement. This method should add the passed name in alphabetic order to a private list field called nameList. Drag the needed blocks from the left into the correct order on the right. Check your solution by clicking on the Check button. You will be told if any of the blocks are in the wrong order or if you need to remove one or more blocks. There is one extra block that is not needed in a correct solution.

🔗

public void insertInOrder(String name)
{
---
  int index = 0;
---
  while (index < nameList.size() &&
     nameList.get(index).compareTo(name)
                             < 0)
  {
---
    index++;
---
  } // end while
---
  nameList.add(index,name);
---
} // end method
---
nameList.add(name); #distractor

🔗

Subsection 10.3.4 Traversing an ArrayList of Student Objects

You can put any kind of objects into an ArrayList. For example, here is an ArrayList of Students. Let’s write some loops that traverse the ArrayList to print out each Student by implicitly calling its toString() method. We’ll also write a method that filters the ArrayList to print out only the students who have a GPA higher than 3.5 for the honor roll.

🔗

Method calls can be chained together like the following:

🔗

// get the name of the 0's student
String name = students.get(0).getName();
// get the GPA of the student at index i
double gpa = students.get(i).getGPA();

Activity 10.3.7.

Write the methods printRoster() and honorRoll() for the ArrayList of Student objects below.

🔗

import java.util.*;

public class Roster
{
    private ArrayList<Student> list = new ArrayList<>();

public Roster()
    {
        list.add(new Student("Skyler", 123456, 3.4));
        list.add(new Student("Ayanna", 234567, 4.0));
        list.add(new Student("Lin", 345678, 3.6));
        list.add(new Student("Sunil", 456789, 3.0));
    }

// Write a method to print the info for each student on the list
    // with each student's info on a new line using a for or for-each loop,
    // implicitly calling the toString() method of the Student class.
    public void printRoster()
    {

}

// Write a honorRoll() method to print the names of students
    // with a GPA greater than 3.5 on the list using an indexed for loop with index i
    // and chaining get(i) with the getGPA() and getName() methods of the Student class.
    public void honorRoll()
    {

}

// main method for testing
    public static void main(String[] args)
    {
        Roster r = new Roster();
        System.out.println("Roster:");
        r.printRoster();
        System.out.println("Honor Roll:");
        r.honorRoll();
    }
}

class Student
{
    private String name;
    private int id;
    private double gpa;

public Student(String name, int id, double gpa)
    {
        this.name = name;
        this.id = id;
        this.gpa = gpa;
    }

// toString() method
    public String toString()
    {
        return id + ": " + name + ": " + gpa;
    }

public String getName()
    {
        return name;
    }

public double getGPA()
    {
        return gpa;
    }

}
====
import static org.junit.Assert.*;

import org.junit.*;

import java.io.*;

public class RunestoneTests extends CodeTestHelper
{
    @Test
    public void testMain() throws IOException
    {
        String output = getMethodOutput("main");
        String expect = "Roster:\n123456: Skyler: 3.4\n234567: Ayanna: 4.0\n345678: Lin: 3.6\n456789: Sunil: 3.0\nHonor Roll:\nAyanna\nLin\n";
        boolean passed = getResults(expect, output, "Expected output from main");
        assertTrue(passed);
    }

@Test
    public void loopCode()
    {
        boolean passed = checkCodeContains("for loop", "for");
        assertTrue(passed);
    }

@Test
    public void chain()
    {
        boolean passed = checkCodeContains("chaining list.get(i).getGPA()", "list.get(i).getGPA()");
        assertTrue(passed);
    }
}

🔗

Subsection 10.3.5 Coding Challenge: FRQ Word Pairs

This challenge is based on the 2018 Free Response Question #2 WordPair. We encourage you to work in pairs on this challenge.

🔗

You are given a class called WordPair that can store pairs of words.

🔗

class WordPair
{
    private String word1;
    private String word2;

    public WordPair(String word1, String word2)
    {
        this.word1 = word1;
        this.word2 = word2;
    }

    public String getFirst()
    {
        return word1;
    }

    public String getSecond()
    {
        return word2;
    }

    public String toString()
    {
        return "(" + word1 + ", " + word2 + ")";
    }
}

First, see if you can create an ArrayList of WordPair objects below. Look at the StudentList example above for help.

🔗

Activity 10.3.8.

Create an Arraylist of WordPair objects.

🔗

import java.util.*;

public class WordPairTest
{
    public static void main(String[] args)
    {
        // Create an ArrayList of WordPair objects called pairs

pairs.add(new WordPair("hi", "there"));
        pairs.add(new WordPair("hi", "bye"));
        System.out.println(pairs);
    }
}

class WordPair
{
    private String word1;
    private String word2;

public WordPair(String word1, String word2)
    {
        this.word1 = word1;
        this.word2 = word2;
    }

public String getFirst()
    {
        return word1;
    }

public String getSecond()
    {
        return word2;
    }

public String toString()
    {
        return "(" + word1 + ", " + word2 + ")";
    }
}
====

import static org.junit.Assert.*;

import org.junit.*;

import java.io.*;

public class RunestoneTests extends CodeTestHelper
{
    public RunestoneTests()
    {
        super("WordPairTest");
    }

@Test
    public void testMain() throws IOException
    {
        String output = getMethodOutput("main");
        String expect = "[(hi, there), (hi, bye)]";
        boolean passed = getResults(expect, output, "Expected output from main");
        assertTrue(passed);
    }

@Test
    public void hasArrayList()
    {
        boolean passed = checkCodeContains("ArrayList declaration", "ArrayList<WordPair>");
        assertTrue(passed);
    }
}

🔗

In this FRQ, you are given an array of words and you will create pairs of them by taking the first word and pairing it with all the other words, then taking the second word and pairing it with all but the first one, and so on. For example, if the word array is [“Hi”, “there”, “Tyler”, “Sam”], this figure shows how the word pairs are formed.

🔗

In the class WordPairsList below, you will write the constructor which takes the array of words and pairs them up as shown in the figure. You will need nested loops to pair each element with the rest of the elements in the list.

🔗

Here is the pseudocode for the constructor method.

🔗

Initialize the allPairs list to an empty ArrayList of WordPair objects.
🔗

🔗
Loop through the words array for the first word in the word pair (for loop from index i = 0 to length-1)
🔗
- Loop through the rest of the word array starting from index i + 1 for the second word in the word pair (for loop from index j = i + 1 to length)
  🔗
  - Add the new WordPair formed from the ith word and the jth word to the allPairs ArrayList.
    🔗
    
    🔗
  🔗
  🔗
🔗
🔗

🔗

Project 10.3.9.

FRQ WordPairs Challenge: Complete the constructor for WordPairsList below which will add pairs of words from a given array to the ArrayList. Then, complete the method numMatches() as described below this exercise.

🔗

import java.util.*;

public class WordPairsList
{
    private ArrayList<WordPair> allPairs;

public WordPairsList(String[] words)
    {
        // WRITE YOUR CODE HERE
        // initialize allPairs to an empty ArrayList of WordPair objects

// nested loops through the words array to add each pair to allPairs

}

public int numMatches()
    {
        // Write the code for the second part described below
        return 0;
    }

public String toString()
    {
        return allPairs.toString();
    }

public static void main(String[] args)
    {
        String[] words = {"Hi", "there", "Tyler", "Sam"};
        WordPairsList list = new WordPairsList(words);
        System.out.println(list);
        // For second part below, uncomment this test:
        // System.out.println("The number of matched pairs is: " +
        // list.numMatches());
    }
}

class WordPair
{
    private String word1;
    private String word2;

public WordPair(String word1, String word2)
    {
        this.word1 = word1;
        this.word2 = word2;
    }

public String getFirst()
    {
        return word1;
    }

public String getSecond()
    {
        return word2;
    }

public String toString()
    {
        return "(" + word1 + ", " + word2 + ")";
    }
}
====

import static org.junit.Assert.*;

import org.junit.*;

import java.io.*;

public class RunestoneTests extends CodeTestHelper
{
    public RunestoneTests()
    {
        super("WordPairsList");
    }

@Test
    public void test1()
    {
        String output = getMethodOutput("main");
        String expect =
                "[(Hi, there), (Hi, Tyler), (Hi, Sam), (there, Tyler), (there, Sam), (Tyler, Sam)]";

boolean passed = output.contains(expect);

String[] lines = output.split("\n");
        if (lines.length > 1) output = lines[0];

getResults(expect, output, "Part 1 - Add all word pairs from main()", passed);
        assertTrue(passed);
    }

/* //remove test because instructions say to add a matched pair.
    @Test
    public void test2()
    {
        String output = getMethodOutput("main");
        String expect = "The number of matched pairs is: 0";

boolean passed = output.contains(expect);
        String[] lines = output.split("\n");
        if (lines.length > 1) output = lines[1];

getResults(expect, output, "Part 2 - call to numMatches from main()", passed);
        assertTrue(passed);
    }
    */

@Test
    public void test3()
    {
        String[] words = {"Hi", "Hi", "Test", "Test"};
        WordPairsList list = new WordPairsList(words);
        String output = list.toString();
        String expect = "[(Hi, Hi), (Hi, Test), (Hi, Test), (Hi, Test), (Hi, Test), (Test, Test)]";

boolean passed =
                getResults(
                        expect,
                        output,
                        "Part 1 - Add all word pairs with {\"Hi\", \"Hi\", \"Test\", \"Test\"}");
        assertTrue(passed);
    }

@Test
    public void test4()
    {
        String[] words = {"Hi", "Hi", "Test", "Test"};
        WordPairsList list = new WordPairsList(words);
        String output = "The number of matched pairs is: " + list.numMatches();
        String expect = "The number of matched pairs is: 2";

boolean passed =
                getResults(
                        expect,
                        output,
                        "Part 2 - numMatches() with {\"Hi\", \"Hi\", \"Test\", \"Test\"}");
        assertTrue(passed);
    }
}

🔗

In the next part of the FRQ challenge, you are asked to write a method called numMatches that counts and returns the number of pairs where the first word is the same as the second word. For example, if the word array is ["hi","bye","hi"], the pairs generated would be ["hi","bye"], ["hi","hi"], and ["bye","hi"]. In the second pair ["hi","hi"], the first word is the same as the second word, so numMatches would return 1.

🔗

For this method, you will need a loop that goes through the ArrayList allPairs and for each WordPair in allPairs, it checks to see if its first word (using the getFirst method) equals the second word (using the getSecond method). If there is a match, it increments a counter which it returns at the end of the method. To test this method, add another “there” into the words array and then uncomment the call to numMatches.

🔗

Subsection 10.3.6 Summary

(AP 4.9.A.1) Traversing an ArrayList is when iteration or recursive statements are used to access all or an ordered sequence of the elements in an ArrayList.
🔗

🔗
ArrayLists can be traversed with an enhanced for loop, a while loop, or a regular for loop using an index.
🔗

🔗
(AP 4.9.A.2) Deleting elements during a traversal of an ArrayList requires the use of special techniques to avoid skipping elements (since remove moves all the elements above the removed index down.)
🔗

🔗
(AP 4.9.A.3) Attempting to access an index value outside of its range will result in an IndexOutOfBoundsException. (The indices for an ArrayList start at 0 and end at the number of elements − 1).
🔗

🔗
(AP 4.9.A.4) Changing the size of an ArrayList while traversing it using an enhanced for loop can result in a ConcurrentModificationException. Therefore, when using an enhanced for loop to traverse an ArrayList, you should not add or remove elements.
🔗

🔗

🔗

You have attempted of activities on this page.

🔗

Prev Top Next

Section 10.3 ArrayList traversals

Subsection 10.3.1 The canonical for loop over an ArrayList

Activity 10.3.1.

Subsection 10.3.2 Enhanced for loop

Activity 10.3.2.

Note 10.3.1.

Activity 10.3.3.

Subsection 10.3.3 while loop

Activity 10.3.4.

Activity 10.3.5.

Activity 10.3.6.

Subsection 10.3.4 Traversing an ArrayList of Student Objects

Activity 10.3.7.

Subsection 10.3.5 Coding Challenge: FRQ Word Pairs

Activity 10.3.8.

Project 10.3.9.

Subsection 10.3.6 Summary

Section 10.3 `ArrayList` traversals

Subsection 10.3.1 The canonical `for` loop over an `ArrayList`

Subsection 10.3.2 Enhanced `for` loop

Subsection 10.3.3 `while` loop