In this post, I’ll walk through some of the most fundamental data structures I’ve been learning: static arrays, dynamic arrays, stacks, hash maps, and prefix sums. These concepts form the foundation for solving many algorithmic problems and understanding how programming languages work under the hood.

Static Arrays

A static array is one of the simplest data structures.

It stores elements in contiguous memory, meaning every element sits directly next to the previous one. The important characteristic of a static array is that its size is fixed when it’s created.

For example, if you create an array of size 10, it will always hold exactly 10 elements. You can’t grow or shrink it later.

Time Complexity

Because elements are stored next to each other, accessing an element by index is extremely fast.

However, inserting or deleting elements isn’t always efficient.

Why are insertions in the middle expensive?

Imagine inserting an element at index 2. Every element after index 2 has to shift one position to the right. That shifting makes the operation linear in the size of the array.

When we talk about Big-O notation, we’re usually referring to the worst-case scenario.

Dynamic Arrays

Most modern programming languages don’t expose fixed-size arrays by default.

Python’s lists, Java’s ArrayList, and C++’s vector are all dynamic arrays.

Unlike static arrays, dynamic arrays automatically grow as you add more elements.

How Dynamic Arrays Resize

A dynamic array starts with some initial capacity.

For example, Java’s ArrayList starts with a default capacity of 10.

Once the array becomes full, it:

1. Allocates a larger block of memory (usually double the current size).
2. Copies every existing element into the new array.
3. Frees the old memory.
4. Continues inserting elements.

The capacity typically grows like this:

1 → 2 → 4 → 8 → 16 → 32 ...

Doubling the capacity dramatically reduces how often resizing occurs.

Amortized O(1)

At first glance, resizing seems expensive because copying every element takes O(n) time.

However, resizing doesn’t happen every insertion.

For example:

1 + 2 + 4 + 8 = 15

Even after several resizes, the total work remains proportional to the number of inserted elements.

This gives us an amortized O(1) insertion time.

That means:

• Most insertions are O(1).
• Occasionally an insertion costs O(n) during resizing.
• Over many insertions, the average cost is still constant.

Dynamic Array Complexity

Stack: A Simple but Powerful Data Structure

A stack follows one simple rule:

Last In, First Out (LIFO)

The last element you add is always the first one you remove.

Think of a stack of plates.

You place new plates on top and always remove the top plate first.

Core Operations

Stacks support three primary operations:

• push(x) — add an element to the top
• pop() — remove the top element
• peek() (or top()) — view the top element without removing it

Why Stacks Are Efficient

Stacks are often implemented using dynamic arrays.

Since all operations happen at the end of the array:

• Push → Amortized O(1)
• Pop → O(1)
• Peek → O(1)

No elements need to shift because we’re only working with one end of the structure.

This simplicity makes stacks incredibly useful for problems involving recursion, expression evaluation, undo functionality, browser history, and depth-first search.

Understanding Hash Maps

One of the most useful data structures in programming is the hash map.

A hash map stores key-value pairs.

Instead of searching through every element to find a value, a hash map uses the key to jump directly to the correct location.

That’s why lookups are typically very fast.

The Role of a Hash Function

Internally, a hash map is backed by an array.

To determine where a key should be stored, the key is passed through a hash function.

The resulting value is converted into a valid array index:

index = hash(key) % capacity

The modulo operation guarantees the index stays within the bounds of the underlying array.

Hash Collisions

No hash function is perfect.

Sometimes two different keys produce the same index.

This is called a hash collision.

Since collisions are inevitable, every hash map needs a strategy to deal with them.

Collision Resolution

There are two common approaches.

1. Chaining

Each array index stores a linked list (or similar collection).

If multiple keys map to the same index, they’re simply stored together.

Pros

• Simple
• Easy to implement

Cons

• Extra memory overhead
• Performance decreases if chains become long

2. Open Addressing

Instead of storing multiple elements in one location, open addressing searches for another empty slot.

The simplest method is linear probing.

If the calculated index is occupied:

• Check the next index.
• If that’s full, check the next.
• Continue until an empty slot is found.

Searching follows the exact same path.

The downside is clustering, where groups of occupied slots form and slow down future searches.

To reduce clustering, more advanced probing methods such as quadratic probing spread elements more evenly across the table.

Why Hash Maps Need Resizing

As more elements are inserted, collisions become more common.

To keep operations fast, hash maps resize once they reach a certain load factor (often around 50–75%).

Resizing involves:

1. Creating a larger array.
2. Recomputing every key’s index.
3. Reinserting every key-value pair.

This process is known as rehashing.

Although rehashing is expensive, it happens infrequently enough that hash maps still provide near constant-time performance on average.

Time Complexity

Good hash functions and sensible resizing policies keep the worst case rare in practice.

Prefix Sums: Trading Memory for Speed

Another elegant technique I’ve been learning is the prefix sum.

Instead of repeatedly computing the sum of subarrays, we perform one preprocessing step that allows every future query to run in constant time.

What Is a Prefix?

A prefix consists of everything from the beginning of an array up to a particular index.

For example:

[0]
[0,1]
[0,1,2]
[0,1,2,3]

A prefix sum array stores cumulative totals.

prefix[i] = arr[0] + arr[1] + ... + arr[i]

The same idea can also be applied to products instead of sums.

Prefix vs. Postfix

A prefix starts at index 0.

A postfix (or suffix) ends at the last index.

They’re essentially mirror images of one another.

Why Prefix Sums Matter

Suppose you’re repeatedly asked:

“What’s the sum of elements between index 2 and index 7?”

The naive solution loops through every element.

That takes O(n) time for every query.

Instead, we compute one prefix sum array.

Then any range sum can be calculated instantly using:

sum(left, right) = prefix[right] - prefix[left - 1]

If the range starts at index 0:

sum(0, right) = prefix[right]

For example, to compute the sum from index 2 to index 5:

• Take prefix[5]
• Subtract prefix[1]

Everything before index 2 cancels out, leaving only the desired subarray.

Time Complexity

Building the prefix array:

O(n)

Every future range sum query:

O(1)

This is a classic example of trading a small amount of preprocessing time for much faster repeated queries.

Final Thoughts

One thing that’s becoming increasingly clear as I study data structures is that they’re all about trade-offs.

• Static arrays are simple but inflexible.
• Dynamic arrays trade occasional resizing for flexible growth.
• Stacks restrict operations to gain simplicity and speed.
• Hash maps use clever hashing to achieve near constant-time lookups.
• Prefix sums spend O(n) upfront to answer future range queries in O(1).

Understanding these trade-offs is much more valuable than memorizing complexity tables. Once you understand the reasoning behind each structure, it becomes much easier to recognize which tool fits a particular problem.

These foundational ideas show up everywhere—from coding interviews to production systems—making them well worth mastering.

This can also be adapted into a more personal “learning in public” style, with reflections on what surprised you and practical coding examples after each section.