Data Structures
  • Understand why arrays give O(1) random access via contiguous memory
  • See the difference between fixed-size and dynamic arrays
  • Learn when to use arrays vs other structures

Introduction to Arrays and Strings

You're building a game that tracks high scores. You need to store the top 10 scores. You could use 10 separate variables: score1, score2, score3... but that's ridiculous. You use an array.

scores = [9500, 8200, 7800, 7200, 6900, 6500, 6100, 5800, 5400, 5000]

Now you can access any score: scores[0] is the highest, scores[9] is the tenth.

That's an array. A collection of items stored contiguously in memory, accessed by index.

Why Arrays Exist

Random access: Need the 5th element? Go straight to index 4. O(1) time. No looping, no searching.

Memory efficiency: Elements sit next to each other in memory. No pointers, no overhead. For 10 integers, you get exactly 10 integers' worth of space (plus a tiny header).

Cache friendly: When you access scores[0], the CPU often loads nearby elements (scores[1], scores[2]) into cache. Sequential access is lightning fast.

Compare to a linked list: elements scattered in memory, pointers everywhere, no cache benefits. Arrays win for random access.

Declaring and Using Arrays

// Java
int[] numbers = new int[5];  // Fixed size: 5 integers
numbers[0] = 10;
numbers[1] = 20;
// numbers[5] = 30;  // Error! Out of bounds

// Or initialize directly
int[] primes = {2, 3, 5, 7, 11};

# Python (lists are dynamic arrays)
numbers = [10, 20, 30, 40, 50]
numbers.append(60)  # Can grow
numbers[2] = 35     # Modify

// JavaScript
let numbers = [10, 20, 30, 40, 50];
numbers.push(60);  // Can grow
numbers[2] = 35;   // Modify

Fixed Size vs Dynamic Arrays

Fixed size (Java's int[], C's arrays): Once created, size is locked. Want to add an element? Create a new array, copy everything over.

int[] old = {1, 2, 3};
int[] bigger = new int[4];
for (int i = 0; i < old.length; i++) {
    bigger[i] = old[i];
}
bigger[3] = 4;

Painful. That's why most languages offer dynamic arrays (Python's list, Java's ArrayList, C++'s vector).

Dynamic arrays: Grow automatically. When full, allocate a bigger array (usually 2x), copy elements, add the new one.

numbers = [1, 2, 3]
numbers.append(4)  # Grows automatically

Behind the scenes: if the internal array is full, Python allocates a new one (say, double the size), copies elements, then adds 4.

Amortized cost: O(1) per append. Most appends are cheap (space available), occasional ones are O(n) (need to copy). Average over many appends: O(1).

Indexing

Arrays use zero-based indexing. The first element is at index 0.

Array:  [10, 20, 30, 40, 50]
Index:   0   1   2   3   4

Why zero-based? Memory addresses. If the array starts at address 1000 and each element is 4 bytes:

  • Element 0: 1000 + 0×4 = 1000
  • Element 1: 1000 + 1×4 = 1004
  • Element i: 1000 + i×4

Simple arithmetic. With one-based indexing, you'd calculate 1000 + (i-1)×4—extra subtraction every time.

Strings: Arrays of Characters

A string is text. Under the hood, it's an array of characters.

name = "Alice"
# Internally: ['A', 'l', 'i', 'c', 'e']

Access characters like array elements:

name[0]  # 'A'
name[4]  # 'e'

Length:

len(name)  # 5

Immutability (in some languages)

Java/Python strings are immutable: You can't change individual characters.

name = "Alice"
# name[0] = 'B'  # Error! Can't modify

To "change" a string, create a new one:

name = "B" + name[1:]  # "Blice"

Why immutable? Thread safety, string pooling (reusing identical strings to save memory), simplicity.

C/C++/JavaScript strings are mutable (or arrays of chars are):

char name[] = "Alice";
name[0] = 'B';  // OK, now "Blice"

Memory Layout

Arrays are contiguous:

Memory addresses: 1000  1004  1008  1012  1016
Array:            [10]  [20]  [30]  [40]  [50]

All elements next to each other. This is why random access is O(1): given index i, calculate address base + i × element_size.

Contrast with linked lists:

Node 1 at 1000:  value=10, next=2500
Node 2 at 2500:  value=20, next=1200
Node 3 at 1200:  value=30, next=...

Scattered. To access the 3rd element, start at head, follow pointers: O(n).

Common Operations

Access: arr[i] → O(1)

Search (unsorted): Loop through all elements → O(n)

Insert at end (dynamic array): arr.append(x) → O(1) amortized

Insert at position i: Shift all elements from i onward right, then insert → O(n)

arr = [1, 2, 3, 4, 5]
# Insert 99 at index 2
arr.insert(2, 99)
# Result: [1, 2, 99, 3, 4, 5]
# Had to shift 3, 4, 5 to make room

Delete at position i: Remove element, shift all elements from i+1 onward left → O(n)

arr = [1, 2, 3, 4, 5]
arr.pop(2)  # Remove index 2 (value 3)
# Result: [1, 2, 4, 5]
# Had to shift 4, 5 left

Multi-dimensional Arrays

Arrays can hold arrays. That's a 2D array (matrix).

matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

matrix[0][0]  # 1
matrix[1][2]  # 6
matrix[2][1]  # 8

Memory layout (row-major order):

[1, 2, 3, 4, 5, 6, 7, 8, 9]

All rows stored sequentially. To access matrix[i][j] in a 3-column matrix: base + (i × num_columns + j) × element_size.

Still O(1) access.

When to Use Arrays

You know the size (or max size): Fixed-size arrays are simple and fast.

You need random access: Jump to any index in O(1).

Sequential access is common: Cache benefits make looping fast.

Memory is tight: Arrays have minimal overhead.

When NOT to Use Arrays

Frequent insertions/deletions in the middle: O(n) each time due to shifting. Use linked lists (O(1) insert/delete if you have a pointer to the position).

Unknown/highly variable size: Dynamic arrays work but can waste space or require frequent resizing. Consider linked lists or other structures.

Need fast search: Unsorted arrays are O(n). Use hash tables (O(1) average) or balanced trees (O(log n)).

Strings Are Special Arrays

Strings get extra operations:

Concatenation: "Hello" + " " + "World" → "Hello World"

Substring: "Hello"[1:4] → "ell" (Python slicing)

Search: "Hello".find("ll") → 2 (index where "ll" starts)

Replace: "Hello".replace("l", "r") → "Herro"

Under the hood, these often create new strings (if immutable) or manipulate the character array (if mutable).

The Foundation

Arrays and strings are the most basic data structures. Almost everything builds on them.

Understanding arrays means understanding:

  • How memory works
  • Why random access is O(1)
  • Trade-offs: fast access vs expensive insertion/deletion

Master arrays, and you've mastered the foundation of data structures.