Dynamic Array

A dynamic array (also known as a resizable array or growable array) is a random access, variable-size list data structure that allows elements to be added or removed. It automatically resizes itself when needed.

Features

Automatic resizing when capacity is exceeded
Amortized O(1) append operation
O(1) random access by index
Generic type support for type safety
Memory efficient with automatic shrinking

Time Complexities

Operation	Time Complexity
Access	O(1)
Append	O(1) amortized, O(n) worst case
Insert	O(n)
Remove	O(n)
Pop	O(1) for end, O(n) for arbitrary index
Search	O(n)
Count	O(n)

Basic Usage

Creating and Initializing

from algo.data_structs.arrays.dynamic_array import DynamicArray

# Create with default capacity
arr = DynamicArray()

# Create with custom initial capacity
arr = DynamicArray(initial_capacity=10)

# Check if empty
print(arr.is_empty())  # True
print(len(arr))        # 0

Adding Elements

# Append elements to the end
arr.append(1)
arr.append(2)
arr.append(3)
print(list(arr))  # [1, 2, 3]

# Extend with multiple elements
arr.extend([4, 5, 6])
print(list(arr))  # [1, 2, 3, 4, 5, 6]

# Insert at specific position
arr.insert(0, 0)     # Insert at beginning
arr.insert(3, 2.5)   # Insert in middle
print(list(arr))     # [0, 1, 2, 2.5, 3, 4, 5, 6]

Accessing Elements

# Access by index
print(arr[0])   # 0 (first element)
print(arr[-1])  # 6 (last element)

# Modify elements
arr[1] = 10
print(arr[1])   # 10

# Get array length
print(len(arr))  # 8

Removing Elements

# Remove by value (first occurrence)
arr.remove(2.5)
print(list(arr))  # [0, 10, 2, 3, 4, 5, 6]

# Pop from end
last = arr.pop()
print(last)       # 6
print(list(arr))  # [0, 10, 2, 3, 4, 5]

# Pop from specific index
first = arr.pop(0)
print(first)      # 0
print(list(arr))  # [10, 2, 3, 4, 5]

# Clear all elements
arr.clear()
print(len(arr))   # 0

Search Operations

arr = DynamicArray()
arr.extend([1, 2, 3, 2, 4, 2])

# Find index of element
print(arr.index(2))      # 1 (first occurrence)
print(arr.index(2, 2))   # 3 (starting from index 2)
print(arr.index(2, 1, 4)) # 1 (within range [1, 4))

# Count occurrences
print(arr.count(2))      # 3
print(arr.count(5))      # 0 (non-existent)

# Handle not found
try:
    arr.index(10)
except ValueError as e:
    print(f"Not found: {e}")

Array Manipulation

arr = DynamicArray()
arr.extend([1, 2, 3, 4, 5])

# Reverse the array
arr.reverse()
print(list(arr))  # [5, 4, 3, 2, 1]

# Iteration
for item in arr:
    print(item)

# Convert to list
python_list = list(arr)

Memory Management

arr = DynamicArray()

# Fill array to observe capacity growth
for i in range(10):
    arr.append(i)
    print(f"Size: {len(arr)}, Capacity: {arr.capacity()}")

# Capacity grows: 1 → 2 → 4 → 8 → 16

# Remove elements to observe shrinking
while len(arr) > 2:
    arr.pop()

print(f"After removal - Size: {len(arr)}, Capacity: {arr.capacity()}")

# Manual capacity reduction
arr.shrink_to_fit()
print(f"After shrink - Size: {len(arr)}, Capacity: {arr.capacity()}")

Working with Different Types

Strings

str_arr = DynamicArray()
str_arr.extend(['apple', 'banana', 'cherry'])

print(str_arr.index('banana'))  # 1
print(str_arr.count('apple'))   # 1

Mixed Types

mixed_arr = DynamicArray()
mixed_arr.extend([1, 'hello', 3.14, True])

print(len(mixed_arr))  # 4
print(mixed_arr[1])    # 'hello'
print(mixed_arr[3])    # True

Custom Objects

class Person:
    def __init__(self, name: str, age: int):
        self.name = name
        self.age = age

    def __eq__(self, other):
        return isinstance(other, Person) and self.name == other.name

people = DynamicArray()
alice = Person("Alice", 30)
bob = Person("Bob", 25)

people.extend([alice, bob])
print(people.count(alice))  # 1

Performance Characteristics

Resizing Behavior

The dynamic array uses a doubling strategy for growth and halving strategy for shrinkage:

Growth: When capacity is exceeded, double the capacity
Shrinkage: When utilization drops below 25%, halve the capacity
This provides amortized O(1) append operations

Memory Efficiency

# Example showing automatic resizing
arr = DynamicArray(initial_capacity=2)

# Growth pattern
arr.append(1)  # capacity: 2
arr.append(2)  # capacity: 2
arr.append(3)  # capacity: 4 (doubled)
arr.append(4)  # capacity: 4
arr.append(5)  # capacity: 8 (doubled)

# Shrinkage pattern (when size ≤ capacity/4)
for _ in range(6):  # Remove 6 elements
    arr.pop()
# Capacity will shrink when appropriate

Error Handling

arr = DynamicArray()

# Index errors
try:
    arr[0]  # IndexError: empty array
except IndexError:
    print("Cannot access empty array")

try:
    arr.insert(-1, 5)  # IndexError: negative index
except IndexError:
    print("Invalid insert index")

# Value errors
arr.extend([1, 2, 3])
try:
    arr.remove(5)  # ValueError: not found
except ValueError:
    print("Value not in array")

try:
    arr.index(5)  # ValueError: not found
except ValueError:
    print("Value not found")

String Representation

arr = DynamicArray()
arr.extend([1, 2, 3])

print(str(arr))   # DynamicArray([1, 2, 3])
print(repr(arr))  # DynamicArray(size=3, capacity=4, data=[1, 2, 3])

Common Patterns

Building from Iterable

# From list
arr = DynamicArray()
arr.extend([1, 2, 3, 4, 5])

# From range
arr2 = DynamicArray()
arr2.extend(range(10))

# From tuple
arr3 = DynamicArray()
arr3.extend((1, 2, 3))

Filtering Elements

arr = DynamicArray()
arr.extend(range(10))

# Remove all even numbers
i = 0
while i < len(arr):
    if arr[i] % 2 == 0:
        arr.pop(i)
    else:
        i += 1

Stack-like Usage

stack = DynamicArray()

# Push
stack.append(1)
stack.append(2)
stack.append(3)

# Pop
while not stack.is_empty():
    print(stack.pop())  # 3, 2, 1

API Reference

Dynamic Array Implementation

A dynamic array (also known as a resizable array, growable array, or array list) is a random access, variable-size list data structure that allows elements to be added or removed. It automatically resizes itself when needed.

Key Features:

Automatic resizing when capacity is exceeded
Amortized O(1) append operation
O(1) random access by index
O(n) insertion/deletion at arbitrary positions

Time Complexities:

Access: O(1)
Append: O(1) amortized, O(n) worst case (when resizing)
Insert: O(n)
Delete: O(n)
Search: O(n)

Space Complexity: O(n)

`DynamicArray(initial_capacity=1)`

Bases: Generic[T]

A dynamic array implementation that automatically resizes as needed.

This implementation uses a backing array that doubles in size when capacity is exceeded and halves when utilization drops below 25% (to avoid thrashing).

Initialize a new dynamic array.

Parameters:

Name	Type	Description	Default
`initial_capacity`	`int`	Initial capacity of the backing array (default: 1)	`1`

Raises:

Type	Description
`ValueError`	If initial_capacity is less than 1

`getitem(index)`

Get element at specified index.

Parameters:

Name	Type	Description	Default
`index`	`int`	Index of element to retrieve (supports negative indexing)	required

Returns:

Type	Description
`T`	Element at the specified index

Raises:

Type	Description
`IndexError`	If index is out of bounds

`iter()`

Return an iterator over the array elements.

`len()`

Return the number of elements in the array.

`repr()`

Return detailed string representation for debugging.

`setitem(index, value)`

Set element at specified index.

Parameters:

Name	Type	Description	Default
`index`	`int`	Index where to set the value (supports negative indexing)	required
`value`	`T`	Value to set	required

Raises:

Type	Description
`IndexError`	If index is out of bounds

`str()`

Return string representation of the array.

`append(value)`

Add an element to the end of the array.

Time Complexity: O(1) amortized, O(n) worst case (when resizing)

Parameters:

Name	Type	Description	Default
`value`	`T`	Element to append	required

`capacity()`

Return the current capacity of the backing array.

`clear()`

Remove all elements from the array.

Time Complexity: O(1)

`count(value)`

Return the number of occurrences of value.

Time Complexity: O(n)

Parameters:

Name	Type	Description	Default
`value`	`T`	Value to count	required

Returns:

Type	Description
`int`	Number of occurrences

`extend(iterable)`

Extend the array by appending all elements from the iterable.

Time Complexity: O(k) where k is the number of elements to add

Parameters:

Name	Type	Description	Default
`iterable`		Iterable containing elements to add	required

`index(value, start=0, stop=None)`

Return the index of the first occurrence of value.

Time Complexity: O(n)

Parameters:

Name	Type	Description	Default
`value`	`T`	Value to search for	required
`start`	`int`	Start index for search (default: 0)	`0`
`stop`	`Optional[int]`	Stop index for search (default: end of array)	`None`

Returns:

Type	Description
`int`	Index of the first occurrence

Raises:

Type	Description
`ValueError`	If value is not found

`insert(index, value)`

Insert an element at the specified index.

Time Complexity: O(n) - need to shift elements

Parameters:

Name	Type	Description	Default
`index`	`int`	Index where to insert (0 <= index <= size)	required
`value`	`T`	Element to insert	required

Raises:

Type	Description
`IndexError`	If index is out of valid insertion range

`is_empty()`

Check if the array is empty.

`pop(index=None)`

Remove and return element at specified index (default: last element).

Time Complexity: O(1) for last element, O(n) for arbitrary index

Parameters:

Name	Type	Description	Default
`index`	`Optional[int]`	Index of element to remove (default: -1, last element)	`None`

Returns:

Type	Description
`T`	The removed element

Raises:

Type	Description
`IndexError`	If array is empty or index is out of bounds

`remove(value)`

Remove the first occurrence of the specified value.

Time Complexity: O(n)

Parameters:

Name	Type	Description	Default
`value`	`T`	Value to remove	required

Raises:

Type	Description
`ValueError`	If value is not found

`reverse()`

Reverse the array in place.

Time Complexity: O(n)

`shrink_to_fit()`

Reduce capacity to match the current size.

This can save memory but may cause performance issues if more elements are added later.

Dynamic Array

Features

Time Complexities

Basic Usage

Creating and Initializing

Adding Elements

Accessing Elements

Removing Elements

Search Operations

Array Manipulation

Memory Management

Working with Different Types

Strings

Mixed Types

Custom Objects

Performance Characteristics

Resizing Behavior

Memory Efficiency

Error Handling

String Representation

Common Patterns

Building from Iterable

Filtering Elements

Stack-like Usage

API Reference

DynamicArray(initial_capacity=1)

__getitem__(index)

__iter__()

__len__()

__repr__()

__setitem__(index, value)

__str__()

append(value)

capacity()

clear()

count(value)

extend(iterable)

index(value, start=0, stop=None)

insert(index, value)

is_empty()

pop(index=None)

remove(value)

reverse()

shrink_to_fit()

`DynamicArray(initial_capacity=1)`

`getitem(index)`

`iter()`

`len()`

`repr()`

`setitem(index, value)`

`str()`

`append(value)`

`capacity()`

`clear()`

`count(value)`

`extend(iterable)`

`index(value, start=0, stop=None)`

`insert(index, value)`

`is_empty()`

`pop(index=None)`

`remove(value)`

`reverse()`

`shrink_to_fit()`