Parallel lists: two lists, one logical record.
When the same index in two lists holds related data, every operation must keep both lists synchronized.
Parallel lists are two (or more) ArrayLists where index i in each list belongs to the same logical entity. Names at index i of one list match the scores at index i of another.
The search-or-add pattern is the canonical use: look for a key in the first list; if found, update the second list at the matched index; if not, append to both. Examples: tally votes per candidate, accumulate points per player, count occurrences of distinct words.
On the AP exam, parallel-list FRQs require careful index tracking — every operation must preserve the alignment between the lists.
Search the key list; act on the same index in the value list.
Add to both lists together; never one without the other.
The template
public void recordScore(ArrayList<String> names,
ArrayList<Integer> scores,
String name, int points) {
int i = -1;
for (int j = 0; j < names.size(); j++) {
if (names.get(j).equals(name)) {
i = j;
}
}
if (i == -1) {
// not found — append to both
names.add(name);
scores.add(points);
} else {
// found — update score at matched index
scores.set(i, scores.get(i) + points);
}
}The synchronization rule
Every structural change to one list must be mirrored in the other. Adding to names means adding to scores. Removing from one means removing from the other at the same index. Otherwise the lists fall out of alignment and every later index becomes wrong.
Why set for updates
When the key is already present, the score list's size stays the same — only the value at one index changes. set is the right tool because it replaces in place without shifting.
Order of additions matters
For a new entry, add to both lists in the same order so they end up with the same size at the same indices. Adding to one and forgetting the other is the classic parallel-list bug.
Avoid the temptation to "fix" later
Don't rely on a later cleanup pass to re-align. Fix synchronization at every operation. AP graders look for this discipline.
Parallel-list vocabulary.
Used in tally and per-key tracking problems.
- Parallel lists — two or more lists aligned by index.
- Key list — the list searched against (e.g., names, ids).
- Value list — the list whose elements get updated.
- Search-or-add — find the key; if absent, append to both.
- Synchronization — keeping the lists aligned through every operation.
- Tally — running count of how many times a key has appeared.
How parallel-list problems are tested.
Synchronization slips and missed not-found branches dominate.
What FRQ graders check:
- Both branches handled. Found → update; not found → append to both.
- Both lists modified together. Never just one.
- String equality with
.equals(). Lookups on text-based keys. - Correct accumulator.
scores.set(i, scores.get(i) + points), notscores.set(i, points).
MCQ patterns to expect: tracing the contents of both lists after several calls; spotting code that adds to only one list.
Tally votes across multiple calls.
Watch both lists grow and update in lockstep.
Setup. Two parallel lists: candidates (names) and votes (counts). Both start empty.
recordScore(candidates, votes, "Alex", 1);
recordScore(candidates, votes, "Ben", 1);
recordScore(candidates, votes, "Alex", 1);
recordScore(candidates, votes, "Cara", 1);
recordScore(candidates, votes, "Ben", 1);Trace.
- Call 1: "Alex" not found. Append both.
candidates=[Alex],votes=[1]. - Call 2: "Ben" not found. Append both.
candidates=[Alex, Ben],votes=[1, 1]. - Call 3: "Alex" found at index 0. Update:
votes=[2, 1]. - Call 4: "Cara" not found. Append both.
candidates=[Alex, Ben, Cara],votes=[2, 1, 1]. - Call 5: "Ben" found at index 1. Update:
votes=[2, 2, 1].
Final. candidates=[Alex, Ben, Cara], votes=[2, 2, 1]. Lists stay the same size; index i in each refers to the same logical candidate.
Why this matters. Every "new key" call grew both lists by exactly one. Every "existing key" call updated votes only. The synchronization rule was followed at every step.
Parallel-list pitfalls.
All come from desynchronizing the lists.
- Adding to only one list. The next call's lookup may match the wrong index.
- Removing from only one list. Same alignment problem.
- Replacing instead of accumulating.
scores.set(i, points)resets the count instead of adding to it. - Missing the not-found branch. New names never get added; their points are lost.
- Wrong key comparison. Using
==for Strings instead of.equals(). - Sorting one list independently. Breaks alignment; reorder both together or not at all.
Search-or-add at a glance.
Two branches; one rule.
Parallel List Reference
AP Quick Reference| Outcome | Action on key list | Action on value list |
|---|---|---|
Key found at index i |
No change | set(i, get(i) + delta) |
| Key not found (i == -1) | add(key) |
add(initialValue) |
| Sizes after any operation | Equal to value list | Equal to key list |
| Lookup comparison | .equals() for Strings |
n/a |
| Synchronization rule | Always together | Always together |
How to master parallel lists.
After every operation, verify both lists have the same size.
Use the three practice tools below this lesson in order:
- MCQ Practice — for each option, check whether both lists are modified together. If only one changes structurally, suspect a sync bug.
- Java Lab — implement vote-tallying or word-counting using parallel lists. Print both after every call to verify alignment.
- FRQ Practice — write the lookup, then the if/else, then the two paired modifications. Treat each pair as a single atomic step.
If you reflexively check "same size?" after every operation, your parallel lists will never go out of sync.
Practice — attempt these now.
AP-style assessments aligned to this lesson. Time them.