Lists of Data: Arrays

Start with the problem

Suppose you are writing a program to record the exam scores of 30 students and compute the class average and highest score. With only individual variables, you would have to declare 30 separate identifiers:

int score0 = 90;
int score1 = 85;
int score2 = 78;
/* ... 27 more variables ... */

Even if you had the patience to type 30 declarations, you could not write a for loop to step through score0, score1, score2, because variable names disappear when the program compiles—you cannot compute a variable name like score + i at runtime. And if next semester's class has 150 students, you would have to rewrite the entire program.

Whenever a program works with a collection of items of the same type, it stores them in an array: a single named block of contiguous memory divided into equal-sized numbered slots called elements.

How the idea works

An array declaration specifies three things: the element type, the array's name, and the number of elements inside square brackets [N]:

int scores[5] = {90, 85, 78, 92, 88};

Look at the trace above to see what that line creates in memory:

1. Contiguous allocation (Step 1): On line 1, the implementation reserves 5 consecutive int slots (5 * sizeof(int) contiguous bytes) and fills them with 90, 85, 78, 92, and 88.
2. Reading by index (Step 2): Each slot has an integer index inside square brackets, starting at 0 for the first element. On line 2, scores[0] reads the first slot (90) and stores it into best.
3. Writing by index (Step 3): On line 3, scores[2] = 80; jumps straight to index 2 (the third element, which held 78) and overwrites it with 80, leaving all other slots unchanged.

Why array indices start at 0

New programmers often wonder why a 5-element array uses indices 0 through 4 instead of 1 through 5. In C, an index is not an ordinal label ("first, second, third")—it is the offset (distance in elements) from the start of the array:

• scores[0] is 0 elements past the beginning of scores.
• scores[1] is 1 element (4 bytes) past the beginning.
• scores[i] is i elements (i * sizeof(int) bytes) past the beginning.

Because the first element sits right at the start of the array (0 elements away), its index is 0, and the last element of an N-element array always sits at index N - 1.

Initializing arrays

C gives you several clean ways to initialize an array when you declare it:

int a[5] = {90, 85, 78, 92, 88}; /* Explicit size and all 5 values */
int b[]  = {90, 85, 78, 92, 88}; /* Compiler counts 5 values and sets size to 5 */
int c[5] = {90, 85};             /* First two set to 90, 85; remaining three zeroed to 0 */
int zeros[100] = {0};            /* All 100 elements initialized to 0 */

If you declare a local array without an initializer (int temp[5];), C does not waste time clearing its bytes—all 5 slots contain unpredictable stack garbage until your code assigns to them.

Processing an array with a for loop

Because array indices run from 0 to N - 1, a for loop starting at int i = 0 with the condition i < N visits every element exactly once:

#include <stdio.h>
 
int main(void) {
    int scores[5] = {90, 85, 80, 92, 88};
    int sum = 0;
    int max_score = scores[0];
 
    for (int i = 0; i < 5; i++) {
        sum = sum + scores[i];
        if (scores[i] > max_score) {
            max_score = scores[i];
        }
    }
 
    printf("Total: %d, Highest: %d", sum, max_score);
    return 0;
}

Passing arrays to functions

When you pass an array to a function, C does not copy all the elements—it passes the starting memory address of the first element. Because the function only receives that starting address, it does not automatically know how many elements the array holds. Always pass the array's length int n as a second parameter:

int sum_array(const int arr[], int n) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += arr[i];
    }
    return total;
}

Why it is correct

Storing elements side by side in contiguous memory gives arrays their defining superpower: constant-time random access, written O(1).

To read or write scores[i], the CPU does not walk past elements 0, 1, ..., i - 1. Instead, it computes the exact memory address in a single arithmetic instruction:

address of scores[i] = base_address_of_scores + (i * sizeof(element))

The language-level operation is constant-time: the implementation can calculate the address from the base and index without scanning earlier elements. The generated machine code and cache behavior still depend on the target and workload.

What it costs

• Lookup and assignment (arr[i]): O(1) time (1 CPU instruction).
• Full scan (summing or finding the maximum over n elements): O(n) time, visiting each element once. Adjacent elements improve locality on systems with cache lines, although the line size and performance are implementation-dependent.
• Memory footprint: n * sizeof(element) bytes for the array object (5 * sizeof(int) for int scores[5]), with no per-element pointer overhead.

Pitfalls and variations

Where it is used

Arrays are the bedrock of almost every data structure in systems programming: audio buffers, image pixel grids, network packet buffers, hash table buckets, and lookup tables are all contiguous C arrays.

In the next lesson, you will see how C uses char arrays with a special zero-byte marker at the end to represent text strings.