Static Arrays

Arrays are the most fundamental data structure in computer science. They store elements in contiguous memory, enabling constant-time access to any element by index.

What is a Static Array?

A static array is a fixed-size collection of elements stored in consecutive memory locations. When you create a static array, you specify its size upfront, and that size cannot change.

// Static array with 5 elements
let arr: [i32; 5] = [10, 20, 30, 40, 50];
//                   ^    ^    ^    ^    ^
//                  [0]  [1]  [2]  [3]  [4]

In Rust, array size is part of the type: [i32; 5] is different from [i32; 6].

Memory Layout

Static arrays store elements contiguously in memory. If each integer is 4 bytes and the array starts at address 0x1000:

Index:    [0]      [1]      [2]      [3]      [4]
Address:  0x1000   0x1004   0x1008   0x100C   0x1010
          +--------+--------+--------+--------+--------+
Value:    |   10   |   20   |   30   |   40   |   50   |
          +--------+--------+--------+--------+--------+

To find element arr[i], we calculate: base_address + (i * element_size)

For arr[3]: 0x1000 + (3 * 4) = 0x100C

This formula works for any index, making access O(1).

Basic Operations

Reading: O(1)

Reading any element takes constant time. We compute the address and read directly.

fn read(arr: &[i32], index: usize) -> i32 {
    arr[index]  // O(1)
}

fn main() {
    let arr = [10, 20, 30, 40, 50];
    let value = read(&arr, 3);  // Returns 40
    println!("{}", value);
}

Writing: O(1)

Overwriting an existing element is also O(1).

fn write(arr: &mut [i32], index: usize, value: i32) {
    arr[index] = value;  // O(1)
}

fn main() {
    let mut arr = [10, 20, 30, 40, 50];
    write(&mut arr, 2, 99);  // arr is now [10, 20, 99, 40, 50]
    println!("{:?}", arr);
}

Insertion at End: O(1)

If there's space at the end, appending is O(1).

// Array with capacity 6, currently holding 5 elements
// [10, 20, 30, 40, 50, _]
//                      ^ empty slot

fn append(arr: &mut [i32], length: usize, value: i32) -> usize {
    arr[length] = value;
    length + 1
}

fn main() {
    let mut arr = [10, 20, 30, 40, 50, 0];
    let length = append(&mut arr, 5, 60);  // [10, 20, 30, 40, 50, 60]
    println!("{:?}, length: {}", arr, length);
}

Insertion at Beginning or Middle: O(n)

To insert at position i, we must shift all elements from i to the end.

// Insert 15 at index 1
// Before: [10, 20, 30, 40, 50, _]
// After:  [10, 15, 20, 30, 40, 50]

fn insert(arr: &mut [i32], index: usize, value: i32, length: usize) -> usize {
    // Shift elements to the right
    for i in (index..length).rev() {
        arr[i + 1] = arr[i];
    }
    arr[index] = value;
    length + 1
}

fn main() {
    let mut arr = [10, 20, 30, 40, 50, 0];
    let length = insert(&mut arr, 1, 15, 5);
    println!("{:?}", &arr[..length]);  // [10, 15, 20, 30, 40, 50]
}

We shift n - index elements, making this O(n) in the worst case (inserting at index 0).

Deletion at End: O(1)

Removing the last element is O(1)—just decrement the length.

fn pop(arr: &[i32], length: usize) -> (i32, usize) {
    (arr[length - 1], length - 1)
}

fn main() {
    let arr = [10, 20, 30, 40, 50];
    let (value, new_len) = pop(&arr, 5);  // Returns (50, 4)
    println!("Popped: {}, new length: {}", value, new_len);
}

Deletion at Beginning or Middle: O(n)

Removing from position i requires shifting elements left.

// Delete element at index 1
// Before: [10, 20, 30, 40, 50]
// After:  [10, 30, 40, 50]

fn delete(arr: &mut [i32], index: usize, length: usize) -> usize {
    // Shift elements to the left
    for i in index..length - 1 {
        arr[i] = arr[i + 1];
    }
    length - 1
}

fn main() {
    let mut arr = [10, 20, 30, 40, 50];
    let length = delete(&mut arr, 1, 5);
    println!("{:?}", &arr[..length]);  // [10, 30, 40, 50]
}

Time Complexity Summary

| Operation | Time Complexity | |-----------|-----------------| | Access by index | O(1) | | Update by index | O(1) | | Insert at end | O(1) | | Insert at beginning | O(n) | | Insert at middle | O(n) | | Delete at end | O(1) | | Delete at beginning | O(n) | | Delete at middle | O(n) | | Search (unsorted) | O(n) | | Search (sorted) | O(log n) |

Searching in Arrays

Linear Search: O(n)

Check each element until you find the target.

fn linear_search(arr: &[i32], target: i32) -> Option<usize> {
    for i in 0..arr.len() {
        if arr[i] == target {
            return Some(i);
        }
    }
    None  // Not found
}

fn main() {
    let arr = [10, 20, 30, 40, 50];
    match linear_search(&arr, 30) {
        Some(idx) => println!("Found at index {}", idx),
        None => println!("Not found"),
    }
}

Binary Search: O(log n)

For sorted arrays, repeatedly halve the search space.

fn binary_search(arr: &[i32], target: i32) -> Option<usize> {
    let mut left = 0;
    let mut right = arr.len();

    while left < right {
        let mid = left + (right - left) / 2;
        if arr[mid] == target {
            return Some(mid);
        } else if arr[mid] < target {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    None  // Not found
}

fn main() {
    let arr = [10, 20, 30, 40, 50];
    match binary_search(&arr, 40) {
        Some(idx) => println!("Found at index {}", idx),
        None => println!("Not found"),
    }
}

Advantages of Static Arrays

1. O(1) random access: Calculate address and read directly
2. Cache-friendly: Contiguous memory means CPU caches work efficiently
3. Low memory overhead: No extra pointers, just the data itself
4. Simple implementation: Direct mapping from index to memory

Disadvantages of Static Arrays

1. Fixed size: Cannot grow or shrink after creation
2. Expensive insertions/deletions: O(n) for middle operations
3. Memory waste: If you allocate more than needed, space is wasted
4. Memory shortage: If you allocate less than needed, you're stuck

When to Use Static Arrays

• You know the exact number of elements in advance
• You need fast random access (O(1) reads by index)
• Memory is constrained and you can't afford overhead
• You're doing mostly reads and updates, not insertions/deletions

Common Patterns

Traversal

fn main() {
    let arr = [10, 20, 30, 40, 50];

    // Forward traversal
    for i in 0..arr.len() {
        println!("{}", arr[i]);
    }

    // Backward traversal
    for i in (0..arr.len()).rev() {
        println!("{}", arr[i]);
    }

    // Iterator style
    for &value in arr.iter() {
        println!("{}", value);
    }
}

Two-Pointer Technique

fn is_palindrome(arr: &[i32]) -> bool {
    let mut left = 0;
    let mut right = arr.len().saturating_sub(1);

    while left < right {
        if arr[left] != arr[right] {
            return false;
        }
        left += 1;
        right -= 1;
    }
    true
}

fn main() {
    let arr = [1, 2, 3, 2, 1];
    println!("Is palindrome: {}", is_palindrome(&arr));  // true
}

Prefix Sum

fn build_prefix_sum(arr: &[i32]) -> Vec<i32> {
    let mut prefix = vec![0; arr.len() + 1];
    for i in 0..arr.len() {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    prefix
}

fn range_sum(prefix: &[i32], left: usize, right: usize) -> i32 {
    prefix[right + 1] - prefix[left]
}

fn main() {
    let arr = [1, 2, 3, 4, 5];
    let prefix = build_prefix_sum(&arr);

    // Sum from index 1 to 3 (inclusive)
    println!("Sum [1..3]: {}", range_sum(&prefix, 1, 3));  // 9
}

Key Takeaways

1. Static arrays have fixed size determined at creation
2. Contiguous memory enables O(1) access by index
3. Insertions and deletions in the middle are O(n) due to shifting
4. Cache-friendly due to sequential memory access
5. Foundation for many other data structures (heaps, hash tables)

Static arrays are the building block upon which dynamic arrays, strings, and many other structures are built. Understanding their memory layout and operation costs is essential for choosing the right data structure for your problem.