Layers of Logic

Foundation 01

Array

A contiguous row of equal-sized slots. An index identifies a slot directly.

Core5 operations comparedJava · Python · C++
01

Mental model

What the structure guarantees

The computer stores the first address and the size of one element. To reach index i, it calculates start + i × element-size. That calculation does not depend on how far i is from zero, so indexed access is constant time.

02

Implementation

How that model appears in code

A fixed array cannot change length. Python lists, Java ArrayList, and C++ vector add a resizable layer over an array; when capacity runs out, they allocate a larger array and copy the elements.

Array basics

int[] values = {4, 2, 7, 1};
int x = values[2];
values[2] = 9;
03

Operation costs

What gets more expensive as the input grows

OperationCostWhy
Read or replace index iO(1)The address is calculated directly.
Scan all elementsO(n)Each element is visited once.
Append to a resizable arrayO(1) amortizedMost appends use spare capacity; occasional growth copies the array.
Insert or delete near the frontO(n)The following elements must shift.
Copy a slice of length kO(k)A new region receives k elements.
04

Tradeoffs

Choose it for the operations it makes cheap

Good fit

  • Direct indexed access
  • Sequential scans
  • Compact storage and cache-friendly traversal

Poor fit

  • Insertions near the front or middle
  • Growth when a fixed array has no spare capacity

Used by

Two PointersSliding WindowMonotonic Stack
05

Common mistakes

Errors that survive a first glance

  1. The last index is length − 1

    An array of length six has indices 0 through 5. Index 6 is outside the array.

  2. Assignment is usually not a copy

    Giving the same array to another variable normally creates another reference to the same data.

  3. A slice may allocate

    Repeated slicing inside a loop can turn a linear idea into quadratic work.