Chapter 01 - Topic 1.1

Arrays and Memory Basics

An array stores values in one continuous block of memory. That single design choice makes indexing extremely fast, but it also makes resizing and middle insertion expensive.

arrays memory basicsarray contiguous memoryarray index access o1array insertion deletion complexitydsa arrays tutorial

Definition

An array is a linear data structure that stores elements in contiguous memory locations, which allows direct O(1) index access.

Core Idea

Every element lives next to the previous one in memory, so the computer can jump to any index using address arithmetic.

Reading arr[i] is O(1), because the address is computed directly instead of scanning from the start.

Inserting in the middle is O(n), because everything after that position must shift right to create space.

Detailed Explanation

An array works because the computer knows the starting address of the block and the size of each element. If the first integer starts at address 1000 and each integer takes 4 bytes, then index 3 lives at address 1012. That is why random access feels instant.

This memory layout is also why arrays are usually cache-friendly. Modern processors prefer nearby memory locations, so walking an array from left to right is often faster in practice than following scattered nodes in a linked list.

The downside appears when the structure must grow or change shape. If you insert in the middle, all later values must move. If you need more capacity than the original array offers, you often need a completely new block.

Find the maximum value in an array

Python

arr = [3, 7, 2, 9, 5]
max_val = arr[0]

for x in arr:
    if x > max_val:
        max_val = x

print(max_val)

Explanation

The code starts by assuming the first element is the maximum. Then it scans each value once. Whenever a larger value appears, max_val is updated. This is a classic linear scan over contiguous data.

Output

Real-life Example

A marks dashboard can scan one student's subject scores and find the highest score shown in the report card summary.

When To Use It

Use arrays when the order matters and direct index access is important.
Use arrays when you frequently scan data from left to right.
Use arrays when the size is stable or resizing cost is acceptable.

Common Mistakes

Confusing fast access with fast insertion. Arrays are fast at reading by index, not at inserting in the middle.
Ignoring off-by-one boundaries while looping over indices.
Treating fixed arrays and dynamic arrays as if they had the same resizing behavior.

Key Takeaways

Use arrays when you need fast index-based access.
Arrays are cache-friendly because contiguous memory is friendly to modern CPUs.
Middle insertions and deletions are expensive because shifting is unavoidable.

Practice Ideas

Find the smallest element in an array.
Reverse an array in-place.
Shift all zeroes to the end while preserving order.

Frequently Asked Questions

Why is array access O(1)?

Because the memory address of any index can be computed directly from the base address and element size.

Why is middle insertion O(n)?

Because all later elements must shift one position to make room for the new value.

Arrays and Memory Basics

Definition

Core Idea

Detailed Explanation

Find the maximum value in an array

When To Use It

Common Mistakes

Key Takeaways

Practice Ideas

Frequently Asked Questions

Why is array access O(1)?

Why is middle insertion O(n)?

More DSA Topic Pages

Arrays and Memory Basics

Definition

Core Idea

Detailed Explanation

Find the maximum value in an array

When To Use It

Common Mistakes

Key Takeaways

Practice Ideas

Frequently Asked Questions

Why is array access O(1)?

Why is middle insertion O(n)?

More DSA Topic Pages