Basics of Arrays (Sequential Storage)

Different programming languages expose the concept of an “array” in quite different ways. Some give you a raw, fixed-size block of memory; others give you a higher-level container that grows and shrinks automatically. To keep the discussion clear we can divide them into two groups: fixed-capacity arrays and resizable arrays.

A fixed-capacity array is simply a contiguous stretch of memory whose individual slots are reached by an index. This is the structure in its most primitive form. A resizable array is a convenience layer built on top of that raw block; it supplies the everyday operations (append, insert, remove, etc.) so you do not have to manage the bookkeeping yourself.

This section shows how those operations are realized on a fixed block of memory and why their costs are what they are. Once the foundation is clear, later structures such as queues, stacks and hash tables become easier to understand, because they are commonly layered on the same idea.

Fixed-Capacity Arrays

Creating a fixed-capacity array requires you to declare both the element type and the exact number of slots in advance. Languages such as C++, Java and Go let you do this directly; Python and JavaScript do not.

These arrays appear only rarely in ordinary application code. Most of the time a resizable array is preferred. Still, the underlying mechanics are worth examining, because every resizable array is ultimately built on top of them.

Here is a simple illustration that uses a Python list only as a stand-in for a raw contiguous block:

# Simulate a fixed-capacity array of 10 integers
arr = [0] * 10

# Write by index
arr[0] = 1
arr[1] = 2

# Read by index
first = arr[0]

Nothing more is possible with the raw form.

Consider what int arr[10] means in C++. Two things happen:

The runtime asks the operating system for a single contiguous region large enough for ten integers. On typical systems an int occupies four bytes, so the region is 40 bytes.

The name arr is bound to the starting address of that region.

The statement arr[1] = 2 likewise does two things:

It computes the address of the second slot by taking the base address and adding one times the size of an integer.

It stores the integer value 2 in the four bytes that begin at that address.

A few clarifying points follow from this model:

Indices begin at zero so that address arithmetic stays simple. The element at index 0 sits at the base address itself; the element at index 1 sits four bytes later, and so on.

Because the array name holds the base address, it behaves like a pointer. Dereferencing it yields the first element, so *arr and arr[0] are equivalent.

In C and C++ the memory is not automatically cleared. The operating system simply hands over a block that may still contain leftover data. That is why programmers usually call a function such as memset before the array is used. In Java and Go a newly allocated fixed array is zero-filled by the language.

Taken together, the declaration tells us three facts: we know the starting address, we know the size of each element, and the block is contiguous. From these facts follows the defining property of an array: random access. Given any valid index, the address of the corresponding element can be calculated in constant time, and modern hardware can then fetch or store the value in constant time as well.

The same contiguity that makes random access cheap is also the source of most of the structure’s drawbacks.

The Four Fundamental Operations

Every data structure must support adding, removing, reading and updating values. With a fixed-capacity array the read and update operations are simply indexed access, both of which run in constant time. Adding and removing are more involved. The snippets below use a Python list only to illustrate the logical steps that would be performed on a raw memory block.

# Simulate a fixed-capacity array of size 10
# In a real low-level language this would be a raw contiguous block of memory.

# ---------- ADD ----------

# 1. Append at the end  → O(1)
arr = [0] * 10
size = 4                      # currently holding 4 elements
for i in range(size):
    arr[i] = i

# append 42
arr[size] = 42
size += 1
# arr is now [0, 1, 2, 3, 42, 0, 0, 0, 0, 0], size == 5


# 2. Insert in the middle  → O(N) because of the shift
# Insert 666 at index 2 of an array that already holds 4 elements
arr = [0] * 10
size = 4
for i in range(size):
    arr[i] = i

# shift every element from the insertion point one position to the right
# (must go backwards so we do not overwrite values we still need)
for i in range(size, 2, -1):
    arr[i] = arr[i - 1]

arr[2] = 666
size += 1
# arr is now [0, 1, 666, 2, 3, 0, 0, 0, 0, 0]


# 3. Array is full → must resize  → O(N)
arr = list(range(10))         # capacity 10, fully occupied
size = 10

# allocate a larger block and copy the old data
new_capacity = 20
new_arr = [0] * new_capacity
for i in range(size):
    new_arr[i] = arr[i]

# old block can now be discarded
arr = new_arr
# now there is room to append
arr[size] = 10
size += 1


# ---------- DELETE ----------

# 4. Remove the last element  → O(1)
arr = [0] * 10
size = 5
for i in range(size):
    arr[i] = i

# simply decrease the logical size (or mark the slot unused)
size -= 1
# the value that was at the end is now considered deleted


# 5. Remove an element from the middle  → O(N) because of the shift
# Delete the element at index 1
arr = [0] * 10
size = 5
for i in range(size):
    arr[i] = i

# shift every later element one position to the left
for i in range(1, size - 1):
    arr[i] = arr[i + 1]

size -= 1
# optionally clear the now-unused last slot
arr[size] = None
# arr is now [0, 2, 3, 4, None, ...]


# ---------- QUERY / UPDATE ----------

# 6. Read or write by a known index  → O(1)
value = arr[2]          # random access
arr[2] = 999            # random access

Adding an element

Three situations arise.

Append at the end.
Writing a new value into the next free slot is a single indexed assignment and therefore takes constant time (see snippet 1).

Insert in the middle.
To place a new value at an interior index, every element from that index onward must be shifted one position higher. The shift is performed from the back of the array toward the front so that no value is overwritten before it has been copied. After the gap has been opened, the new value is written into the vacated slot. Because up to n elements may have to move, the cost is linear (see snippet 2).

The array is already full.
A fixed-capacity block cannot grow in place. The memory that immediately follows it may already belong to another object. The only solution is to request a larger contiguous block, copy the existing elements into it, and then insert the new value. Allocating the new block and copying the old contents both take time proportional to the current number of elements (see snippet 3).

Removing an element

The cases mirror those for insertion.

Remove the last element.
It is enough to decrease the logical size (or mark the final occupied slot as unused). The operation is a single random-access write and therefore constant time (see snippet 4).

Remove an element from the middle.
Every element that follows the deleted one must be shifted one position toward the front so that the remaining values stay contiguous. The shift is performed from front to back. After the move, the newly freed last slot is marked unused. Again the cost is linear (see snippet 5).

Reading and updating

When the index is already known, both operations are pure random access and therefore constant time (see snippet 6).

Summary of costs for a fixed-capacity array

Append at the end: constant time

Insert anywhere else: linear time

Remove the last element: constant time

Remove anywhere else: linear time

Read or write by a known index: constant time

Resizing is not charged to every insertion. Because a resize happens only occasionally, its cost is usually analyzed with amortized analysis.

One common source of confusion is worth noting: the constant-time claims above apply only when the index is already known. If you are given a value and must discover its index, you have no choice but to scan the entire array, which takes linear time. Understanding the underlying memory model makes these distinctions obvious.

Resizable Arrays

A resizable array does not magically remove the cost of inserting or deleting in the middle. Because it is still backed by a contiguous block, those operations still require shifting. What it does provide is automatic management of the underlying capacity and a convenient set of methods that hide the bookkeeping.

Typical usage looks like this (again using Python):

arr = []                     # capacity grows and shrinks automatically

for i in range(10):
    arr.append(i)            # amortized constant time

arr.insert(2, 666)           # linear
arr.insert(0, -1)            # linear

arr.pop()                    # constant
arr.pop(2)                   # linear

val = arr[0]                 # constant
arr[0] = 100                 # constant

idx = arr.index(666)         # linear

In the chapters that follow we will build exactly this kind of resizable array from a raw fixed-capacity block, so that the automatic growth, the shifting logic, and the amortized cost of expansion become fully transparent.