Arrays: The Data Structure Everything Else Builds On

Imagine an apartment building where every unit is the exact same size, numbered in a straight line starting from 0, and the building manager keeps a master list of exactly where each unit is. Need unit 47? You don't walk the whole building counting doors — you go straight there, because the building's layout tells you exactly how far to go. That's an array. It's the simplest data structure there is, and it's also the one every other data structure in this series will eventually be compared against.

We touched on Big O last time in the abstract — today you'll see exactly why arrays get their reputation for being fast at some things and slow at others, and why that reputation is really about memory, not magic.

What is an Array?

An array is a collection of elements, all the same type, stored in contiguous memory — meaning right next to each other, back to back, with no gaps. Each element has an index, starting at 0, that tells the computer exactly how far to jump from the start of the array to find it.

📝 Note

"Contiguous memory" is the whole trick behind arrays. Because every element is the same size and stored back-to-back, the computer can calculate any element's exact memory address with simple math — no searching required.

Why Index Access is O(1)

Here's the math the computer actually does when you write arr[5]:

address of arr[5] = address of arr[0] + (5 × size of one element)

That's it — one multiplication, one addition, done. It doesn't matter if the array has 10 elements or 10 million; the calculation takes exactly the same amount of work. That's why accessing an array by index is O(1) — constant time, the fastest category there is.

Declaring and Using Arrays in Java

public class ArrayBasics {
    public static void main(String[] args) {
        // Declare an array of 5 integers, all initialized to 0
        int[] scores = new int[5];

        // Assign values by index
        scores[0] = 90;
        scores[1] = 85;
        scores[2] = 78;
        scores[3] = 92;
        scores[4] = 88;

        // Or declare and fill in one line
        int[] moreScores = {90, 85, 78, 92, 88};

        // O(1) — direct index access, no searching involved
        System.out.println("Third score: " + scores[2]);

        // O(n) — visiting every element requires one step per element
        int total = 0;
        for (int i = 0; i < scores.length; i++) {
            total += scores[i];
        }
        System.out.println("Average: " + (total / scores.length));
    }
}

Where Arrays Actually Slow Down

Fast index access is only half the story. Arrays have a fixed size decided at creation time — and that fixed size is exactly what causes their weak points:

Inserting or Deleting in the Middle

Say you have [10, 20, 30, 40, 50] and need to insert 25 between 20 and 30. There's no "gap" sitting there waiting — every element after the insertion point has to physically shift over by one to make room:

// Inserting 25 at index 2 in a 5-element array
int[] arr = {10, 20, 30, 40, 50, 0}; // extra slot for the new element
int insertIndex = 2;
int newValue = 25;

// Shift every element from the end backward to open a gap
for (int i = arr.length - 1; i > insertIndex; i--) {
    arr[i] = arr[i - 1];
}
arr[insertIndex] = newValue;
// arr is now [10, 20, 25, 30, 40, 50]

In the worst case — inserting at the very front — every single element has to shift. That's O(n), not O(1). The same shifting problem applies to deletion: remove an element from the middle, and everything after it has to shift back to close the gap.

⚠️ Warning

This is the exact trade-off that motivates Linked Lists, which we'll cover soon: they make inserting and deleting fast by giving up array's O(1) index access. Neither structure is "better" — they're optimized for different situations.

Fixed Size

A Java array's size is locked in the moment you create it with new int[5]. Need a 6th element? You can't resize it — you have to create a brand new, bigger array and copy everything over, which is an O(n) operation that happens behind the scenes. This is exactly why Java gives you ArrayList, which handles that resizing automatically — but it's still doing the same copy-and-grow work underneath when it runs out of room.

Array Time Complexity Summary

Operation	Time Complexity	Why
Access by index	O(1)	Direct address calculation
Search (unsorted)	O(n)	Might have to check every element
Search (sorted, Binary Search)	O(log n)	Covered in Day 6
Insert/Delete at the end	O(1)*	No shifting needed, if space exists
Insert/Delete at start or middle	O(n)	Elements must shift to make/close a gap

*Assuming there's already room. If the array is full, resizing makes it O(n).

Common Interview Questions

• Why is array index access O(1) but linked list index access is O(n)?
• Walk through what happens in memory when you delete an element from the middle of an array.
• What's the time complexity of Java's ArrayList.add(), and why does it occasionally spike?
• When would you choose an array over a more "modern" structure like a HashMap or ArrayList?

The Takeaway

Arrays are fast where the data doesn't need to move — reading any element by its position — and slow wherever the data has to shift around. That single trade-off is the reason almost every other data structure in this series exists: each one is solving a specific weakness that arrays have. Next up: Strings, which in Java are actually a special, more complex case built on similar ideas — and understanding how they really work under the hood will save you from some very common interview mistakes.

➡️ Next in the Series

Strings in Java: How They Actually Work in Memory

Happy learning!
— Team CodeElevateX 🚀