DSAverse

Basics & Data Structures

Loading Data Structures...

Array Access

array[0..5]indexed access

Array

Stack

Queue

DSAverse

Initializing Sorting Algorithms...

Sorting

Trees

Graphs

Preparing interactive visualizations...

Back to Basics

Intermediate

List: Dynamic Array

Watch a dynamic array grow, shrink, and shift elements. Understand how Python lists, Java ArrayLists, and C++ vectors work under the hood.

Interactive Operations

Auto-Resizing

O(1) Access

Array Visualization

Filled cells = data, dashed cells = reserved capacity. Watch it resize!

Color Legend

DefaultScanning / TargetFound / InsertedShifting

Speed:

—

[0]

—

[1]

—

[2]

—

[3]

Load Factor0 / 4 (0%)

Size (elements)

Capacity (slots)

16B

Memory (est.)

Current Step

Use Insert, Delete, Search, or Access to begin visualization.

Complexity Analysis

O(1)

Access

O(n)

Insert/Delete

O(n)

O(1)*

Append

O(n) Space

Allocated capacity + element data

*Append is O(1) amortized — rare O(n) resize amortizes over many O(1) appends.

Operations

Insert

Shift elements right, insert at index. Resize if full.

Delete

Remove element at index, shift remaining elements left.

Access

Direct index calculation — O(1) random access.

Search

Linear scan from index 0 until found or end.

Why Doubling Works

When capacity doubles at sizes 4 → 8 → 16 → 32…:

Total copies after n appends

n + n/2 + n/4 + … ≤ 2n

Cost per append (amortized)

O(1) — spread over many ops

Wasted space (worst case)

Up to 50% unused capacity

Test Yourself

Q1/3

What happens when you insert into a full dynamic array?

Implementation

Python

class DynamicArray:
    def __init__(self, initial_capacity=4):
        self.data = [None] * initial_capacity
        self.size = 0
        self.capacity = initial_capacity

    def _resize(self):
        old_cap = self.capacity
        self.capacity *= 2              # Double the capacity
        new_data = [None] * self.capacity
        for i in range(self.size):     # Copy all elements
            new_data[i] = self.data[i]
        self.data = new_data

    def insert(self, index, value):
        if index < 0 or index > self.size:
            raise IndexError("Index out of bounds")
        if self.size >= self.capacity:
            self._resize()             # Expand before inserting
        for i in range(self.size, index, -1):
            self.data[i] = self.data[i - 1]
        self.data[index] = value
        self.size += 1

    def delete(self, index):
        if index < 0 or index >= self.size:
            raise IndexError("Index out of bounds")
        value = self.data[index]
        for i in range(index, self.size - 1):
            self.data[i] = self.data[i + 1]
        self.size -= 1
        return value

    def search(self, value):
        for i in range(self.size):
            if self.data[i] == value:
                return i
        return -1                       # Not found

    def access(self, index):           # O(1) — direct address calculation
        return self.data[index]

    def append(self, value):
        self.insert(self.size, value)

DSAverse

Basics & Data Structures

Loading Data Structures...

Array Access

array[0..5]indexed access

Array

Stack

Queue

Back to Basics

Intermediate

List: Dynamic Array

Watch a dynamic array grow, shrink, and shift elements. Understand how Python lists, Java ArrayLists, and C++ vectors work under the hood.

Interactive Operations

Auto-Resizing

O(1) Access

Array Visualization

Filled cells = data, dashed cells = reserved capacity. Watch it resize!

Color Legend

DefaultScanning / TargetFound / InsertedShifting

Speed:

—

[0]

—

[1]

—

[2]

—

[3]

Load Factor0 / 4 (0%)

Size (elements)

Capacity (slots)

16B

Memory (est.)

Current Step

Use Insert, Delete, Search, or Access to begin visualization.

Complexity Analysis

O(1)

Access

O(n)

Insert/Delete

O(n)

O(1)*

Append

O(n) Space

Allocated capacity + element data

*Append is O(1) amortized — rare O(n) resize amortizes over many O(1) appends.

Operations

Insert

Shift elements right, insert at index. Resize if full.

Delete

Remove element at index, shift remaining elements left.

Access

Direct index calculation — O(1) random access.

Search

Linear scan from index 0 until found or end.

Why Doubling Works

When capacity doubles at sizes 4 → 8 → 16 → 32…:

Total copies after n appends

n + n/2 + n/4 + … ≤ 2n

Cost per append (amortized)

O(1) — spread over many ops

Wasted space (worst case)

Up to 50% unused capacity

Test Yourself

Q1/3

What happens when you insert into a full dynamic array?

Implementation

Python

class DynamicArray:
    def __init__(self, initial_capacity=4):
        self.data = [None] * initial_capacity
        self.size = 0
        self.capacity = initial_capacity

    def _resize(self):
        old_cap = self.capacity
        self.capacity *= 2              # Double the capacity
        new_data = [None] * self.capacity
        for i in range(self.size):     # Copy all elements
            new_data[i] = self.data[i]
        self.data = new_data

    def insert(self, index, value):
        if index < 0 or index > self.size:
            raise IndexError("Index out of bounds")
        if self.size >= self.capacity:
            self._resize()             # Expand before inserting
        for i in range(self.size, index, -1):
            self.data[i] = self.data[i - 1]
        self.data[index] = value
        self.size += 1

    def delete(self, index):
        if index < 0 or index >= self.size:
            raise IndexError("Index out of bounds")
        value = self.data[index]
        for i in range(index, self.size - 1):
            self.data[i] = self.data[i + 1]
        self.size -= 1
        return value

    def search(self, value):
        for i in range(self.size):
            if self.data[i] == value:
                return i
        return -1                       # Not found

    def access(self, index):           # O(1) — direct address calculation
        return self.data[index]

    def append(self, value):
        self.insert(self.size, value)