Arrays

Part of Programming Fundamentals

Arrays are the simplest and most powerful way to organize collections of related data in memory.

Why This Matters

When rebuilding computational infrastructure from scratch, the array is the first data structure you will reach for — before linked lists, before trees, before hash tables. Every useful program processes collections: a list of temperatures, a set of sensor readings, a sequence of characters forming a word. Arrays give you that collection in the most direct form possible: a contiguous block of memory where every element sits at a predictable address.

Understanding arrays means understanding memory itself. Once you grasp that an array is simply a base address plus an offset, you have unlocked the fundamental model of how all data structures work. Everything more sophisticated builds on this foundation.

For a civilization rebuilding computation, arrays appear in every domain. A weather station logs hourly temperature readings into an array. A grain inventory tracks bushel counts by field number. A simple text editor stores characters in a character array. Before databases, before spreadsheets, the array is your workhorse.

What an Array Is

An array is a fixed-size, ordered collection of elements of the same type, stored at consecutive memory addresses. “Fixed-size” means you declare how many elements you need before you use it. “Ordered” means element zero comes before element one, always. “Same type” means each element occupies the same number of bytes, so the address of any element can be computed directly.

If an array of integers starts at address 1000 and each integer occupies 2 bytes, then element 0 is at 1000, element 1 is at 1002, element 2 is at 1004, and element N is at 1000 + (N × 2). This formula — base address plus index times element size — is all arithmetic the CPU does to access any array element in constant time. It does not matter whether you want element 0 or element 999; the access takes the same number of steps.

This property is called random access. It distinguishes arrays from linked structures where you must follow a chain of pointers to reach a distant element. Random access makes arrays ideal when you know the index of what you want.

Declaring and Initializing Arrays

In most languages developed for constrained hardware, you declare an array by specifying its type and size. In a BASIC-like language you might write:

DIM TEMPS(24)

This reserves space for 25 elements (indices 0 through 24, or sometimes 1 through 24 depending on convention — know your language). In assembly language, you reserve space in the data segment:

TEMPS: DS 24    ; reserve 24 bytes

Initialization means filling the array with starting values. You can initialize explicitly, element by element:

FOR I = 0 TO 23
  TEMPS(I) = 0
NEXT I

Or in assembly, a loop that zeros out memory from the base address through the last element. On a newly powered system, memory contents are unpredictable. Always initialize arrays before reading from them, or your program will process garbage.

Some environments let you initialize at declaration time:

DIM DAYS(7) = {0, 1, 2, 3, 4, 5, 6}

This embeds the values in the program binary itself, copied into RAM at startup. Useful for lookup tables that never change.

Reading and Writing Elements

Array access uses an index — a number identifying which element you want. Most languages use zero-based indexing: the first element is index 0, the last is index (size - 1). Some languages, particularly early BASIC variants, use one-based indexing. Mixing conventions is a perennial source of off-by-one errors.

Reading element I from array A:

VALUE = A(I)

Writing to element I:

A(I) = VALUE

In assembly, accessing element I of a byte array starting at BASE:

LD HL, BASE    ; load base address
LD DE, I       ; load index
ADD HL, DE     ; add index to base
LD A, (HL)     ; load byte at that address

For multi-byte elements, multiply the index by element size before adding. If each element is 2 bytes:

LD DE, I
SLA E          ; multiply DE by 2 (shift left)
RL D
ADD HL, DE

Bounds checking — verifying that I falls within 0 to size-1 — is your responsibility in low-level languages. Accessing outside the array bounds reads or writes arbitrary memory. This corrupts data silently or crashes the program in spectacular ways. Always validate indices when accepting them from external input or loop variables that might exceed expectations.

Traversing Arrays

The most common array operation is iteration — visiting every element in sequence. A simple loop suffices:

FOR I = 0 TO SIZE - 1
  PROCESS(A(I))
NEXT I

Common traversal tasks include:

Summing: Add every element to a running total. Useful for averaging sensor data, computing totals in inventory systems.

Finding maximum or minimum: Track the largest (or smallest) value seen so far as you scan through. After one pass, you have the answer.

Searching: Scan until you find an element matching a target value. This linear search examines up to every element in the worst case. For a sorted array, binary search is far faster but requires the array to be ordered.

Copying: Transfer elements from one array to another with a simple loop. Essential when you need to preserve original data while transforming a copy.

Reversing: Swap element at index 0 with element at index (size-1), then index 1 with index (size-2), and so on until you reach the middle.

Sorting Arrays

Sorting rearranges array elements into ascending or descending order. Once sorted, binary search can find any element in logarithmic rather than linear time — critical for large arrays.

Bubble sort is the simplest to implement. Make repeated passes through the array, swapping adjacent elements that are out of order. Continue until a full pass produces no swaps.

DO
  SWAPPED = 0
  FOR I = 0 TO SIZE - 2
    IF A(I) > A(I+1) THEN
      SWAP A(I), A(I+1)
      SWAPPED = 1
    END IF
  NEXT I
LOOP WHILE SWAPPED = 1

Bubble sort is slow on large arrays — its worst case is proportional to the square of the array size. For small arrays (dozens of elements), it is perfectly adequate. For hundreds of elements, consider insertion sort, which is similarly simple but performs better on nearly-sorted data. For thousands of elements, implement quicksort or merge sort.

Insertion sort builds a sorted sub-array one element at a time. Take the next unsorted element and insert it into its correct position in the sorted portion by shifting larger elements rightward.

Binary search on a sorted array: compare the target to the middle element. If equal, done. If target is less, search the left half. If greater, search the right half. Repeat, halving the search space each time. Finds any element in at most log₂(N) comparisons.

Multi-Dimensional Arrays

A two-dimensional array is a table — rows and columns. Declare it with two dimensions:

DIM GRID(8, 8)   ; 8x8 chessboard, for example

Access element at row R, column C:

VALUE = GRID(R, C)

In memory, the 2D array is stored as a 1D sequence. Row-major order stores all elements of row 0 first, then row 1, and so on. The address of element (R, C) in a grid with COLS columns is:

BASE + (R × COLS + C) × ELEMENT_SIZE

Multi-dimensional arrays model grids, matrices, game boards, and tables. A temperature logging system might use a 2D array with rows for days and columns for hours. Matrix multiplication — fundamental to many engineering calculations — operates on 2D arrays.

Arrays as Buffers

A critical use of arrays is the circular buffer (also called ring buffer), essential for communication between hardware and software. Imagine a serial port receiving characters faster than your program can process them. Store incoming characters in an array used as a circular buffer.

Maintain two indices: HEAD (where the next character will be written) and TAIL (where the next character will be read). When HEAD or TAIL reaches the end of the array, wrap it back to zero. The buffer is full when HEAD is one position behind TAIL; empty when HEAD equals TAIL.

This pattern appears constantly in embedded systems: serial communication buffers, audio sample queues, sensor data pipelines. Understanding it unlocks the ability to write interrupt-driven I/O routines that never lose data.

Practical Notes for Rebuilders

When working with constrained memory — early microprocessors typically had 4 KB to 64 KB of RAM — array sizing is a genuine design decision. Allocate too much and you leave insufficient space for program code and other variables. Too little and your program fails when it encounters data sets larger than anticipated.

Document every array’s purpose, type, size, and index convention at the declaration. Future maintainers (including yourself six months later) will need this context. Comment which indices correspond to which physical quantities.

Prefer arrays over individual variables whenever you find yourself writing A1, A2, A3… up to some limit. That pattern is always an array waiting to be written properly.

The array is the atom of data organization. Master it first, then build toward more complex structures only when the problem genuinely requires them.