Previous Topic

What Is an Array?

An array is a sequence of elements stored in contiguous memory and addressed by integer indices. Arrays are among the most fundamental data structures in programming, enabling fast random access, efficient iteration, and compact representation of homogeneous data.

Key Properties

• Fixed order: elements are stored and visited in a consistent order.
• Contiguous memory: elements are placed back-to-back, improving cache locality.
• Uniform type: typically all elements share the same type (or uniform-sized references).
• Indexed access: retrieve or update by index in constant time.

Indexing and Memory Layout

Most languages use zero-based indexing, meaning the first element is at index 0. The address of element i is computed from the base address plus i times the element size. This arithmetic makes arr[i] an O(1) operation.

For multidimensional arrays, memory can be organized in row-major order (C, C++, Java) or column-major order (Fortran, MATLAB). Some languages implement multidimensional arrays as arrays of arrays (“jagged arrays”), where inner rows can have different lengths.

Common Operations and Complexity

• Access by index: O(1)
• Search (unsorted): O(n)
• Binary search (sorted): O(log n)
• Insert/delete at end: Static arrays: not possible if full; Dynamic arrays: amortized O(1) append, O(1) pop
• Insert/delete in middle: O(n) due to shifting elements
• Iteration: O(n)
• Resize (dynamic arrays): occasional O(n) reallocation/copy; amortized O(1) per append with geometric growth

Static vs. Dynamic Arrays

• Static arrays: size fixed at allocation time; common in low-level languages (e.g., C) and for performance-critical code. Efficient and compact, but cannot grow.
• Dynamic arrays: grow automatically by allocating a larger block and copying elements when capacity is exceeded (e.g., Python lists, Java ArrayList, C++ std::vector, JavaScript arrays). They offer amortized O(1) append with occasional O(n) resize operations.

Multidimensional, Rectangular, and Jagged

• Rectangular arrays: all rows have equal length; suitable for matrices.
• Jagged arrays: an array of arrays where inner lengths may differ; more flexible structure and memory usage tailored to each row.

Common Patterns

• Two pointers: move indices from ends or at different speeds for tasks like partitioning, removing duplicates, or cycle detection.
• Sliding window: maintain a subarray range to compute running metrics (sums, counts) in O(n).
• Prefix sums: precompute cumulative totals for O(1) range queries.
• In-place transforms: reverse, rotate, partition without extra memory.

Language Notes and Examples

The syntax and semantics vary by language, but the core ideas hold.

# Python (dynamic array: list)
arr = [10, 20, 30]
arr[1] = 25
arr.append(40)      # amortized O(1)
arr.insert(1, 15)   # O(n)
del arr[2]          # O(n)
for x in arr:
    print(x)

# Copying vs referencing
alias = arr          # references same list
copy1 = arr.copy()   # shallow copy
copy2 = arr[:]       # shallow copy

// JavaScript (dynamic array)
const arr = [10, 20, 30];
arr[1] = 25;
arr.push(40);            // amortized O(1)
arr.splice(1, 0, 15);    // insert at index 1, O(n)
arr.splice(2, 1);        // delete at index 2, O(n)

// Copying vs referencing
const alias = arr;             // same underlying array
const copy = arr.slice();      // shallow copy
const copy2 = [...arr];        // shallow copy

// Java (static arrays and ArrayList)
int[] arr = new int[]{10, 20, 30};
arr[1] = 25;
for (int x : arr) {
    System.out.println(x);
}

// Dynamic behavior with ArrayList
import java.util.*;
List<Integer> list = new ArrayList<>(Arrays.asList(10, 20, 30));
list.add(40);          // amortized O(1)
list.add(1, 15);       // O(n)
list.remove(2);        // O(n)

/* C (static array) */
#include <stdio.h>

int main(void) {
    int arr[5] = {10, 20, 30, 40, 50};
    arr[1] = 25;
    size_t n = sizeof(arr) / sizeof(arr[0]);
    for (size_t i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

Pitfalls and Best Practices

• Bounds: Accessing out-of-range indices causes undefined behavior in C/C++, exceptions in Java/Python, and returns undefined in JavaScript.
• Off-by-one errors: Pay attention to inclusive vs exclusive boundaries and zero-based indexing.
• Copy vs alias: Assignments may create references to the same array; use explicit copy when needed.
• Mutability: Some arrays or slices are mutable; be cautious when sharing references.
• Performance: Prefer appending at the end; minimize inserts/deletes in the middle; exploit contiguous memory for better cache performance.

When to Use Arrays

• When you need fast random access and predictable layout.
• When the number of elements is known or grows primarily at the end.
• When performance-critical code benefits from cache locality.
• Consider alternatives when frequent middle insertions/deletions (linked lists, balanced trees) or key-based lookups (hash tables, maps) are primary operations.

Next Topic