Unit 4: Data Collections

Everything the AP Computer Science A exam can ask about in Unit 4, explained in plain language. This unit is roughly 30–40% of the multiple-choice section and has 17 topics and 71 ideas.

Each idea has a code like 1.2.A.1: the unit, the topic, the learning objective (the letter), then the idea itself. The codes on the practice questions link straight to the idea they tested. These are summaries in our own words. For the exact official wording, see the AP Computer Science A Course and Exam Description.

Topics in this unit

• 4.1 Ethical and Social Issues Around Data Collection
• 4.2 Introduction to Using Data Sets
• 4.3 Array Creation and Access
• 4.4 Array Traversals
• 4.5 Implementing Array Algorithms
• 4.6 Using Text Files
• 4.7 Wrapper Classes
• 4.8 ArrayList Methods
• 4.9 ArrayList Traversals
• 4.10 Implementing ArrayList Algorithms
• 4.11 2D Array Creation and Access
• 4.12 2D Array Traversals
• 4.13 Implementing 2D Array Algorithms
• 4.14 Searching Algorithms
• 4.15 Sorting Algorithms
• 4.16 Recursion
• 4.17 Recursive Searching and Sorting

Topic 4.1: Ethical and Social Issues Around Data Collection

Practice this topic: Topics 4.1–4.2: Data Collection Ethics and Data Sets

4.1.A — Describe how collecting and storing personal data on computers can put people's privacy at risk.

• 4.1.A.1 Using a computer can expose your private information. When you build programs, you should try to protect the privacy of the people who use them.

4.1.B — Explain why you should check the quality of a data set and watch for problems before using it.

• 4.1.B.1 Algorithmic bias means a program keeps making the same kind of mistake in a way that treats one group of users unfairly.
• 4.1.B.2 Before you draw conclusions or predict new things from data, check how that data was collected. The collection method itself might lean toward certain results (bias).
• 4.1.B.3 Some data sets have missing pieces or wrong values. If a program uses data like that, it can give wrong answers or run less efficiently.

4.1.C — Pick a data set that fits the problem you want to solve or the question you want to answer.

• 4.1.C.1 A data set usually fits one particular question or subject. It may not give correct answers, or support predictions, for a different question or subject.

Topic 4.2: Introduction to Using Data Sets

Practice this topic: Topics 4.1–4.2: Data Collection Ethics and Data Sets

4.2.A — Show a pattern or process that works with everyday data sets by using written steps or a diagram.

• 4.2.A.1 A data set is simply a group of related pieces of information, such as a list of test scores.
• 4.2.A.2 Programs answer questions about data by going through it and handling the values one at a time, then using what they find to reach the result.
• 4.2.A.3 You can draw data as a chart or table. That picture helps you plan the steps (the algorithm) you will use to work with the data.

Topic 4.3: Array Creation and Access

Practice this topic: Topics 4.3–4.5: Array Creation, Traversal, and Algorithms

4.3.A — Write code that uses 1D arrays to store a group of related values.

• 4.3.A.1 An array holds many values that are all the same type. Those values can be primitive values (like int) or references to objects.
• 4.3.A.2 An array's size is fixed when you create it, and it can never grow or shrink. You read the size with the length attribute (no parentheses), as in arr.length.
• 4.3.A.3 When you create an array with new, every element starts with a default value for its type.
  • int starts at 0.
  • double starts at 0.0.
  • boolean starts at false.
  • Reference types (like String) start at null.
• 4.3.A.4 An initializer list lets you create an array and fill it with starting values in one step, such as int[] nums = {4, 7, 9};.
• 4.3.A.5 You use square brackets [] with an index (a position number) to read or change one element of a 1D array, such as arr[2] = 5;.
• 4.3.A.6 Valid indexes run from 0 up to the array's length minus 1, including both ends. Any index outside that range causes an ArrayIndexOutOfBoundsException (an error that stops your program).

Topic 4.4: Array Traversals

Practice this topic: Topics 4.3–4.5: Array Creation, Traversal, and Algorithms

4.4.A — Write code that loops through the elements of a 1D array, and predict what the loop produces.

• 4.4.A.1 Traversing an array means using a loop to visit every element, or a set of elements in order, one after another.
• 4.4.A.2 When you loop with a regular for loop that uses a counter, or with a while loop, you reach each element through its index, like arr[i].
• 4.4.A.3 An enhanced for loop declares a loop variable. On each pass, that variable gets a copy of the next element, and you never use an index.
• 4.4.A.4 Changing the enhanced for loop variable only changes your copy. The value inside the array stays the same.
• 4.4.A.5 If the array holds object references, you can call methods on the loop variable to change that object's attributes. The array still refers to the same objects as before.
• 4.4.A.6 An enhanced for loop traversal is never the only way to do it: you can get the same result with a while loop, or with a regular for loop that steps through the indexes.

Topic 4.5: Implementing Array Algorithms

Practice this topic: Topics 4.3–4.5: Array Creation, Traversal, and Algorithms

4.5.A — Write array code for standard or new algorithms that fit a given task, and predict the results of running them.

• 4.5.A.1 These jobs come up again and again when you loop through an array:
  • Find the smallest or largest value.
  • Add up the values or find their average.
  • Check whether at least one element meets some condition.
  • Check whether every element meets it.
  • Count how many elements meet it.
  • Compare each element with the one next to it (every consecutive pair).
  • Find out whether the same value shows up more than once.
  • Shift elements left or right, or rotate them so the ends wrap around.
  • Flip the array so the order is reversed.

Topic 4.6: Using Text Files

Practice this topic: Topics 4.6–4.7: Text Files and Wrapper Classes

4.6.A — Write code that reads data from a text file.

• 4.6.A.1 A file stores data even when your program is not running. Your program can load that data while it runs.
• 4.6.A.2 To bring a file into your program, you use the File class together with the Scanner class.
• 4.6.A.3 You open a file by making a File object and passing the file's name to the constructor.
  • File(String str) builds a File for reading, where str is the path (the location and name) of the file.
• 4.6.A.4 Opening a file can fail, for example when the name is wrong, and Java requires your code to deal with that possibility. One simple way is to add throws IOException to the declaration line of any method that touches the file. If the name is invalid, the program stops running.
• 4.6.A.5 File and IOException live in the java.io package, so you need an import statement before your program can use them.
• 4.6.A.6 You get these Scanner tools, with their descriptions, on the exam reference sheet.
  • Scanner(File f) builds a Scanner that reads from a File.
  • int nextInt() gives the next int if there is one. If it is missing or out of range, you get an InputMismatchException.
  • double nextDouble() gives the next double. If there is none, you get an InputMismatchException.
  • boolean nextBoolean() gives the next boolean. If there is none, you get an InputMismatchException.
  • String nextLine() gives the next whole line as a String. It can give an empty String if you call it right after another Scanner read method.
  • String next() gives the next String (one word, up to whitespace).
  • boolean hasNext() is true if something is left to read, and false if not.
  • void close() closes the Scanner. Reading keyboard input is not covered.
• 4.6.A.7 If you mix nextLine with the other Scanner methods on the same source, you may need extra code because they treat whitespace (spaces and line breaks) differently. Writing or analyzing code that mixes them is not covered.
• 4.6.A.8 You get this extra String method on the exam reference sheet.
  • String[] split(String del) gives a String array of the pieces you get when you cut the String wherever del matches. The del value is a regular expression, but using its special features (like * or .) is not covered.
• 4.6.A.9 To keep reading until a file runs out of data, use a while loop whose condition is hasNext().
• 4.6.A.10 Close the file when you are done with it. You do that by calling the Scanner method close.

Topic 4.7: Wrapper Classes

Practice this topic: Topics 4.6–4.7: Text Files and Wrapper Classes

4.7.A — Write code that converts between int and Integer or double and Double, and predict what happens when you use these objects.

• 4.7.A.1 Integer and Double are wrapper classes (object versions of int and double) in the java.lang package. Both are immutable, so once you create one of these objects, its value can never be changed.
• 4.7.A.2 Autoboxing is when Java automatically turns a primitive into its wrapper object, such as int into Integer or double into Double. It happens when you pass a primitive to a method that expects the wrapper type, and when you assign a primitive to a variable of the wrapper type.
• 4.7.A.3 Unboxing is the reverse: Java automatically turns a wrapper object back into a primitive, such as Integer into int or Double into double. It happens when you pass the object to a method that expects the primitive, and when you assign it to a primitive variable.
• 4.7.A.4 You get this Integer method on the exam reference sheet.
  • static int parseInt(String s) turns the String you give it into an int.
• 4.7.A.5 You get this Double method on the exam reference sheet.
  • static double parseDouble(String s) turns the String you give it into a double.

Topic 4.8: ArrayList Methods

Practice this topic: Topics 4.8–4.10: ArrayList Methods, Traversals, and Algorithms

4.8.A — Write code that stores related objects in an ArrayList, and predict what happens when you call its methods.

• 4.8.A.1 An ArrayList can grow and shrink while your program runs, unlike an array. It holds references to objects, not raw primitive values.
• 4.8.A.2 Writing new ArrayList() with nothing in the parentheses gives you a brand new list that has no elements in it yet.
• 4.8.A.3 You can tell an ArrayList what kind of thing it stores using angle brackets, like ArrayList<String>. Here E stands for that element type, and the list's methods then take and return that type. This form is better than a plain ArrayList because the compiler (the tool that checks your code before it runs) can catch type mistakes early instead of your program crashing later. Example: ArrayList<String> names = new ArrayList<String>();
• 4.8.A.4 ArrayList lives in a package (a group of related classes) called java.util. Before you can use it, you need an import statement at the top of your file.
• 4.8.A.5 You get these ArrayList methods on the exam reference sheet, so know what each one does and when to use it.
  • int size() tells you how many elements the list holds.
  • boolean add(E obj) puts obj at the very end and returns true.
  • void add(int index, E obj) puts obj at position index (from 0 up to size), slides everything from that spot onward one place to the right, and makes the list one bigger.
  • E get(int index) gives you the element at position index.
  • E set(int index, E obj) swaps obj into position index and returns the element that used to be there.
  • E remove(int index) takes out the element at index, slides everything after it one place to the left, makes the list one smaller, and returns the removed element.
• 4.8.A.6 The first element of an ArrayList is at index 0. The last element is at index size() - 1.

Topic 4.9: ArrayList Traversals

Practice this topic: Topics 4.8–4.10: ArrayList Methods, Traversals, and Algorithms

4.9.A — Write loops that go through the elements of an ArrayList, and predict what those loops produce.

• 4.9.A.1 To traverse an ArrayList means to visit its elements one by one using a loop or recursion. You can visit every element, or just a certain run of them in order.
• 4.9.A.2 If you remove items while looping through an ArrayList, the remaining items shift down and your loop can jump over one. You need a careful approach, such as adjusting the index or looping backward.
• 4.9.A.3 Using an index that is below 0 or at/above size() on an ArrayList makes the program throw an IndexOutOfBoundsException.
• 4.9.A.4 If an enhanced for loop is walking through an ArrayList and the list's size changes, Java can throw a ConcurrentModificationException. So do not add or remove elements inside that kind of loop.

Topic 4.10: Implementing ArrayList Algorithms

Practice this topic: Topics 4.8–4.10: ArrayList Methods, Traversals, and Algorithms

4.10.A — Write and trace standard or custom algorithms that work on ArrayList objects to meet a given goal.

• 4.10.A.1 Many common tasks on an ArrayList are done by traversing it with a loop. Typical ones are:
  • finding the smallest or largest value
  • adding up values or finding an average
  • checking whether at least one element meets a condition
  • checking whether every element meets a condition
  • counting how many elements meet a condition
  • looking at each pair of neighboring elements
  • checking whether any value appears more than once
  • shifting or rotating elements left or right
  • reversing the order
  • inserting new elements
  • deleting elements
• 4.10.A.2 Some tasks need you to walk through two or more collections at once, such as two String objects, two arrays, or two ArrayList objects, moving along each as you go.

Topic 4.11: 2D Array Creation and Access

Practice this topic: Topics 4.11–4.13: 2D Arrays

4.11.A — Write code that uses 2D arrays to hold related data arranged in rows and columns.

• 4.11.A.1 A 2D array is really an array whose elements are themselves arrays, so making and indexing one works much like a 1D array. Its size is fixed when you create it. It can hold primitives or object references. Rows with different lengths (nonrectangular arrays) are not something you need to know.
• 4.11.A.2 When you create a 2D array with new, every spot starts with a default value for its type. That is 0 for int, 0.0 for double, false for boolean, and null for any reference type.
• 4.11.A.3 You can create and fill a 2D array in one step with an initializer list: curly braces containing one smaller curly-brace list for each row. For example, int[][] grid = { {7, 8, 9}, {1, 2, 3} }; makes a 2D array with 2 rows and 3 columns.
• 4.11.A.4 Use two sets of square brackets, [row][col], to read or change one element of a 2D array. In arr[first][second], the first number picks the row and the second picks the column.
• 4.11.A.5 If you write the 2D array's name with just one pair of brackets holding a row number, such as arr[2], you get that whole row, which is a 1D array.
• 4.11.A.6 Use length to find sizes in a 2D array.
  • The number of rows is the array's own length, and valid row indices run from 0 to that number minus 1.
  • The number of columns is the length of any one row, and valid column indices run from 0 to that number minus 1.
  • For an array named values, rows are values.length and columns are values[0].length.
  • Using an index outside these ranges causes an ArrayIndexOutOfBoundsException.

Topic 4.12: 2D Array Traversals

Practice this topic: Topics 4.11–4.13: 2D Arrays

4.12.A — Write nested loops that visit the elements of a 2D array, and predict what they produce.

• 4.12.A.1 You walk through a 2D array with nested loops, a loop inside a loop, using regular for or enhanced for, much like with a 1D array. You can go in row-major order (across each row, one row after another), column-major order (down each column, one column after another), or some other custom order.
• 4.12.A.2 In a nested enhanced for loop over a 2D array, the outer loop goes through the rows, so its variable must be a 1D array type. The inner loop goes through one row, so its variable must match the element type. Changing the loop variable does not change what is stored in the array.

Topic 4.13: Implementing 2D Array Algorithms

Practice this topic: Topics 4.11–4.13: 2D Arrays

4.13.A — Write and trace standard or custom algorithms that use 2D arrays to meet a given goal.

• 4.13.A.1 Common 2D array tasks use nested traversals, either over the whole array or over just one row, column, or other section. They include:
  • finding the smallest or largest value
  • adding up values or finding an average
  • checking whether at least one element meets a condition
  • checking whether every element meets a condition
  • counting how many elements meet a condition
  • looking at each pair of neighboring elements
  • checking whether any value appears more than once
  • shifting or rotating elements along a row (left or right) or a column (up or down)
  • reversing the order of a row or column

Topic 4.14: Searching Algorithms

Practice this topic: Topics 4.14–4.17: Searching, Sorting, and Recursion

4.14.A — Write linear search code to look for a value in a collection, and predict the outcome of a search.

• 4.14.A.1 A linear search looks at elements one at a time, in order, and stops when it finds the target or runs out of elements. It works on arrays and ArrayList objects, and it can start from either the front or the back.
• 4.14.A.2 To linear search a 2D array, go to each row in turn and run a linear search on that row.

Topic 4.15: Sorting Algorithms

Practice this topic: Topics 4.14–4.17: Searching, Sorting, and Recursion

4.15.A — Trace each step that selection sort and insertion sort take while sorting a collection.

• 4.15.A.1 Selection sort and insertion sort both use loops (they are iterative) and can sort the elements of an array or an ArrayList.
• 4.15.A.2 Selection sort looks through the part that is not yet sorted, picks the smallest value (or the largest), and swaps it into its spot in the sorted part. Once placed, that value is in its final position.
• 4.15.A.3 Insertion sort takes the next value from the unsorted part and slides it into the sorted part, shifting other sorted values over to make space. That spot is right for now, but later insertions can still move it.

Topic 4.16: Recursion

Practice this topic: Topics 4.14–4.17: Searching, Sorting, and Recursion

4.16.A — Trace recursive method calls and work out what value they produce.

• 4.16.A.1 A recursive method calls itself. To avoid running forever, it needs a base case (a situation where it stops without calling itself again) and a recursive case, which is where it calls itself. Recursion is one more way to get repetition, similar to a loop.
• 4.16.A.2 Every recursive call gets its own separate copy of local variables, including parameters. The parameter values show how far along the process is, the way a loop variable does in a loop.
• 4.16.A.3 Anything you can solve with recursion can also be solved with a loop, and the reverse is true too. You do not need to write recursive code yourself, only understand what it does.

Topic 4.17: Recursive Searching and Sorting

Practice this topic: Topics 4.14–4.17: Searching, Sorting, and Recursion

4.17.A — Trace recursive algorithms that work on strings or collections and find their results.

• 4.17.A.1 You can use recursion to go through a String, an array, or an ArrayList, handling one piece and then making a recursive call on the rest.

4.17.B — Trace each round of a binary search through a sorted collection and see what it does.

• 4.17.B.1 Binary search only works if the data is already sorted. It begins at the middle of the array or ArrayList, then throws away half of what is left with each recursive call, until it finds the target or has no elements left.
• 4.17.B.2 Binary search usually finds things faster than linear search. Other search algorithms besides these two are not something you need to know.
• 4.17.B.3 You can write binary search with a loop (iteratively) or with recursion, and both ways give the same result.

4.17.C — Trace each stage of merge sort as it sorts a collection.

• 4.17.C.1 Merge sort is a recursive way to sort an array or ArrayList. Sorting methods beyond selection, insertion, and merge sort are not something you need to know.
• 4.17.C.2 Merge sort keeps splitting the array into smaller pieces until each piece has just one element. Then it merges those pieces back together, recursively, keeping them in order, until you have one fully sorted array.