Array Basics

What Is an Array?

An array is a collection of elements of the same type, stored in a contiguous block of memory and accessible by an index. Arrays provide fast random access to elements and are one of the most widely used data structures in computing.

Why Arrays Matter

• Performance: Constant-time (O(1)) random access by index.
• Predictable layout: Contiguous memory improves cache locality.
• Foundation: Many structures (strings, matrices, dynamic arrays, hash tables, heaps) build on arrays.

Core Properties

• Homogeneous elements: All elements share the same type (or size) in most languages.
• Indexing: Typically zero-based (0..n-1), though some languages use one-based indexing (1..n).
• Size: Fixed-length arrays have a size determined at creation; dynamic arrays (array lists) can grow/shrink by resizing under the hood.
• Contiguity: Elements are stored back-to-back in memory, enabling pointer arithmetic and fast traversal.

Creating and Accessing

// Pseudocode
let a = new Array of length 5
// Initialize
for i from 0 to 4:
  a[i] = 0

// Access and update
x = a[2]        // read
a[2] = x + 10   // write

Accessing or updating an element by index is O(1). Accessing outside the valid range (e.g., a[-1] or a[n]) is an out-of-bounds error.

Iteration Patterns

// Index-based loop
for i from 0 to n-1:
  visit(a[i])

// Enhanced/for-each (conceptual)
for value in a:
  visit(value)

Sequential iteration is cache-friendly and typically very fast.

Common Operations and Complexity

• Read/Write by index: O(1)
• Search (unsorted): O(n) linear scan
• Search (sorted with binary search): O(log n)
• Insert/Delete at end (dynamic array): Amortized O(1)
• Insert/Delete at start or middle: O(n), due to shifting elements
• Resize (dynamic arrays): Occasional O(n) copy when capacity grows
• Slicing: Often O(k) to copy k elements; some systems provide O(1) “views” that reference the same data

Fixed vs. Dynamic Arrays

• Fixed-length arrays: Size set at creation; memory is a contiguous block. Efficient but inflexible.
• Dynamic arrays: Backed by a fixed array that resizes (typically doubling capacity) when full. Append is amortized O(1); occasional O(n) resize.

Multidimensional Arrays

• True multidimensional (contiguous): A 2D array stored in row-major (rows contiguous) or column-major (columns contiguous) order.
• Array of arrays (jagged): Each row is its own array; rows can have different lengths.

// 2D indexing (row, col)
value = m[r][c]

// Traversal (row-major friendly)
for r from 0 to R-1:
  for c from 0 to C-1:
    visit(m[r][c])

For performance-sensitive code, align traversal with memory layout (row-major vs. column-major) to maximize cache locality.

Copying, Aliasing, and Mutability

• Shallow copy: Copies references to elements (or the top-level container) without duplicating nested data.
• Deep copy: Recursively duplicates all nested structures.
• Aliasing: Two variables can refer to the same array; changes through one name are visible through the other.

// Aliasing example
b = a       // b and a refer to the same array
b[0] = 42   // a[0] is now 42 as well

Common Pitfalls

• Off-by-one errors: Remember valid indices are typically 0..n-1.
• Out-of-bounds access: Can throw errors or cause undefined behavior.
• Incorrect assumptions about copying: Know whether operations create views or copies.
• Costly mid-array insertions/deletions: Prefer data structures optimized for these operations when needed.

Practical Examples

// Sum all elements
sum = 0
for i from 0 to n-1:
  sum += a[i]

// Reverse in-place
left = 0
right = n - 1
while left < right:
  swap(a[left], a[right])
  left += 1
  right -= 1

// Remove consecutive duplicates (in-place, assuming sorted)
if n > 0:
  write = 1
  for read from 1 to n-1:
    if a[read] != a[read - 1]:
      a[write] = a[read]
      write += 1
  // first 'write' elements are unique

Use Cases

• Buffers and streams: Network packets, I/O buffers.
• Media data: Pixels in images, samples in audio.
• Numerical computing: Vectors, matrices, tensors.
• Lookup tables: Direct indexing for small key ranges.

Choosing Arrays vs. Other Structures

• Use arrays when you need fast random access and contiguous storage.
• Consider linked lists for frequent insertions/deletions in the middle (with trade-offs).
• Use dynamic arrays for flexible growth with mostly end-appends.
• Use hash tables or trees for fast keyed lookup not based on indices.

Key Takeaways

• Arrays provide O(1) index-based access and excellent cache performance.
• Mid-array insertions/deletions are O(n) due to shifting.
• Understand your environment's indexing, bounds behavior, and copy semantics.
• Leverage arrays as building blocks for higher-level data structures and algorithms.

Next Topic