Chapter 01 - Topic 1.2

Dynamic Arrays

A dynamic array wraps a fixed array internally and grows when it runs out of space. The trick is that growth is occasional, not constant, which keeps append fast on average.

dynamic arraysarraylist resize explanationvector capacity sizeamortized o1 appenddynamic array tutorial

Definition

A dynamic array is an array-backed structure that automatically resizes its internal buffer when capacity is full.

Core Idea

size tells you how many elements are actually stored, while capacity tells you how much internal room is allocated.

When size reaches capacity, the data is copied into a bigger buffer, often double the old size.

Resizing costs O(n), but because it happens rarely, append stays amortized O(1).

Detailed Explanation

A dynamic array keeps the convenience of index access while quietly handling growth in the background. Internally, it still depends on a normal array buffer, but the wrapper class manages when to allocate more space.

The key idea is amortization. One append may occasionally be expensive because it triggers a resize and copy, but many appends before and after that resize remain cheap. When averaged over time, append remains effectively constant.

This is why structures like Java ArrayList, C++ vector, and Python list are so widely used. They give a great balance between simple indexing and practical growth without making developers manage raw memory manually.

Append with automatic resize

JavaScript

class DynamicArray {
  constructor() {
    this.data = new Array(2);
    this.size = 0;
    this.capacity = 2;
  }

  append(value) {
    if (this.size === this.capacity) {
      const newData = new Array(this.capacity * 2);
      for (let i = 0; i < this.size; i++) {
        newData[i] = this.data[i];
      }
      this.data = newData;
      this.capacity *= 2;
    }

    this.data[this.size] = value;
    this.size++;
  }
}

const arr = new DynamicArray();
arr.append(10);
arr.append(25);
arr.append(37);
console.log(arr.data.slice(0, arr.size));
console.log(arr.capacity);

Explanation

The first two appends fit in the original buffer. The third append detects that size equals capacity, allocates a new array with double capacity, copies old elements, and then writes the new value.

Output

[10, 25, 37]
4

Real-life Example

A photo gallery app keeps extra reserved slots so adding one more image usually does not require rebuilding the whole gallery structure every single time.

When To Use It

Use dynamic arrays when you need both indexed access and a structure that can grow.
Use them for stacks, buffers, result lists, and most general-purpose collections.
Prefer them over linked lists when traversal and indexing matter more than frequent middle insertions.

Common Mistakes

Thinking every append is literally O(1). The precise statement is amortized O(1).
Confusing reserved capacity with actual stored size.
Using repeated middle insertions and expecting array-like speed.

Key Takeaways

Doubling capacity is the main reason append remains amortized O(1).
Dynamic arrays trade a little extra memory for much better append performance.
Insert and delete in the middle are still O(n) because elements must shift.

Practice Ideas

Implement append and get from scratch.
Track how capacity changes as values are inserted.
Compare append-at-end versus insert-at-front cost.

Frequently Asked Questions

What is the difference between size and capacity?

Size is the number of stored elements, while capacity is the total reserved slots in the internal buffer.

Why not increase capacity by one every time?

Because repeated copying would make append much slower overall, turning it into O(n) amortized behavior.

More DSA Topic Pages

Topic 1.1

Arrays and Memory Basics

Learn how arrays work in memory, why index access is O(1), where insertion becomes expensive, and how this pattern appears in real software systems.

Topic 1.3

Two Pointer Technique

Learn opposite-end and fast-slow pointer patterns, how to reduce O(n²) brute force to O(n), and where this technique shows up in interviews.

Topic 1.4

Sliding Window Technique

Master fixed and variable window patterns for subarrays and substrings, with efficient updates, code walkthroughs, outputs, and practical analogies.

Topic 1.5

Strings and Character Arrays

Study string memory, immutability, palindrome checks, anagram frequency maps, and the right way to build strings efficiently.

Detailed Explanation

class DynamicArray { constructor() { this.data = new Array(2); this.size = 0; this.capacity = 2; } append(value) { if (this.size === this.capacity) { const newData = new Array(this.capacity * 2); for (let i = 0; i < this.size; i++) { newData[i] = this.data[i]; } this.data = newData; this.capacity *= 2; } this.data[this.size] = value; this.size++; } } const arr = new DynamicArray(); arr.append(10); arr.append(25); arr.append(37); console.log(arr.data.slice(0, arr.size)); console.log(arr.capacity);

Frequently Asked Questions

What is the difference between size and capacity?

Size is the number of stored elements, while capacity is the total reserved slots in the internal buffer.

Why not increase capacity by one every time?

Because repeated copying would make append much slower overall, turning it into O(n) amortized behavior.