Array Limitations & Need for Linked Structures

Throughout this chapter, we have celebrated arrays as the fundamental collection—the workhorse data structure that enables constant-time access by index, powers countless algorithms, and underlies virtually every other data structure you will encounter. Arrays are elegant, efficient, and deeply integrated into how computers manage memory.

But now we must confront an uncomfortable truth: arrays have fundamental limitations that no amount of clever programming can overcome.

The most profound of these limitations is the fixed-size nature of static arrays. When you allocate a static array, you are making a commitment—a commitment to a specific amount of memory, at a specific location, for the lifetime of that array. This commitment, while enabling arrays' greatest strengths, simultaneously creates constraints that prove untenable for many real-world applications.

To understand why static arrays are fixed-size, we must first understand how they are allocated. When you declare an array in a language like C, C++, or when you allocate a fixed buffer in any language, you are requesting a contiguous block of memory from the operating system or runtime.

The allocation process:

1. Size calculation: The system calculates the total bytes needed: number_of_elements × size_per_element
2. Memory search: The memory allocator searches for a contiguous region of the calculated size
3. Address assignment: Upon finding a suitable region, the system returns the starting address
4. Commitment: The memory region is marked as occupied and cannot be used for anything else

This process reveals why the size must be fixed: the allocator needs to find a single, contiguous block. It cannot allocate "approximately" enough space or allocate a region that might grow—it must find and reserve exactly the right amount.

The anatomy of static array memory:

Consider declaring an array of 10 integers, where each integer occupies 4 bytes:

Memory Address:  1000  1004  1008  1012  1016  1020  1024  1028  1032  1036
                 ┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
Array Elements:  │ 0  │ 1  │ 2  │ 3  │ 4  │ 5  │ 6  │ 7  │ 8  │ 9  │
                 └────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
                 ↑                                                 ↑
                 Base Address (returned by allocator)              End of allocation

Every aspect of this allocation is determined at the moment of creation:

• Starting address: Fixed at 1000
• Ending address: Fixed at 1039 (1000 + 40 - 1)
• Number of elements: Fixed at 10
• Total bytes: Fixed at 40

None of these can change after allocation.

The most immediate consequence of fixed-size allocation is that arrays cannot grow in place. When your array is full and you need one more element, you cannot simply "extend" it into the adjacent memory. This limitation stems from how memory is managed.

The adjacent memory problem:

When you allocate an array, the memory immediately following your allocation is not reserved for you. It may contain:

• Another program's data
• Operating system structures
• Another data structure from your own program
• Memory that appears free but is fragmented

Consider this scenario:

Memory Layout After Various Allocations:

 Address:     1000              1040         1100              1160
              ┌──────────────────┬───────────┬──────────────────┬────────
              │   Your Array     │  Object B │   Another Array  │  ...
              │   (40 bytes)     │ (60 bytes)│   (60 bytes)     │
              └──────────────────┴───────────┴──────────────────┴────────
                                 ↑
                                 You cannot extend here—it's occupied!

Even if you wanted to add just one more element (4 bytes) to your array, you cannot. The memory at address 1040 belongs to Object B. The system cannot move Object B without breaking all pointers to it.

What happens when you try to "grow" a static array:

In languages that appear to allow array resizing, what actually happens is a reallocation:

1. Allocate new memory: Request a new, larger contiguous block
2. Copy all elements: Transfer every element from old array to new
3. Free old memory: Release the previous allocation
4. Update references: Any code holding the old address must be updated

This is not "growing"—it's creating an entirely new array and copying. The old array never actually changed size; it was replaced.

Because static arrays cannot grow, programmers face a difficult decision at the moment of creation: how large should the array be? This decision must be made before knowing how the program will actually be used, leading to what we call the pre-allocation dilemma.

The two failure modes:

Every pre-allocation decision risks one of two failures:

1. Allocate too small: Run out of space, requiring expensive reallocation or causing program crashes
2. Allocate too large: Waste memory on unused capacity, potentially exhausting system resources

Neither failure mode is acceptable in production systems, yet one becomes inevitable when requirements are unknown at allocation time.

Real-world scenario: The user list example

Imagine building a system that tracks active users. You need to store user IDs in an array.

• You allocate space for 1,000 users (seems reasonable for a small application)
• The application goes viral; within a week, you have 50,000 active users
• Your array cannot hold them; the system begins rejecting logins

Alternatively:

• You allocate space for 1,000,000 users (to be "safe")
• Only 500 people ever use the application
• You've wasted memory for 999,500 unused slots
• On a server with limited RAM, this waste prevents other critical processes from running

The core problem: you cannot know at allocation time how many users you will have.

The fixed-size constraint becomes particularly painful when we consider when the size is determined. In many languages, static arrays require the size to be known at compile time—before the program even runs.

Compile-time size requirement:

In C, for example, a traditional array declaration requires a constant size:

int numbers[100];  // Size 100 is a compile-time constant

This means the programmer must predict, when writing the code, exactly how much space will be needed when the program runs—potentially months or years later, in conditions the programmer cannot foresee.

The prediction problem:

Software systems face requirements that are fundamentally unpredictable:

• User growth: How many users will register today? This month? This year?
• Data variation: How many items will a single user add to their cart?
• External inputs: How many records will the API receive in this request?
• Algorithmic needs: How deep will the recursion go for this particular input?

None of these can be known at compile time, yet static arrays demand an answer before the program runs.

Variable-length arrays (VLAs) don't solve the problem:

Some languages (C99, for example) introduced variable-length arrays where the size can be a runtime expression:

void process(int n) {
    int data[n];  // Size determined at runtime
    // ...
}

While this allows runtime sizing, VLAs still cannot grow after creation. They trade one inflexibility (compile-time size) for another problem: they're typically allocated on the stack, which has severe size limitations and can easily cause stack overflow for large n.

The fixed-size nature of static arrays isn't merely inconvenient—it's a major source of security vulnerabilities. When a program assumes an array is "large enough" but receives more data than allocated, the result is a buffer overflow—one of the most exploited vulnerabilities in computing history.

How buffer overflows occur:

1. Programmer allocates a fixed-size buffer: char name[64]
2. Program reads user input into the buffer without checking length
3. User provides more than 64 characters
4. Extra characters overwrite adjacent memory
5. Depending on what's adjacent, system crashes or malicious code executes

The anatomy of exploitation:

Stack Memory Layout (simplified):

 Higher Addresses
 ┌────────────────────────┐
 │   Return Address       │  ← Overwrites here allow code execution
 ├────────────────────────┤
 │   Saved Frame Pointer  │
 ├────────────────────────┤
 │   Local Variables      │
 │   (after buffer)       │
 ├────────────────────────┤
 │   buffer[63]           │
 │   buffer[62]           │
 │   ...                  │  ← Extra input overwrites upward
 │   buffer[1]            │
 │   buffer[0]            │  ← Legitimate input starts here
 ├────────────────────────┤
 │   Previous Stack Frame │
 └────────────────────────┘
 Lower Addresses

When input exceeds 64 bytes, it overwrites the saved frame pointer and return address. An attacker can craft input that places their own code address in the return address location. When the function returns, execution jumps to the attacker's code.

Why fixed sizes enable this vulnerability:

The root cause is the mismatch between:

• What the programmer assumed: "64 bytes is enough for a name"
• What reality provides: Arbitrary, potentially malicious input of any length

If arrays could grow dynamically to accommodate any input, this entire class of vulnerability would not exist. The fixed-size constraint forces programmers to make assumptions that attackers exploit.

Another consequence of fixed-size allocation is memory waste when usage is sparse. Since the entire array is allocated upfront, memory is consumed whether or not each slot is actually used.

The sparse array problem:

Consider an array indexed by user ID, where user IDs can range from 0 to 1,000,000:

Allocated Array: 1,000,001 slots × 8 bytes = ~8MB

Actual Usage:
- User 42 is active
- User 1,337 is active  
- User 999,999 is active

Slots used: 3
Slots wasted: 999,998

To use arrays for direct indexing by user ID, you must allocate space for every possible ID, even if only a tiny fraction are ever used.

The fundamental tradeoff:

Arrays provide O(1) access by index, but this comes at the cost of allocating space for every possible index. When the index space is large relative to actual usage, this tradeoff becomes untenable.

Where this matters:

• Hash tables: Must allocate array of buckets even when many are empty
• Graph adjacency matrices: n × n matrix for n nodes, even if sparse
• Lookup tables: Indexed by ID ranges much larger than active count
• Caching systems: Must pre-allocate slots for potential entries

For sparse data, alternative structures (hash maps, linked structures, trees) often provide better memory efficiency at the cost of slower access.

Fixed-size arrays don't exist in isolation—they must be allocated within the constraints of the operating system and hardware. These system-level constraints impose hard limits that no amount of programming cleverness can overcome.

Stack-allocated arrays:

When arrays are allocated on the stack (as local variables in functions), they're subject to the stack size limit:

• Linux/macOS default: 8MB stack per thread
• Windows default: 1MB stack per thread
• Embedded systems: Often 1KB-64KB total

Allocating a stack array larger than the stack size causes immediate stack overflow:

void dangerous_function() {
    int huge_array[10000000];  // 40MB on stack → instant crash
}

Heap-allocated arrays still have limits:

Moving to heap allocation avoids stack limits but introduces others:

• Physical RAM: Exceeding RAM triggers slow disk swapping
• Virtual address space: 32-bit systems limited to ~3GB per process
• Contiguous memory: A 2GB contiguous block may not be available even if 2GB total is free
• Allocator limitations: Some allocators have per-allocation size limits

The contiguous memory problem:

A system might have 4GB of free memory distributed in 1,000 fragments of ~4MB each. An array needing 100MB contiguous space would fail to allocate, despite abundant total free memory. This is a direct consequence of arrays requiring contiguous storage.

We have thoroughly examined the first fundamental limitation of arrays: their fixed-size nature. This isn't a design flaw—it's an inherent consequence of how arrays achieve O(1) access through contiguous memory storage.

What's next:

Fixed size is just the first limitation. In the next page, we'll examine another critical array weakness: the expensive cost of insertions and deletions. Where fixed size limits what we can store, insertion/deletion costs limit how we can modify that stored data.