Arrays & ArrayList Lab

Arrays store elements in contiguous memory with fixed size. Access any element by index in O(1) time.

// Declare and initialize
int[] arr = {3, 7, 1, 9, 4};

// Access element
int x = arr[2];  // x = 1

// Traverse
for (int i = 0; i < arr.length; i++) {
    System.out.println(arr[i]);
}

Array length is fixed after creation. To resize, you must create a new array and copy elements.

Linear search checks each element sequentially: O(n). Binary search halves the search space each step: O(log n), but requires a sorted array.

// Binary search (array must be sorted)
int low = 0, high = arr.length - 1;
while (low <= high) {
    int mid = (low + high) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
}
return -1;  // Not found

Selection sort finds the minimum and swaps it to the front. Insertion sort builds the sorted portion by inserting each element into its correct position. Both are O(n²) but insertion sort can be faster on nearly sorted data.

// Selection sort
for (int i = 0; i < arr.length - 1; i++) {
    int minIdx = i;
    for (int j = i + 1; j < arr.length; j++) {
        if (arr[j] < arr[minIdx]) minIdx = j;
    }
    int temp = arr[i];
    arr[i] = arr[minIdx];
    arr[minIdx] = temp;
}

2D arrays are arrays of arrays. Row-major traversal visits all columns in each row before moving to the next row. ArrayList is a resizable array with built-in methods for add, remove, set, and get.

// 2D array traversal (row-major)
for (int r = 0; r < grid.length; r++) {
    for (int c = 0; c < grid[r].length; c++) {
        System.out.print(grid[r][c]);
    }
}

// ArrayList
ArrayList<Integer> list = new ArrayList<>();
list.add(10);       // [10]
list.add(0, 5);     // [5, 10]
list.remove(1);     // [5]
list.set(0, 99);    // [99]