Array algorithms and ArrayList

You know how to create and traverse an array. This week covers the standard jobs done with it: searching, counting, reversing, copying, shifting. They are all patterns of a few lines, and they come up again and again as “write a method” questions on the exam. In the second half you will learn ArrayList, which solves the size problem of arrays.

Golden rules:

1. A search returns as soon as it finds the key; if it does not, -1 after the loop.
2. In an in-place reversal the loop goes only halfway: i < length / 2.
3. b = a is not a copy. For a copy, create a new array.
4. In ArrayList the size is size(), the element is get(i). No square brackets.
5. If you delete elements in a loop, go from the end to the start.

Linear search and counting

public static int linearSearch(int[] arr, int key) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == key) return i;     // found it, leave immediately
    }
    return -1;                           // never found
}
public static int count(int[] arr, int key) {
    int c = 0;
    for (int x : arr) if (x == key) c++;
    return c;
}
// in main:
int[] a = {8, 3, 5, 3, 1};
System.out.println(linearSearch(a, 3) + " " + linearSearch(a, 1) + " " + linearSearch(a, 7));
System.out.println(count(a, 3));

1 4 -1
2

-1 is not a valid index, so it is used to mean “not found”. The return -1 line must be outside the loop. If you put it in an else inside, you only check the first element.

Reversing in place

Swap the first with the last, then the second with the second from the end, up to the middle.

public static void reverse(int[] arr) {
    for (int i = 0; i < arr.length / 2; i++) {
        int temp = arr[i];
        arr[i] = arr[arr.length - 1 - i];
        arr[arr.length - 1 - i] = temp;
    }
}

For {1, 2, 3, 4, 5} and {1, 2, 3, 4}:

[5, 4, 3, 2, 1]
[4, 3, 2, 1]

i   indexes swapped          array (5 elements)
0   0 ↔ 4                    [5, 2, 3, 4, 1]
1   1 ↔ 3                    [5, 4, 3, 2, 1]
2   loop ends (2 < 5/2 = 2 is false), the middle 3 stays in place

PITFALL · going all the way to the end. If you make the loop i < arr.length, it reverses in the first half and reverses back in the second half. In verification this version left the array as [1, 2, 3, 4, 5], that is, unchanged.

Copy and alias

int[] orig = {1, 2, 3};
int[] alias = orig;                              // the same array
int[] real = copy(orig);                         // a copy made with a loop
int[] c2 = Arrays.copyOf(orig, orig.length);     // a ready-made copy
orig[0] = 99;
System.out.println(alias[0] + " " + real[0] + " " + c2[0]);
System.out.println((orig == alias) + " " + (orig == real));
int[] x1 = {1, 2}, x2 = {1, 2};
System.out.println((x1 == x2) + " " + Arrays.equals(x1, x2));

99 1 1
true false
false true

A copy with a loop is written like this:

public static int[] copy(int[] arr) {
    int[] result = new int[arr.length];
    for (int i = 0; i < arr.length; i++) result[i] = arr[i];
    return result;
}

With arrays, == does not look at the contents; it looks at whether two variables point to the same array. For content comparison use Arrays.equals (or your own loop).

Sorted? Shifting. Sorting.

public static boolean isSorted(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {     // length-1 because we use i+1
        if (arr[i] > arr[i + 1]) return false;
    }
    return true;
}
public static void shiftLeft(int[] arr) {          // rotate left
    int first = arr[0];
    for (int i = 0; i < arr.length - 1; i++) arr[i] = arr[i + 1];
    arr[arr.length - 1] = first;
}

isSorted({1, 3, 3, 7}), isSorted({1, 5, 2}), shiftLeft({10, 20, 30, 40}) and Arrays.sort({5, 2, 9, 1}):

true false
[20, 30, 40, 10]
[1, 2, 5, 9]

TIP · if you see i + 1, lower the bound. If you use arr[i + 1] in the loop, the last iteration must be i = length - 2, otherwise you go outside the array in the last iteration. The condition is i < arr.length - 1.

ArrayList: an array whose size can change

The size of an array is fixed from the start. If you do not know how many elements will come (read numbers until the user enters -1, delete elements from a list), you use ArrayList. It grows and shrinks by itself.

import java.util.ArrayList;

ArrayList<String> names = new ArrayList<>();
names.add("Ali");
names.add("Can");
names.add("Ece");
System.out.println(names + " " + names.size());
names.add(1, "Bora");          // insert at index 1, the rest shifts
System.out.println(names);
System.out.println(names.get(2));
names.set(0, "Arda");          // replace
System.out.println(names);
names.remove(3);               // delete by index
System.out.println(names);
names.remove("Bora");          // delete by value
System.out.println(names);
System.out.println(names.contains("Can") + " " + names.indexOf("Can") + " " + names.indexOf("Zeynep"));
System.out.println(names.isEmpty());

[Ali, Can, Ece] 3
[Ali, Bora, Can, Ece]
Can
[Arda, Bora, Can, Ece]
[Arda, Bora, Can]
[Arda, Can]
true 1 -1
false

If you call get with an invalid index it crashes: IndexOutOfBoundsException: Index 1 out of bounds for length 1.

Wrapper classes and autoboxing

ArrayList holds only objects, not primitives. ArrayList<int> does not compile (unexpected type). Every primitive has a wrapper class: int → Integer, double → Double, char → Character, boolean → Boolean. Java does the conversion between them by itself (autoboxing / unboxing):

ArrayList<Integer> nums = new ArrayList<>();
for (int i = 1; i <= 5; i++) nums.add(i * 10);     // int → Integer automatically
System.out.println(nums);
nums.remove(1);                                    // INDEX 1
System.out.println(nums);
nums.remove(Integer.valueOf(40));                  // VALUE 40
System.out.println(nums);
int first = nums.get(0);                           // Integer → int automatically
System.out.println(first + 1);
for (int i = 0; i < nums.size(); i++) System.out.print(nums.get(i) + " ");

[10, 20, 30, 40, 50]
[10, 30, 40, 50]
[10, 30, 50]
11
10 30 50 

PITFALL · remove(1) or remove(value)? In an Integer list, remove(1) takes an int argument, so it deletes index 1. If you want to delete the value 1, write remove(Integer.valueOf(1)). In a String list there is no confusion: remove("Bora") deletes the value.

Deleting in a loop

ArrayList<Integer> list = new ArrayList<>(Arrays.asList(2, 4, 5, 6, 7));
for (int i = 0; i < list.size(); i++) {
    if (list.get(i) % 2 == 0) list.remove(i);      // from the start: WRONG
}
System.out.println(list);
ArrayList<Integer> list2 = new ArrayList<>(Arrays.asList(2, 4, 5, 6, 7));
for (int i = list2.size() - 1; i >= 0; i--) {
    if (list2.get(i) % 2 == 0) list2.remove(i);    // from the end: CORRECT
}
System.out.println(list2);

[4, 5, 7]
[5, 7]

When going from the start, after 2 is deleted, 4 shifted to index zero, but because i moved on to 1, 4 was never checked. If you go from the end, the elements to the right of a deleted element have already been checked.

Common mistakes

int[] a = {4, 7, 4, 2, 4};
System.out.println(linearSearch(a, 4) + " " + count(a, 4) + " " + linearSearch(a, 9));

int[] a = {1, 2, 3, 4, 5, 6};
for (int i = 0; i < a.length / 2; i++) {
    int t = a[i];
    a[i] = a[a.length - 1 - i];
    a[a.length - 1 - i] = t;
}
System.out.println(a[0] + " " + a[2] + " " + a[5]);

int[] a = {3, 6, 9};
int[] b = a;
int[] c = Arrays.copyOf(a, 3);
b[0] = 0;
c[1] = 0;
System.out.println(a[0] + " " + a[1]);

int[] a = {1, 2, 3, 4, 5};
for (int i = 0; i < a.length - 1; i++) a[i] = a[i + 1];
System.out.println(Arrays.toString(a));

ArrayList<String> list = new ArrayList<>();
list.add("x");
list.add("y");
list.add(0, "z");
list.add("w");
list.set(2, "v");
System.out.println(list + " " + list.size());

ArrayList<Integer> list = new ArrayList<>();
list.add(5); list.add(10); list.add(15); list.add(20);
list.remove(1);
list.remove(Integer.valueOf(20));
System.out.println(list);

ArrayList<Integer> list = new ArrayList<>(Arrays.asList(3, 3, 3, 8));
for (int i = 0; i < list.size(); i++) {
    if (list.get(i) == 3) list.remove(i);
}
System.out.println(list);

ArrayList<String> list = new ArrayList<>(Arrays.asList("cat", "dog", "cow"));
int total = 0;
for (String s : list) if (s.startsWith("c")) total += s.length();
System.out.println(total + " " + list.indexOf("cow") + " " + list.contains("Dog"));

int[] a = {2, 8, 5};
System.out.println(isSorted(a));
Arrays.sort(a);
System.out.println(isSorted(a) + " " + a[1]);

int[] a = {1, 2, 3};
int[] b = {1, 2, 3};
System.out.println((a == b) + " " + Arrays.equals(a, b));