Arrays in DSA: The Fundamental Data Structure

An array is a collection of elements stored in contiguous memory, each reachable by a numeric index starting at 0. Because the elements sit side by side, the computer can jump straight to any index with a simple address calculation — making reads and writes by index O(1) (constant time). Arrays are the foundation almost every other data structure is built on.

How an array works

Picture numbered lockers in a row. If each locker is the same size and you know where locker 0 starts, you can find locker i instantly: start + i × size. That’s why a[i] is constant time — no scanning required.

#include <vector>
std::vector<int> a = {5, 8, 13, 21};
int x = a[2];   // 13 — O(1) access
a[2] = 99;      // O(1) update

int[] a = {5, 8, 13, 21};
int x = a[2];   // 13 — O(1) access
a[2] = 99;      // O(1) update

const a = [5, 8, 13, 21];
let x = a[2];   // 13 — O(1) access
a[2] = 99;      // O(1) update

a = [5, 8, 13, 21]
x = a[2]    # 13 — O(1) access
a[2] = 99   # O(1) update

The cost of inserting and deleting

The trade-off: because elements are packed together, inserting or removing anywhere but the end forces every later element to shift. That’s O(n) in the worst case.

• Access by index: O(1)
• Update by index: O(1)
• Insert/delete at end: O(1) amortized (for dynamic arrays)
• Insert/delete at front or middle: O(n) — everything after must move
• Search by value (unsorted): O(n)

For beginners: “Amortized O(1)” means usually constant, with occasional costly resize when the array grows — averaged out, each append is cheap. Covered in dynamic arrays.

Fixed vs dynamic arrays

• Fixed-size arrays (C++ raw arrays, Java int[]) have a length set at creation.
• Dynamic arrays (C++ std::vector, Java ArrayList, JS Array, Python list) grow automatically as you add elements.

This course uses dynamic arrays by default because they map cleanly across all four languages.

When to use an array

Reach for an array when you need fast index access and you mostly read or append. If you’ll insert/delete in the middle a lot, consider a linked list; if you need fast lookup by key, a hash table.

Ready to practice? Try the array exercises.