The Array Data Structure

Let’s explore the organization, operations, and trade-offs of (fixed-size) arrays in Java.

Organization

When we create an array in Java, the program allocates a contiguous block in the computer’s Random Access Memory (RAM) to hold the elements. Each element is stored at a specific address, and we can calculate the address of any element using its index.

Let’s say the array starts at memory address 100 and each integer takes 4 bytes.

Index:     0     1     2     3
        ┌─────┬─────┬─────┬─────┐
        │  5  │  3  │  8  │  1  │
        └─────┴─────┴─────┴─────┘
Address:  100   104   108   112
Random Access Memory (RAM)

RAM is the computer’s main memory, where data is stored temporarily for processing.

The computer stores information in binary digits or bits where each bit can be either 0 or 1. The unit of memory is typically 8 bits or a byte.

In Java, an int is a 32-bit value, so modeling it as 4 bytes was a reasonable example.

RAM is organized as a linear sequence of bytes, with each byte having a unique address. Your computer’s processor (CPU) uses these addresses to read and write data to RAM. The CPU can read and write to any address in RAM, in any order, in almost the same amount of time. This is why it is called “random access” memory. In algorithm analysis, we often treat reading from or writing to RAM as a zero-cost step, although it is not truly free.

Depending on your computer’s architecture, the address size may vary (e.g., 32-bit or 64-bit). In a 32-bit system, each address is represented by 8 hexadecimal digits (e.g., 0x1A2B3C4D).

Operations

To find the element at index i, the program computes start_address + (i × element_size). With zero-indexing, the arithmetic works out like this:

- Element 0: 100 + (0 × 4) = 100
- Element 3: 100 + (3 × 4) = 112

Since an array is stored in RAM, once we know the address of an element, we can jump straight to it. In other words, the cost to access an array element is just one multiplication and one addition, regardless of array size. Accessing the first element takes the same time as accessing the millionth element. The program does not need to iterate through the elements one by one.

Writing to a slot works the same way. numbers[2] = 99 computes the same address and stores a value there instead of reading one.

An Example of Abstraction

Writing array[i] to get an element back, without thinking about addresses or bytes, is an example of abstraction: hiding the details behind a simple interface. It is one of the most important ideas in computer science, and we will cover it in more detail shortly.

Trade-offs

Arrays are fast for access, but there are limitations:

  • Fixed size: once we create an array, we cannot change its size.
  • Insertion and deletion: adding or removing an element forces us to shift the elements after that position.
  • Wasted memory: if we do not use all the allocated space, that memory stays allocated and unused.

These limitations are why we need other data structures, and we will study several of them in this course. Each one has its own organization, its own operations, and its own trade-offs.