Arrays as a Data Structure

An array is a collection of elements stored in one continuous block of memory, where each element sits at a known offset from the start. Because the computer can calculate any element's address with a single multiplication, reading or writing element number i takes constant time — O(1) — no matter how big the array is. That single property makes arrays the workhorse of almost every program.

How arrays live in memory

Imagine a row of identical boxes laid end to end. The first box holds index 0, the next index 1, and so on. If each box is 4 bytes and the row starts at address 1000, then index 5 lives at 1000 + 5 * 4 = 1020. The machine does that arithmetic instantly, which is why array access does not slow down as the array grows.

This contiguous layout is also why arrays are cache-friendly. When the CPU fetches one element, it pulls in neighbouring elements too, so looping over an array is fast in practice, not just in theory.

What arrays are good and bad at

The asterisk on insert-at-end is for dynamic arrays that have spare capacity; if they need to grow, that single insert occasionally costs O(n) to copy everything into a bigger block, but averaged out it is still effectively O(1).

Static versus dynamic arrays

A static array has a fixed size decided when you create it. A dynamic array (like C++ std::vector or Java ArrayList) can grow: when it fills up, it allocates a larger block, copies the old contents over, and continues. You get the same O(1) indexing with the convenience of resizing.

Inserting into an array

Here is why inserting in the middle is expensive. To make room, every element after the insertion point must shift one slot to the right:

#include <iostream>
using namespace std;

// Insert `value` at position `pos` in an array of length `size`.
// Assumes the array has room for one more element (capacity > size).
// Returns the new length.
int insertAt(int arr[], int size, int pos, int value) {
    // Shift elements right, starting from the last one,
    // to open a gap at index `pos`. This loop is O(n).
    for (int i = size; i > pos; i--) {
        arr[i] = arr[i - 1];
    }
    arr[pos] = value;   // place the new value in the gap
    return size + 1;    // array is now one longer
}

int main() {
    int arr[10] = {10, 20, 40, 50}; // capacity 10, currently 4 used
    int size = 4;
    size = insertAt(arr, size, 2, 30); // insert 30 at index 2

    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";  // prints: 10 20 30 40 50
    }
    return 0;
}

The shifting loop is what makes mid-array insertion O(n). If your workload is full of middle insertions, a linked list may serve you better.

When to reach for an array

Choose an array when you mostly read and update by index, when you iterate over everything in order, or when memory locality matters for speed. Reach for something else when you constantly insert and remove from the middle, or when you do not know the size in advance and resizing churn would hurt.

Common mistakes

• Off-by-one errors. A valid array of length n has indices 0 to n-1. Touching index n reads past the end and corrupts memory or crashes.
• Forgetting bounds checks. In C++, raw arrays do not stop you from writing out of bounds. Always validate indices yourself.
• Assuming insert is cheap everywhere. Inserting at the end is fast; inserting at the front shifts every element and is O(n).
• Confusing length with capacity. A dynamic array's capacity (allocated room) is usually larger than its length (elements in use). Mixing them up causes subtle bugs.
• Searching an unsorted array repeatedly. If you search the same array often, sorting it once and using binary search, or switching to a hash table, beats scanning every time.

Keep learning

Arrays underpin nearly every other structure you will study. See how linked structures trade indexing for cheap insertion in Linked Lists Explained, and revisit Big-O Notation to sharpen your sense of these costs. The full DSA hub maps out the whole journey.

Ready to practise array problems with instructor feedback in Jalgaon? Join the waitlist for our Data Structures & Algorithms course.