Before you begin
Why this matters
A C array never grows and never checks an index. The program must track how many elements are in use and keep every index in range itself. Knowing how indexes, counts, and capacity relate lets you predict what a loop reads, and spot a read past the data before it becomes a crash.
What this helps you reason about
- Find the last element in use from a count, without reading one step too far.
- Keep a count below the capacity, and decide what happens when the array is full.
- Spot a saved index that finds a different element after the elements move.
At a station, taxis wait in a queue in the order they arrive, and the first taxi in the queue leaves first. This lesson keeps the taxis in a C array and asks how an index finds a taxi, how a program makes space in an array whose size never changes, and what C does with an index past the end.
Already know this? The short version
- A C array has a fixed size and stores no length; sizeof queue / sizeof queue[0] gives the element count only where the array itself is declared, not through a pointer parameter.
- For a changing number of elements, keep a count below the capacity and decide what happens when the array is full; growing means copying into a larger block (realloc, doubling for a small amortized cost).
- C never checks an index: reading past the end of an array is undefined behavior, and reading past the count but inside the array reads places not in use.
- Inserting or removing at the front moves every element (by hand, or with memmove, never memcpy), so a saved index can name a different element.
Words in this lesson (5)
- index
- The position of an element in an ordered collection, counted from 0. The first element has index 0, and the last has index length − 1.
- array
- A fixed number of elements of one type, stored side by side, such as int queue[5]. Its size is set when it is declared and never changes.
- capacity
- How many elements an array has space for. A C array’s capacity is its size; a separate count says how many of its elements are in use.
- off-by-one error
- A mistake where a loop or a count goes one step too far or stops one step too early, such as a loop that never reaches the last element of an array.
- undefined behavior
- Code for which the C standard sets no requirements. The program may crash, print wrong results, or seem to work, and the result can change between builds.
Examples are focused snippets; imports, enclosing functions, or classes may be omitted. C examples use C11; Haskell examples use Haskell 2010. Expand the notes for language-specific depth.
01 / Positions
How does a collection find the element at a position?
An array keeps its elements side by side in memory. Each element has a position, its index, counted from 0. In int queue[] = {12, 7, 31}, taxi 12 is at index 0, taxi 7 at index 1, and taxi 31 at index 2. queue[i] reads the element at index i. Reading it takes one step: its address is the address of queue[0] plus i times the size of one int.
C stores no length with an array. Where the array is declared, sizeof queue / sizeof queue[0] gives the number of elements: the size of the whole array in bytes, divided by the size of one element. The result has the type size_t, an unsigned integer type for sizes, which printf prints with %zu. The last index is that number minus 1.
int queue[] = {12, 7, 31};
size_t count = sizeof queue / sizeof queue[0]; /* 3 */
printf("%d\n", queue[0]); /* 12 */
printf("%d\n", queue[count - 1]); /* 31 */Indexes run from 0 to count − 1; the last element is at count − 1.
Precisely: where sizeof works
Inside a function that receives the array as a parameter, queue is a pointer, as Function calls showed, and sizeof queue is the size of a pointer. Pass the count as a second parameter. C pointer arithmetic and bounds shows queue[i] as *(queue + i), with the addresses step by step.
Experiment
Read the first and the last taxi
The first element is at index 0. The length is 3, so the last index is 3 - 1 = 2. After a fourth taxi is added, the length is 4, and the same expression reads index 3.
Why it matters Compute the last index from the length, as length - 1, so it stays right when the number of elements changes.
Predict the three printed numbers. Then change the braces to {12, 7, 31, 25} and predict again.
#include <stdio.h>
int main(void) {
setvbuf(stdout, NULL, _IOLBF, 0); // line by line, as in a terminal
int queue[] = {12, 7, 31};
size_t count = sizeof queue / sizeof queue[0];
int first = queue[0];
int last = queue[count - 1];
printf("%zu %d %d\n", count, first, last);
return 0;
}
What to look for
queue shows {12, 7, 31} and count shows 3: the size of the array divided by the size of one element. first shows 12 and last shows 31, and the run prints 3 12 31. After the edit, queue shows {12, 7, 31, 25}, count shows 4, last shows 25, and the run prints 4 12 25.
Expected output
3 12 3102 / Fixed or growable
What stays fixed, and what can grow?
A C array’s size is fixed when it is declared. To hold a number of elements that changes, declare the array with space for the most you expect, its capacity, and keep a separate count of the elements in use. The elements in use are at indexes 0 to count − 1. Adding one writes at index count and adds 1 to count, but only while count is below the capacity.
An initializer with fewer values than the array’s size sets the remaining elements to 0. So int queue[5] = {12, 7, 31}; holds 12, 7, 31, 0, 0, and only the first three are taxis.
int queue[5] = {12, 7, 31}; /* space for 5; the rest are 0 */
int count = 3; /* taxis in use */
if (count < 5) {
queue[count] = 25; /* add at the end */
count++;
}A C array’s size never changes; keep a count of the elements in use, below the capacity.
Coming from Python: There is no append. The array has the size you declared, and the number of elements in use is a variable you keep yourself.
Precisely: what the standard promises
C11 6.7.9 sets the elements without an initializer value to 0. A local array with no initializer at all holds indeterminate values until the program writes them, and reading one is not reliable.
03 / Growing
How do you make space for more elements?
When count reaches the capacity, the program must decide. It can refuse the new element, drop an old one, or move everything into a larger array. Moving means copying every element in use into the larger array, one by one, and from then on using the larger one. That costs one copy per element, so programs that grow often make the new array twice as large: the copies then become rarer as the data grows.
An array declared in a function cannot be made larger later. Memory whose size is chosen while the program runs comes from malloc, and realloc asks for a larger block and copies the contents; a later lesson on manual memory covers both. Until then, choose a capacity and decide what happens when it is full.
int bigger[8];
for (int i = 0; i < count; i++) {
bigger[i] = queue[i]; /* one copy per element in use */
}Growing a C array means copying its elements into a larger one; decide what happens when an array is full.
Precisely: doubling
Doubling keeps the average cost of one addition small: n additions cause copies of about 1 + 2 + 4 + … + n elements, fewer than 2n in all. Growing by a fixed number of elements instead makes the copies grow with the square of n.
Experiment
Add taxis until the array is full
The array’s capacity is fixed at 4 when it is declared. count says how many places are in use, so index count is the first free place, until count reaches the capacity.
Why it matters A C array never makes space by itself. Check the count against the capacity before every write, and decide what happens when the array is full.
Predict both printed lines. Then change int queue[4] to int queue[5] and count < 4 to count < 5, and predict again.
#include <stdio.h>
int main(void) {
setvbuf(stdout, NULL, _IOLBF, 0); // line by line, as in a terminal
int queue[4] = {12, 7, 31};
int count = 3;
int arriving[] = {25, 40};
for (int i = 0; i < 2; i++) {
if (count < 4) {
queue[count] = arriving[i];
count++;
} else {
printf("no space for %d\n", arriving[i]);
}
}
printf("%d taxis\n", count);
return 0;
}
What to look for
queue shows {12, 7, 31, 0}: C sets the places without an initial value to 0. The first round puts 25 at index 3 and count becomes 4; in the second round count < 4 is false, and the run prints no space for 40, then 4 taxis. After the edit, queue starts as {12, 7, 31, 0, 0}, both taxis fit, and the run prints 5 taxis.
Expected output
no space for 40
4 taxis04 / Out of range
What happens at an index past the end?
C does not check indexes. Reading queue[i] with i at the count or beyond reads whatever is stored there. Inside the array, past the count, that is a place the program has not filled: here a 0 from the initializer. Past the end of the array itself, the read is undefined behavior. The C standard then sets no requirements: the program may crash, print a wrong value, or seem to work.
The usual cause is an off-by-one error: a loop that runs one step too far. for (int i = 0; i < count; i++) starts i at 0, runs the block while i < count, and adds 1 to i after each round. With <=, the last round reads index count, one past the last element in use.
int queue[5] = {12, 7, 31};
int count = 3;
for (int i = 0; i < count; i++) {
printf("%d %d\n", i, queue[i]);
}
/* i <= count would also read queue[3], a place not in use */C never checks an index: loop with i < count, and never read past the end of the array.
Coming from Java: There is no exception for an index past the end. The read happens anyway, and the mistake shows as a wrong value, a crash, or nothing at all.
Precisely: the rules and the tools
C11 6.5.6 lets a pointer point one past the end of an array but not read through it, and Annex J.2 lists such reads as undefined. GCC’s -fsanitize=address option stops a program at a read past an array; the stepper does not use it. C pointer arithmetic and bounds shows the same <= mistake with pointers.
Experiment
Loop one step past the last taxi
With <=, the loop runs once more, with i equal to count. queue[3] is inside the array but past the taxis in use, so it reads the 0 the initializer put there. This read stays inside the array, so the run is defined; two more steps, at queue[5], would read past the array, which is undefined behavior.
Why it matters Loop with i < length, never i <= length. The last index is length - 1. In C, nothing stops the extra round, so the mistake shows only as a wrong value, or not at all.
Predict the printed lines. Then change i < count to i <= count and predict again.
#include <stdio.h>
int main(void) {
setvbuf(stdout, NULL, _IOLBF, 0); // line by line, as in a terminal
int queue[5] = {12, 7, 31};
int count = 3;
for (int i = 0; i < count; i++) {
printf("%d %d\n", i, queue[i]);
}
return 0;
}
What to look for
queue shows {12, 7, 31, 0, 0}: space for five, three in use, and the run prints 0 12, 1 7, and 2 31. After the edit, a fourth round reads queue[3], a place not in use, and the run prints 3 0 as its last line. No error appears: C does not check.
Expected output
0 12
1 7
2 3105 / Front and end
What changes when you add or remove at the front?
Adding at the end writes at index count and moves nothing. Adding at the front first moves every element one index later, starting from the last, so that no element is written over before it has moved; then it writes index 0. In the loop below, i-- subtracts 1 from i after each round. Removing from the front moves every later element one index earlier. Each costs one move per element in use.
A saved index does not move with its element. If spot holds 1, the index of taxi 7, then after 40 is added at the front, queue[spot] is 12. Find the element again after a change at the front or in the middle.
for (int i = count; i > 0; i--) {
queue[i] = queue[i - 1]; /* each taxi one index later */
}
queue[0] = 40;
count++;Changes at the front move every element; a saved index then finds a different element.
Precisely: memmove and ring buffers
memmove(queue + 1, queue, count * sizeof queue[0]), from <string.h>, does the same move in one call. memcpy must not be used here, because the two areas overlap. A queue that removes from the front often keeps a start index instead and wraps it around the array, a ring buffer, so that nothing moves.
Experiment
Save a position, then add at the front
Adding at the front moves 12, 7, and 31 one index later. spot still holds 1, and index 1 now holds 12. Adding at the end moves nothing, so index 1 still holds 7. The loop starts from the last taxi, so no taxi is written over before it has moved.
Why it matters A saved index is a place, not an element. After a change at the front or in the middle, find the element again.
Predict both printed numbers. Then delete the for loop, change queue[0] = 40; to queue[count] = 40;, and predict again.
#include <stdio.h>
int main(void) {
setvbuf(stdout, NULL, _IOLBF, 0); // line by line, as in a terminal
int queue[5] = {12, 7, 31};
int count = 3;
int spot = 1; // taxi 7 is at index 1
for (int i = count; i > 0; i--) {
queue[i] = queue[i - 1];
}
queue[0] = 40;
count++;
printf("%d %d\n", spot, queue[spot]);
return 0;
}
What to look for
In the loop, each round copies one taxi one index later: queue shows {12, 7, 31, 31, 0}, then {12, 7, 7, 31, 0}, then {12, 12, 7, 31, 0}, so for a moment one taxi appears twice. queue[0] = 40 then gives {40, 12, 7, 31, 0}, spot still shows 1, and the run prints 1 12. After the edit, queue shows {12, 7, 31, 40, 0}, and the run prints 1 7.
Expected output
1 1206 / Try it
Can you predict a fresh example?
Decide which elements move, then read each index. The next lesson, Stack and heap, shows where the blocks that hold elements are stored.
#include <stdio.h>
int main(void) {
int queue[5] = {12, 7, 31, 25};
int count = 4;
int spot = 2; /* taxi 31 */
for (int i = 0; i + 1 < count; i++) {
queue[i] = queue[i + 1];
}
count--;
printf("%d %d %d\n", count, queue[0], queue[spot]);
return 0;
}
What is printed?
Reveal the reasoning
3 7 25. The loop moves each taxi one index earlier, over taxi 12, and count goes down to 3, so the taxis in use are 7, 31, and 25. Index 2, saved for taxi 31, now holds taxi 25.
Practice tickets
- ARRAY-101 · The van screen shows the stop after the one the driver typed → Free
- ARRAY-102 · A cabin that needs inspection stays in service when the cabin before it also needs one → Sign in · Pro
- ARRAY-103 · New flights stop appearing in the logbook after the fifth → Sign in · Pro