Crash Course — Unit 4: Data Collections

• 1D Array
  €” A fixed-size, ordered collection of elements all of the same type. Think of it as a numbered row of mailboxes; once built, you can't add more boxes.
• ArrayList
  €” A resizable, ordered collection of objects. It's like a magical, stretching binder that can hold different types of pages (as long as they're objects) and grow as needed.
• Array vs. ArrayList
  €” The most critical distinction in this unit. Arrays are static in size and can hold primitives; ArrayLists are dynamic and hold objects only.
• Traversal
  €” The process of visiting every element in a collection, usually with a for loop or for-each loop, to perform some operation like printing or calculating a sum.
• Wrapper Classes (Integer, Double) — These turn primitive values (int, double) into objects so they can be stored in an ArrayList.
• 2D Array
  €” A "grid" or "table" of data, essentially an array of arrays. Perfect for representing a tic-tac-toe board, a spreadsheet, or seating chart for a concert in Chicago.
• Standard Algorithms
  €” Common tasks you'll perform on collections, like finding the min/max, calculating the sum/average, or checking if an element exists.
• Linear Search
  €” A straightforward search that checks every single element from the beginning until it finds what it's looking for. It's simple, but can be slow.
• Binary Search
  €” A super-efficient "divide and conquer" search that only works on sorted data. It repeatedly checks the middle element to narrow down the search area.
• Selection Sort
  €” An algorithm that sorts an array by repeatedly finding the smallest remaining element and swapping it into its correct position.
• Insertion Sort
  €” An algorithm that builds a sorted list one element at a time, by taking the next item and "inserting" it into its proper place among the already-sorted items.
• Recursion
  €” A problem-solving technique where a method calls itself to solve smaller, identical versions of the problem, until it reaches a simple "base case" it can solve directly.

Key Formulas / Terms

• 1D Array Creation:

  // Creates an array of 50 integers, all initialized to 0.
  int[] scores = new int[50];
  // Creates and initializes an array in one step.
  String[] names = {"Priya", "Carlos", "Aaliyah"};

• Standard for Loop Traversal (for arrays and ArrayLists):

  // Use when you need the index, `i`.
  for (int i = 0; i < arr.length; i++) {
      // Access element with arr[i]
  }
  for (int i = 0; i < list.size(); i++) {
      // Access element with list.get(i)
  }

• Enhanced for-each Loop Traversal (for arrays and ArrayLists):

  // Use when you just need the element, not its index.
  for (double price : prices) {
      // Use the element `price` directly
  }

• Key ArrayList Methods:

  list.add(element);       // Adds to the end
  list.add(index, element); // Inserts at an index
  list.get(index);         // Retrieves an element
  list.set(index, element); // Replaces an element
  list.remove(index);      // Removes an element
  list.size();             // Gets the number of elements

• 2D Array Traversal (Row-Major Order):

  // Processes the grid row by row.
  for (int row = 0; row < grid.length; row++) {
      for (int col = 0; col < grid[row].length; col++) {
          // Access element with grid[row][col]
      }
  }

Exam Traps

• Trap
  Off-by-one errors in loops. The exam loves testing if you'll write i <= scores.length, which causes an ArrayIndexOutOfBoundsException because the last valid index is length - 1. · Counter: Burn this into your memory: array and ArrayList indices run from 0 to size - 1. Your loop condition must always be i < array.length or i < list.size().
• Trap
  Mixing up array.length and list.size(). Using myArray.length() or myList.size will result in a compiler error and a lost point on an FRQ. · Counter: array.length is a property (like a stat on a baseball card). list.size() is a method call (an action). Say it out loud: "array dot length, list dot size parenthesis."
• Trap
  Trying to create an ArrayList of primitives, like ArrayList<int>. The compiler won't allow this. · Counter: Remember that ArrayLists only hold objects. You must use the corresponding wrapper class: ArrayList<Integer>, ArrayList<Double>, etc.
• Trap
  Modifying an ArrayList while traversing it with a standard for loop. If you remove an element, all subsequent elements shift left, and your loop might skip the very next element. · Counter: If you must remove elements during a traversal, the safest way is to loop backward. Start at i = list.size() - 1 and go down to 0. That way, removing an element doesn't affect the indices of the elements you haven't visited yet.
• Trap
  Applying binary search to an unsorted array. The algorithm will run, but it will produce an incorrect result. · Counter: Binary search has one non-negotiable prerequisite: the data must be sorted. If a problem description doesn't guarantee the array is sorted, you must assume it isn't and use linear search.