Interview OS
Back to Algorithms & Data Structures

Library

Dynamic arrays

Amortized O(1) append via doubling.

Linear

Overview

A dynamic array (vector/ArrayList) gives O(1) random access and amortized O(1) append by doubling its capacity when full. Understanding the growth/copy cost explains why appends are cheap on average but occasionally expensive.

How it works

Linear
StoreAccessGrowOutputContiguousindex O(1)Random indexa[i]Double capamortized O(1)Use
DataClientServiceEdge

Step by step, with examples

  1. 1

    Contiguous

    • Elements are packed in memory.
  2. 2

    Random index

    • Direct offset lookup.
  3. 3

    Double cap

    • Resize and copy when full.
  4. 4

    Use

    • Fast append/read; mid-insert is O(n).
    • Example: ArrayList, vector

Overview

A contiguous buffer that grows by doubling capacity when full, giving amortized O(1) appends.

Key idea

Doubling makes the total cost of n appends O(n), so each append is O(1) amortized.

When to use it

  • Default list type
  • Random access by index
  • Stack behavior

Common pitfalls

  • Assuming insert-in-middle is O(1)
  • Ignoring resize copy cost in tight loops

Where this content comes from

For full transparency, this content is curated and verified from these sources:

CLRS — Introduction to AlgorithmsCurated competitive-programming archivesOppZen-authored algorithm guides