Dynamic 2D Arrays: Pointers vs. Contiguous

Hello! Welcome back to our C interview preparation.

In the last lesson, we mastered the contiguous block method for dynamic 2D arrays, focusing on its high performance due to cache locality and simple memory management (one malloc, one free). We saw that its main drawback was the need for manual index calculation (matrix[i * COLS + j]).

Today, we'll explore the second major strategy. This will complete your toolkit for handling dynamic 2D arrays and, more importantly, allow you to intelligently discuss the trade-offs between them in an interview.

Your learning outcome for this lesson is to: Dynamically allocate and free a 2D array using an array of pointers to separately allocated rows, and contrast this with the contiguous method.

This method is often called the "programmer-friendly" way because it allows us to use the natural matrix[i][j] syntax we're all used to. However, as you know from your work in performance-critical automotive software, convenience often comes with a cost. Let's find out what that cost is.

Method 2: The Array of Pointers

The conceptual model here is different from the single block. Instead of one large rectangle of memory, we create a "jagged" structure:

We first allocate a 1D array of pointers.
Then, we iterate through this pointer array, and for each pointer, we allocate a separate 1D array representing a row of our matrix.

The result is an array where each element is a pointer to a row. The rows themselves are contiguous, but the rows are not necessarily contiguous with each other in memory.

2.5.1. Single-Dimensional Arrays - Dive Into Systems

The 'Dive Into Systems' textbook provides an excellent conceptual breakdown of this method. It explains the pointer types involved and the multi-step allocation process.

Please read the section titled 'Method 2: The Programmer-Friendly Way'. Focus on the declaration int **two_d_array and the two-stage allocation process involving N+1 calls to malloc.

Allocation and Pointer Types

As you just read, the key is the use of a double pointer, int**. Let's dissect this.

int** matrix;: matrix is a pointer... to a pointer... to an int.
The first malloc allocates the array of pointers: matrix = malloc(rows * sizeof(int*));. Note that we are allocating space for rows number of pointers, hence sizeof(int*). After this, matrix points to the start of this pointer array.
The second stage happens in a loop. For each i from 0 to rows-1, we allocate a row: matrix[i] = malloc(cols * sizeof(int));. Each matrix[i] now holds the base address of a separately allocated block of memory for that row's integers.

Visualizing the Memory Layout

This is the most critical part for your interview preparation goal of comparing memory layouts. The two methods result in fundamentally different arrangements in memory.

2D Array Memory Layout Comparison — This image visually contrasts the memory layout of a 2D array implemented as an array of pointers (left) versus a contiguous block (right). On the left, a pointer array on the stack or heap points to separate data arrays (rows) that can be scattered throughout the heap. On the right, all data is in one continuous block.

Look closely at the "Array of Pointers" side of the diagram. The "Pointer Array" holds the addresses of the "Data Arrays" (the rows). Those data arrays can be located anywhere on the heap. This has significant performance implications. When your code finishes processing row[0] and needs to access the start of row[1], the CPU may have to jump to a completely different memory location, likely causing a cache miss. This is in stark contrast to the contiguous layout on the right, where row[1] is guaranteed to immediately follow row[0], maximizing cache efficiency.

Access and Deallocation

The main advantage of this method is syntactic convenience. You can access elements using matrix[i][j]. The compiler understands how to resolve this:

matrix[i]: This expression dereferences the main pointer matrix to get the i-th element from the pointer array. The result is of type int*—a pointer to the beginning of the i-th row.
[j]: This second index is then applied to the int* from step 1, accessing the j-th integer in that row.

This is a two-step process of pointer chasing, which is slightly slower than the single calculation (i * cols + j) used in the contiguous method.

Deallocation must be the exact reverse of allocation. You have rows + 1 allocations, so you need rows + 1 deallocations. Forgetting any of them will cause a memory leak.

First, free each individual row inside a loop.
Then, free the top-level pointer array.

Let's look at a complete example.

Module 4 : Pointers & Dynamic Array

This resource provides a clean, complete code example demonstrating allocation, filling, printing, and the crucial two-step deallocation for the array-of-pointers method.

Please study the code under the heading 'Method 1: Array of Pointers'. Pay close attention to the free loop followed by the final free(matrix). This precise sequence is critical to avoid memory bugs.

The correct deallocation logic is non-negotiable:

// 1. Free each row
for (int i = 0; i < rows; i++) {
    free(matrix[i]);
}
// 2. Free the pointer array
free(matrix);

Failing to free the rows before freeing the pointer array would make the row pointers inaccessible, resulting in a memory leak. Freeing the pointer array twice would be a double-free error.

Interview Prep: Contrasting the Two Methods

This is the core of the lesson. An interviewer will expect you to be able to articulate the trade-offs clearly. Here is a summary table you can use for your review.

Feature	Method 1: Contiguous Block	Method 2: Array of Pointers
Memory Layout	Single, contiguous block of `R*C` elements.	`R` separate blocks for rows, plus one block for pointers. Rows are not contiguous with each other.
Pointer Type	`type` (e.g., `int`)	`type` (e.g., `int`)
Allocation	One call to `malloc()`.	`rows + 1` calls to `malloc()`.
Deallocation	One call to `free()`.	`rows + 1` calls to `free()`.
Access Syntax	Manual: `arr[i * cols + j]`	Natural: `arr[i][j]`
Performance	Higher. Excellent spatial locality and cache utilization.	Lower. Pointer chasing (`arr[i]` then `[j]`) and poor locality between rows can lead to cache misses.
Memory Overhead	Minimal. Only data is stored.	Higher. Requires extra space for the array of `R` pointers.
Flexibility	Rectangular arrays only. All rows must have the same length (`cols`).	Can easily create "jagged arrays" where each row has a different length.

A great point to make in an interview is about flexibility. The array-of-pointers method is the natural choice if you need a jagged array (e.g., storing a variable number of sensor readings per timestamp), because you can malloc each matrix[i] with a different size. This is impossible with the contiguous block method.

Conclusion

You now have a comprehensive understanding of the two primary methods for dynamic 2D array allocation in C. Knowing when to use each one is a sign of an experienced programmer.

Key Takeaways:

Array of Pointers Method: Uses N+1 malloc calls, a type** pointer, and allows for natural [i][j] syntax.
Memory Management: Deallocation is more complex and requires N+1 free calls in the reverse order of allocation.
Trade-offs: This method provides syntactic convenience and flexibility for jagged arrays. This comes at the cost of lower performance due to poor cache locality, higher memory overhead from the pointer array, and more complex memory management.
Context is Key: For the high-performance, predictable memory layouts required in much of automotive software, the contiguous block method is almost always preferred. The array-of-pointers method is better suited for applications where flexibility is more important than raw performance.

In our next lesson, we will delve into the common bugs that arise from dynamic memory management, such as memory leaks, double frees, and use-after-free errors. Your understanding of the two deallocation procedures we've just covered will be an excellent foundation for that discussion.