Array Operations

Why This Matters

Arrays are the backbone of nearly every program you'll write, and understanding their operations is fundamental to success in Programming Languages I. You're being tested on more than just syntax—examiners want to see that you understand time complexity, memory management, and when to choose one operation over another. These concepts connect directly to algorithm efficiency, data structure selection, and writing code that scales.

When you encounter array problems, think about the underlying principles: constant-time access, linear-time searches, in-place vs. copy operations, and fixed vs. dynamic sizing. Don't just memorize how to write a for-loop—know why accessing arr[5] is instant while finding a value requires scanning the entire array. This conceptual understanding is what separates students who ace FRQs from those who struggle.

---

Basic Array Mechanics

These foundational operations establish how arrays work in memory. Arrays store elements in contiguous memory locations, which is why index-based access is so fast—the computer calculates the exact memory address using simple arithmetic.

Array Creation and Initialization

• Declaration syntax varies by language—Java uses int[] arr = new int[5];, Python uses arr = [0] * 5, but the concept of allocating fixed space remains constant
• Default values fill uninitialized slots—integers default to $0$, booleans to false, and object references to null
• Initialization timing matters—you can declare now and populate later, but the array size is locked at creation in most languages

Array Length/Size

• Fixed size at creation is the defining constraint of basic arrays—this is why dynamic structures like ArrayLists exist
• Length property access is $O(1)$—the size is stored as metadata, not calculated each time (arr.length in Java, len(arr) in Python)
• Off-by-one errors stem from forgetting that valid indices run from $0$ to $length - 1$, not $1$ to $length$

---

Element Access and Modification

These operations leverage the core strength of arrays: direct access to any element via index calculation, making read and write operations constant time regardless of array size.

Accessing Array Elements

• Zero-based indexing means arr[0] is the first element—this convention exists because the index represents the offset from the starting memory address
• $O(1)$ time complexity for access is arrays' superpower—the address is calculated as $base + (index \times element\_size)$
• Out-of-bounds access throws runtime exceptions (ArrayIndexOutOfBoundsException in Java)—always validate indices before access

Modifying Array Elements

• Direct assignment updates in place—arr[2] = 42; changes the original array without creating copies
• No shifting required for modification—unlike insertion or deletion, changing a value at an index is instant
• Immutability considerations—some languages or contexts treat arrays as immutable, requiring new array creation instead

---

Traversal and Iteration

Iteration patterns let you process every element systematically. The choice between loop types affects both readability and what operations you can perform—index-based loops allow modification, while enhanced for-loops prioritize simplicity.

Iterating Through Arrays

• For-loops with index variables give full control—for (int i = 0; i < arr.length; i++) lets you access, modify, and track position
• Enhanced for-loops simplify read-only traversal—for (int x : arr) in Java or for x in arr in Python
• Time complexity is $O(n)$ for full traversal—you must visit each element once, making this linear regardless of loop style

Multi-Dimensional Arrays

• Arrays of arrays create grid structures—int[][] matrix = new int[3][4]; creates 3 rows with 4 columns each
• Multiple indices required for access—matrix[row][col] where the first index selects the sub-array, the second selects the element
• Nested loops for traversal—outer loop iterates rows, inner loop iterates columns, resulting in $O(rows \times cols)$ complexity

---

Array Manipulation Operations

These operations create new arrays or modify existing ones in bulk. Understanding whether an operation modifies in place or returns a copy is critical for predicting program behavior and avoiding bugs.

Array Slicing

• Creates a new sub-array from specified indices—arr.slice(1, 4) in JavaScript returns elements at indices 1, 2, and 3 (end index is exclusive)
• Original array unchanged—slicing is a non-destructive operation, important for preserving source data
• Language-specific syntax varies—Python uses arr[1:4], Java requires manual copying or Arrays.copyOfRange()

Array Concatenation

• Combines multiple arrays into a single new array—arr1.concat(arr2) in JavaScript, arr1 + arr2 in Python
• Returns a new array rather than modifying originals—both source arrays remain intact after concatenation
• Time complexity is $O(n + m)$ where $n$ and $m$ are the lengths of the arrays being combined

---

Search and Sort Operations

These algorithms transform how quickly you can find and organize data. The key insight is that sorting has upfront cost but enables faster searching—a classic time-space tradeoff.

Searching Arrays

• Linear search is $O(n)$—check each element sequentially until found; works on any array but scales poorly
• Binary search is $O(\log n)$—repeatedly halve the search space, but requires a sorted array as a precondition
• Built-in methods like indexOf() typically use linear search—know what's happening under the hood

Sorting Arrays

• Arranges elements in order (ascending/descending) to enable efficient searching and organized output
• Algorithm complexity varies—bubble sort is $O(n^2)$, while quicksort and mergesort average $O(n \log n)$
• Built-in sort methods (like Arrays.sort() in Java) use optimized algorithms—use them unless asked to implement manually

---

Quick Reference Table

---

Self-Check Questions

1. Which two operations share $O(1)$ time complexity, and why does the array's memory structure make this possible?

2. Compare linear search and binary search: under what conditions would you choose each, and what's the prerequisite for using binary search?

3. If you need to extract elements 2-5 from an array and later combine them with another array, which operations would you use? Do either modify the original?

4. A 2D array has 4 rows and 6 columns. How many total iterations occur when traversing it with nested loops, and what's the time complexity in Big-O notation?

5. FRQ-style: Given an unsorted array that will be searched 1,000 times, explain whether you should sort it first. Include the relevant time complexities in your reasoning.