Array Indexing, Manipulation, and Traversal in Java

1

OUT-OF-BOUNDS INDEXES The indexes that are legal to access in an array are those in the range of 0 to the The indexes that are legal to access in an array are those in the range of 0 to the array's length array's length - - 1. 1. Reading or writing any index outside this range will throw an ArrayIndexOutOfBoundsException. Example: Example: int[] data = new int[10]; System.out.println(data[0]); // okay System.out.println(data[-1]); // exception System.out.println(data[9]); // okay System.out.println(data[10]); // exception index 0 1 2 3 4 5 6 7 8 9 value 0 0 0 0 0 0 0 0 0 0 2 2

THE ARRAYS CLASS The The Arrays class in package manipulating arrays: manipulating arrays: class in package java.util has several useful static methods for has several useful static methods for Method name binarySearch(array, value) Description returns the index of the given value in this array (< 0 if not found) returns true if the two given arrays contain exactly the same elements in the same order sets every element in the array to have the given value arranges the elements in the array into ascending order returns a string representing the array, such as "[10, 30, 17]" equals(array1, array2) fill(array, value) sort(array) toString(array) 3 3

ARRAYS.TOSTRING The The Arrays.toString method is useful when you want to print an array's elements. method is useful when you want to print an array's elements. Arrays.toString accepts an array as a parameter and returns the String representation, which you can then print. Example: int[] a = {2, 5, 1, 6, 14, 7, 9}; for (int i = 1; i < a.length; i++) { a[i] += a[i - 1]; } System.out.println("a is " + Arrays.toString(a)); Output: a is [2, 7, 8, 14, 28, 35, 44] 4 4

ARRAY TRAVERSAL traversal: An examination of each element of an array. An examination of each element of an array. traversal: Traversal algorithms often take the following form: for (int i = 0; i < <array> do something with <array> } <array>.length; i++) { <array> [i]; Traversals are useful in many situations: Traversals are useful in many situations: printing the elements of an array searching an array for a specific value rearranging the elements of an array computing the sum, product, etc. of an array's elements ... 5 5

PRINTING ARRAY ELEMENTS Example (print each element of an array on a line): Example (print each element of an array on a line): int[] myarray = {4, 1, 9, 7}; for (int i = 0; i < myarray.length; i++) { System.out.println(i + ": " + myarray[i]); } Output: 0: 4 1: 1 2: 9 3: 7 How How could we change the code to print the following? could we change the code to print the following? 4, 1, 9, 7 (Do not use Arrays.toString.) 6 6

EXAMINING ARRAY ELEMENTS Example (find the largest even integer in an array Example (find the largest even integer in an array): ): int[] list = {4, 1, 2, 7, 6, 3, 2, 4, 0, 9}; int largestEven = 0; for (int i = 0; i < list.length; i++) { if (list[i] % 2 == 0 && list[i] > largestEven) { largestEven = list[i]; } } System.out.println("Largest even: " + largestEven); Output: Largest even: 6 7 7

STRING TRAVERSAL Strings are like arrays of s are like arrays of chars; they also use 0 We can write algorithms to traverse strings to compute information: // string stores voters' votes // (R)epublican, (D)emocrat, (I)ndependent String votes = "RDRDRRIDRRRDDDDIRRRDRRRDIDIDDRDDRRDRDIDD"; int[] counts = new int[3]; // R -> 0, D -> 1, I -> 2 for (int i = 0; i < votes.length(); i++) { char c = votes.charAt(i); if (c == 'R') { counts[0]++; } else if (c == 'D') { counts[1]++; } else { // c == 'I') counts[2]++; } } System.out.println(Arrays.toString(counts)); Output: [17, 18, 5] s; they also use 0- -based indexes. based indexes. 8 8

OUTPUT PARAMETERS output parameter: An array or object passed as a parameter that has its contents altered by the output parameter: An array or object passed as a parameter that has its contents altered by the method. method. We can pass in an array to a method and the method can change its contents in useful ways for us. Examples: The methods Arrays.fill and Arrays.sort. int[] nums = {4, -1, 2, 7, 3, 6}; System.out.println(Arrays.toString(nums)); Arrays.sort(nums); // modifies contents of nums System.out.println(Arrays.toString(nums)); Arrays.fill(nums, 42); System.out.println(Arrays.toString(nums)); Output: [4, -1, 2, 7, 3, 6] [-1, 2, 3, 4, 6, 7] [42, 42, 42, 42, 42, 42] 9 9

ARRAYS AS RETURN VALUES An array can also be returned from a method. An array can also be returned from a method. Syntax (declaration): public static <type> <type>[] <name> <name>(<parameters> <parameters>) { Example: public static int[] readAllNumbers(Scanner input) { Syntax (call): <type> <type>[] <name> <name> = <method name> <method name>(<parameters> <parameters>); Example: Scanner fileScan = new Scanner(new File("temp.dat")); int[] numbers = readAllNumbers(fileScan); 10 10

ARRAY RETURN EXAMPLE Example (digit Example (digit- -counting problem from an earlier slide): counting problem from an earlier slide): public static int[] countDigits(int n) { int[] counts = new int[10]; while (n > 0) { int digit = n % 10; n = n / 10; counts[digit]++; } return counts; } public static void main(String[] args) { int number = 229231007; int[] tally = countDigits(number); System.out.println(Arrays.toString(tally)); } Output: [2, 1, 3, 1, 0, 0, 0, 1, 0, 1] 11 11

STRING METHODS WITH ARRAYS These These String methods return arrays: methods return arrays: String s = "long book"; Method name toCharArray() Description separates this string into an array of its characters Example s.toCharArray() returns {'l', 'o', 'n', 'g', ' ', 'b', 'o', 'o', 'k'} s.split(" ") returns {"long", "book"} split(delimiter) separates this string into substrings by the given delimiting string s.split("o") returns {"l", "ng b", "", "k"} 12 12

STRING/ARRAY PROBLEMS Write a method named Write a method named areAnagrams that accepts two whether those strings contain the same letters (in any order whether those strings contain the same letters (in any order). ). areAnagrams("bear", "bare") returns true areAnagrams("sale", "sail") returns false Use the methods from the previous slide, as well as any relevant methods from the Arrays class. that accepts two Strings as parameters and returns s as parameters and returns Write a method named Write a method named wordCount that accepts a number of words in that string. Words are separated by spaces. number of words in that string. Words are separated by spaces. that accepts a String as its parameter and returns the as its parameter and returns the wordCount("the quick brown fox") returns 4 Use the methods from the previous slide. 13 13

14

CONCEPT OF AN ARRAY ROTATION Imagine we want to 'rotate' the elements of an array; that is, to shift them left by one index. Imagine we want to 'rotate' the elements of an array; that is, to shift them left by one index. The element that used to be at index 0 will move to the last slot in the array. For example, {3, 8, 9, 7, 5} becomes {8, 9, 7, 5, 3}. Before: index 0 1 2 3 4 After: value 3 8 9 7 5 Shifting elements is useful when inserting and removing values from arrays after they have already been filled with data. index 0 1 2 3 4 value 8 9 7 5 3 15 15

SHIFTING ELEMENTS LEFT A left shift of the elements of an array: A left shift of the elements of an array: index 0 1 2 3 4 value 3 8 9 7 5 index 0 1 2 3 4 Let's write the code to do the left shift. Let's write the code to do the left shift. Can we generalize it so that it will work on an array of any size? Can we write a right-shift as well? value 8 9 7 5 3 16 16

SHIFTING PRACTICE PROBLEM Write a method Write a method insertInOrder that accepts a sorted array parameters, and inserts parameters, and inserts n n into into a a while maintaining sorted order In other words, assume that the element values in In other words, assume that the element values in a a occur in sorted ascending order, and insert the new value n into the array at the appropriate index, shifting to make room if necessary. The the new value n into the array at the appropriate index, shifting to make room if necessary. The last element in the array will be lost after the insertion. last element in the array will be lost after the insertion. that accepts a sorted array a a of integers and an integer value of integers and an integer value n n as while maintaining sorted order. . occur in sorted ascending order, and insert as Example: calling insertInOrder on array {1, 3, 7, 10, 12, 15, 22, 47, 74} and value 11 produces {1, 3, 7, 10, 11, 12, 15, 22, 47}. 17 17