Lesson on Arrays in Java
Introduction
- Arrays are fundamental data structures in Java that allow storing multiple elements of the same type under a single variable.
- They provide a convenient way to work with collections of data efficiently.
Array Creation and Access
- Use of Array Objects: Arrays allow multiple related items to be represented using a single variable.
- Fixed Size: The size of an array is established at the time of creation and cannot be changed.
- Initialization: Arrays are created using the
new
keyword, and their elements are initialized with specific values based on the type of element. Elements of reference type are initialized to the reference valuenull
. - ArrayIndexOutOfBoundsException: Accessing elements outside the bounds of the array leads to this exception.
public class ArrayExceptionExample {
public static void main(String[] args) {
int[] numbers = {1, 2, 3, 4, 5};
// accessing element out of bounds of array
int indexOutOfRange = numbers[10]; // this will throw the error
}
}
ArrayExceptionExample.main(null);
---------------------------------------------------------------------------
java.lang.ArrayIndexOutOfBoundsException: Index 10 out of bounds for length 5
at ArrayExceptionExample.main(#12:6)
at .(#13:1)
import java.util.Random;
public class Array {
public static void main(String[] args) {
// creating array of integers with size 5
int[] numbers = new int[5];
// generating random values and assigning them to elements of the array
Random random = new Random();
for (int i = 0; i < numbers.length; i++) {
numbers[i] = random.nextInt(100); // random integers are between 0 and 99
}
// accessing and printing elements of the array
for (int i = 0; i < numbers.length; i++) {
System.out.println("Element at index " + i + ": " + numbers[i]);
}
}
}
Array.main(null);
Element at index 0: 18
Element at index 1: 21
Element at index 2: 1
Element at index 3: 57
Element at index 4: 15
Traversing Arrays
- Iteration Statements: Iteration statements like
for
orwhile
loops are used to access all elements in an array. - Indexed Access: Traversing an array with an indexed
for
loop orwhile
loop requires accessing elements using their indices.
Enhanced for loop for Arrays
- Syntax: An enhanced
for
loop header includes a variable that iterates over each element in the array. - Element Access: During each iteration, the enhanced
for
loop variable is assigned a copy of an element without using its index. - Immutability: Modifying the enhanced
for
loop variable does not change the value stored in the array. - Flexibility: Program code using an enhanced
for
loop for array traversal can be rewritten using an indexedfor
loop or awhile
loop.
public class ArrayTraversal {
public static void main(String[] args) {
// creating integer array
int[] numbers = {10, 20, 30, 40, 50};
// traversing array with for loop
System.out.println("Traversing the array using a for loop:");
for (int i = 0; i < numbers.length; i++) {
System.out.println("Element at index " + i + ": " + numbers[i]);
}
// traversing array with enhanced for loop
System.out.println("\nTraversing the array using an enhanced for loop:");
for (int num : numbers) {
System.out.println("Element: " + num);
}
}
}
ArrayTraversal.main(null);
Traversing the array using a for loop:
Element at index 0: 10
Element at index 1: 20
Element at index 2: 30
Element at index 3: 40
Element at index 4: 50
Traversing the array using an enhanced for loop:
Element: 10
Element: 20
Element: 30
Element: 40
Element: 50
FRQ Tip for Developing Algorithms Using Arrays
Be familiar with certain algorithms that are likely to come on the exam:
-
Determine the minimum or maximum value in an array
-
Compute a sum, average, or mode of array elements
-
Search for a particular element in the array
-
Determine if at least one element has a particular property
-
Determine if all elements have a particular property
-
Access all consecutive pairs of elements
-
Determine the presence or absence of duplicate elements
-
Determine the number of elements meeting specific criteria
-
Shift or rotate elements left or right
-
Reverse the order of the elements
SAMPLE FRQ PART: 2019 Question 3
A string containing text and possibly delimiters has been split into tokens and stored in String[] tokens. Each token is either an open delimiter, a close delimiter, or a substring that is not a delimiter. You will write the method getDelimitersList, which returns an ArrayList containing all the open and close delimiters found in tokens in their original order.
Complete method getDelimitersList below:
public ArrayList<String> getDelimitersList (String[] tokens){
ArrayList<String> delimeters = new ArrayList<String>();
for(int i = 0; i < tokens.length; i++){
if(tokens[i].equals(openDel) || tokens[i].equals(closeDel)){
delimeters.add(tokens[i]);
}
}
return delimeters;
}
GIVEN SOLUTION
public ArrayList<String> getDelimitersList(String[] tokens)
{
// creating a new ArrayList to store delimiter tokens
ArrayList<String> d = new ArrayList<String>();
// use enhanced for loop to iterate through each token in the provided array
for (String str : tokens)
{
// check if current token is equal to the specified open delimiter or close delimiter
if (str.equals(openDel) || str.equals(closeDel))
{
// if token is delimiter, add to arraylist
d.add(str);
}
}
// return arraylist with delimiter tokens
return d;
}
SCORING CRITERIA
- Create the ArrayList
- Accesses all elements in array tokens without any bound errors.
- Compares strings in tokens with both instance variables which must be in the context of a loop.
- Adds delimiters into ArrayList in original order.
HACKS
PART A: How does the use of an array simplify the management of related data compared to individual variables?
Using an array to manage related data allows us to hold multiple values of the same type (ex. integers or strings) under a single variable name. Arrays also enable scalable and memory-efficient management of very large data sets. Furthermore, arrays also enhances code readability and maintainability by grouping related elements under one variable name rather (more readable than just defining multiple individual variables).
PART B: Develop an algorithm to find the median value of an integer array WITHOUT sorting the array.
public class Algorithm {
public static int findMedian(int[] nums) {
int n = nums.length;
if (n % 2 == 1) {
return quickselect(nums, 0, n - 1, n / 2);
} else {
int mid1 = quickselect(nums, 0, n - 1, n / 2 - 1);
int mid2 = quickselect(nums, 0, n - 1, n / 2);
return (mid1 + mid2) / 2;
}
}
private static int quickselect(int[] nums, int low, int high, int k) {
if (low == high) {
return nums[low];
}
int pivotIndex = partition(nums, low, high);
if (k == pivotIndex) {
return nums[k];
} else if (k < pivotIndex) {
return quickselect(nums, low, pivotIndex - 1, k);
} else {
return quickselect(nums, pivotIndex + 1, high, k);
}
}
private static int partition(int[] nums, int low, int high) {
int pivot = nums[high];
int i = low;
for (int j = low; j < high; j++) {
if (nums[j] <= pivot) {
swap(nums, i, j);
i++;
}
}
swap(nums, i, high);
return i;
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public static void main(String[] args) {
int[] nums = {7, 2, 1, 6, 8, 5, 3, 4};
int median = findMedian(nums);
System.out.println("Median: " + median);
}
}
Algorithm.main(null);
Median: 4