15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
An array keeps its values in consecutive positions, in index order, starting at a base address. The address of index i is the base address plus i times the element size, so one calculation reaches any element. Capacity counts the positions allocated. Length counts how many of them currently hold elements.
| Address of index i | base address + i x element size |
|---|---|
| Read or write at a valid index | O(1), no scan of earlier positions |
| Valid element indices | 0 through length - 1, never through capacity - 1 |
| In-place append | O(1), only when length < capacity |
| Growing a full array | Allocate larger storage, copy n elements: O(n) |
| Storage for capacity C | O(C) positions reserved |
An array is an ordered collection stored in indexed positions.
Use two numbers to describe one fixed-capacity array:
If length = 3, the logical array elements have indices 0, 1, and 2. Index 3 is not an element yet, even if storage exists there.
For this lesson, treat the backing storage as a conceptual contiguous sequence of positions in index order. Language runtimes may manage physical memory differently. The array model here is:
The base address is the conceptual location of index 0.
Reference scope: Algorithms, 4th edition companion site and the data structures and algorithms course outline.
Start with this backing array:
53[8, 2, 6]Draw all allocated positions, including positions outside the logical array.
| Index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Backing position | 8 | 2 | 6 | unused | unused |
| Part of logical array? | yes | yes | yes | no | no |
The array's logical value sequence is:
1[8, 2, 6]Unused positions are excluded from the logical sequence:
1[8, 2, 6, unused, unused]The capacity is 5, so allocated indices run from 0 through 4. The length is 3, so valid element indices run from 0 through 2.
Append 9.
Appending places a new element immediately after the current last logical element. Since the current length is 3, the next element belongs at index 3.
Positions 0 through 4 have been allocated.
Capacity is how many cells exist (5); length is how many count as elements. Appending 9 writes into unused index 3, then moves the boundary so length is 4. No new storage is needed.
The logical elements occupy indices from 0 through length - 1.
Since length - 1 = 2, these are the elements:
1index: 0 1 2
2element: [8] [2] [6]Indices 3 and 4 are allocated positions, but they are outside the logical array.
The boundary is between indices 2 and 3.
Before writing, check whether a free allocated position exists:
1length < capacity
23 < 5The condition is true, so index 3 is valid allocated storage. Write 9 there.
The write has happened, while the old logical length is still 3. Update the length next.
Increase length from 3 to 4.
Capacity did not change. The append used one already allocated position.
After the append:
0 through 2 were elements.0 through 3 are elements.4, is still outside the logical array.The following condition must remain true:
At all times, valid array elements occupy exactly the indices
0throughlength - 1; indiceslengththroughcapacity - 1are not part of the logical array.
The condition is the array's invariant.
It gives two rules:
0 ≤ index < length.length < capacity.Capacity answers, “How much storage exists?”
Length answers, “How many positions currently count as elements?”
Do not use capacity to decide whether a position is an existing element.
The positions are arranged conceptually in index order. If index 0 begins at the base address, each later index is offset by a fixed number of element-sized positions.
For index i:
For example, index 3 is three element-size offsets after index 0. The calculation uses the index directly. It does not scan positions 0, 1, and 2.
Build a fixed-capacity append operation from the invariant.
length = capacity, there is no unused allocated position.
length.length < capacity.
length is the first unused allocated position.length by one.
The operation does not allocate a new backing array. An implementation that appends when full must first allocate larger storage and copy the existing elements. That step differs from the in-place append shown here.
Data contract
A is a fixed-capacity array record with:
A.cells: allocated backing positions, indexed from 0 through A.capacity - 1A.length: number of logical elementsA.capacity: number of allocated positionsBefore calling the operation:
10 ≤ A.length ≤ A.capacityMutation behavior
A.length by one.A.cells, A.length, or A.capacity.A.capacity.11 operation FixedCapacityAppend(A, value) -> (success, updatedLength)
22 input: A, a fixed-capacity array with 0 ≤ A.length ≤ A.capacity
33 input: value, the element to append
44 mutates: A.cells[A.length] and A.length only when append succeeds
55
66 if A.length = A.capacity
77 return (false, A.length)
88
99 A.cells[A.length] <- value
1010 A.length <- A.length + 1
1111 return (true, A.length)No helper operation is hidden in the pseudocode. The indexed write on line 9 uses the first unused position.
Use the original array and append value 9.
1A.capacity = 5
2A.length = 3
3
4index: 0 1 2 3 4
5A.cells: [8] [2] [6] [unused] [unused]| Pseudocode line | Action | Array state |
|---|---|---|
| 1 | Call FixedCapacityAppend(A, 9). | length = 3, capacity = 5 |
| 2 | Check the required array condition. 0 ≤ 3 ≤ 5 is true. | No change |
| 3 | Receive value = 9. | No change |
| 4 | Note the allowed mutation boundary. | No change |
| 6 | Test A.length = A.capacity. 3 = 5 is false. | No change |
| 9 | Write 9 to A.cells[A.length], which is A.cells[3]. | [8, 2, 6, 9, unused] |
| 10 | Set A.length <- A.length + 1. This changes 3 to 4. | length = 4 |
| 11 | Return (true, 4). | capacity = 5 remains unchanged |
Final state:
1A.capacity = 5
2A.length = 4
3
4index: 0 1 2 3 4
5A.cells: [8] [2] [6] [9] [unused]The logical array is now [8, 2, 6, 9]. Index 4 is still unused capacity.
There is no loop in this operation, so a loop proof does not apply. Prove correctness by considering the two possible capacity cases.
Suppose A.length = A.capacity.
Line 6 is true, so line 7 returns failure before any write occurs. Because the operation does not write to A.cells or change A.length, it cannot write outside the allocated range.
The existing invariant remains true: elements still occupy exactly indices 0 through length - 1.
Suppose A.length < A.capacity.
Because valid allocated indices are 0 through capacity - 1, the old value of A.length is a valid allocated index:
Line 9 writes inside the backing storage. Before line 9, that index is outside the logical array because it is index length.
Line 10 then increases length by one. The new valid element range becomes:
10 through (old length + 1) - 1which simplifies to:
10 through old lengthThat range includes exactly the position written on line 9. No unused-capacity position is read as an element, and the new value becomes the last logical element.
A successful append preserves the invariant and returns the updated length. A failed append leaves the array unchanged and reports failure.
Consider a known valid array index i.
Reading A.cells[i] performs one indexed access. Writing A.cells[i] also performs one indexed access. Each takes constant time in this array model:
Now count the work in FixedCapacityAppend.
When length < capacity, the operation performs:
length = capacityThe number of operations does not depend on the number of stored elements.
When length = capacity, the operation performs:
The operation also takes:
Creating backing storage with capacity C reserves C element positions:
The append operation uses only a constant number of temporary values beyond the array record and its backing storage:
If a larger backing array must be allocated, and the existing logical length is n, copying requires reading n old elements and writing n elements into the new storage. That resizing step is:
The fixed-capacity pseudocode does not perform that resize. It reports failure instead.
Incorrect assumption
1capacity = 5 means indices 0 through 5 are validSmallest exposing input
1capacity = 5Wrong result
The implementation treats index 5 as allocated.
Why it is wrong
Five positions have indices:
10, 1, 2, 3, 4Index 5 would be a sixth position.
Correction
For capacity C, allocated indices are:
10 through C - 1Incorrect assumption
1Every allocated backing slot is automatically an array element.Exposing input
1capacity = 5
2length = 3
3backing slot 3 happens to contain an old valueWrong result
The implementation reports four elements because slot 3 has a value.
Why it is wrong
Logical membership comes from length, not from whether a backing position appears to contain data.
Correction
Read existing elements only at indices satisfying:
10 ≤ index < lengthWith length = 3, only indices 0, 1, and 2 are elements.
length when fullIncorrect line
1A.cells[A.length] <- valuewithout first checking capacity.
Smallest exposing input
1length = 3
2capacity = 3Wrong state
The operation tries to write at index 3, but allocated indices are only 0, 1, and 2.
Correction
Check before writing:
1if A.length = A.capacity
2 return failureWrite at index length only when length < capacity.
| Capacity | Length | Valid logical indices | Append behavior |
|---|---|---|---|
| 0 | 0 | none | Requires larger storage; fixed-capacity append fails |
| 5 | 0 | none | First successful append writes index 0 |
| 5 | 5 | 0 through 4 | No unused position exists; fixed-capacity append fails |
Reads also have boundaries. With length 3, an attempted read at index -1 or index 3 must be rejected as out of bounds. Valid reads are only at indices 0, 1, and 2.
Implement a fixed-capacity append operation that returns the updated length and reports failure when length equals capacity.
Your operation will be tested for this contract:
length index,1def fixed_capacity_append(cells, length, value):
2 # len(cells) is the capacity; returns (success, updated_length)
3 if length == len(cells):
4 return False, length
5 cells[length] = value
6 return True, length + 1
7
8cells = [8, 2, 6, 0, 0] # indices 3 and 4 are allocated but not elements yet
9length = 3
10for value in (9, 7, 1):
11 ok, length = fixed_capacity_append(cells, length, value)
12 print(f"append {value} -> {str(ok).lower()}, length {length}")
13print(cells[:length])1import java.util.Arrays;
2
3public class Main {
4 static int[] cells = {8, 2, 6, 0, 0}; // indices 3 and 4 are allocated but not elements yet
5 static int length = 3;
6
7 static boolean fixedCapacityAppend(int value) {
8 if (length == cells.length) return false; // full: no write
9 cells[length] = value;
10 length++;
11 return true;
12 }
13
14 public static void main(String[] args) {
15 for (int value : new int[]{9, 7, 1}) {
16 boolean ok = fixedCapacityAppend(value);
17 System.out.println("append " + value + " -> " + ok + ", length " + length);
18 }
19 System.out.println(Arrays.toString(Arrays.copyOf(cells, length)));
20 }
21}1#include <iostream>
2#include <vector>
3using namespace std;
4
5struct FixedArray {
6 vector<int> cells; // size() is the capacity
7 int length;
8};
9
10bool fixedCapacityAppend(FixedArray& a, int value) {
11 if (a.length == (int)a.cells.size()) return false; // full: no write
12 a.cells[a.length] = value;
13 a.length++;
14 return true;
15}
16
17int main() {
18 FixedArray a{{8, 2, 6, 0, 0}, 3}; // indices 3 and 4 are allocated but not elements yet
19 for (int value : {9, 7, 1}) {
20 bool ok = fixedCapacityAppend(a, value);
21 cout << "append " << value << " -> " << (ok ? "true" : "false") << ", length " << a.length << "\n";
22 }
23 cout << "[";
24 for (int i = 0; i < a.length; i++) cout << (i ? ", " : "") << a.cells[i];
25 cout << "]" << endl;
26}1const A = { cells: [8, 2, 6, 0, 0], length: 3 }; // indices 3 and 4 are allocated but not elements yet
2
3function fixedCapacityAppend(a, value) {
4 if (a.length === a.cells.length) return false; // full: no write
5 a.cells[a.length] = value;
6 a.length++;
7 return true;
8}
9
10for (const value of [9, 7, 1]) {
11 const ok = fixedCapacityAppend(A, value);
12 console.log(`append ${value} -> ${ok}, length ${A.length}`);
13}
14console.log(`[${A.cells.slice(0, A.length).join(', ')}]`);In the model used here, yes: positions sit next to each other in index order, which is what makes the address formula work. Real runtimes vary. A C or C++ array is one contiguous block, while a Python list holds contiguous references to objects that can live elsewhere.
It depends on the language, not on the array idea. A local fixed-size array in C or C++ usually lives on the stack, while one made with new or malloc lives on the heap. Java arrays and Python lists are heap objects.
Creating storage with capacity C reserves C element positions, which is O(C) space. Appending into spare capacity allocates nothing. When the array is full, you allocate a larger backing array and copy the n existing elements, which costs O(n).
Add i times the element size to the base address of index 0. Index 3 sits three element-size offsets after index 0. The formula uses the index directly, so reaching any element is O(1) and never scans positions 0, 1 and 2.
Capacity is how many positions exist. Length is how many of them count as elements. With capacity 5 and length 3, indices 0 to 2 are elements and indices 3 and 4 are allocated but outside the array. Never use capacity to decide whether a position is an element.