Back to Basics

List: Array Implementation

Explore how dynamic arrays work with automatic resizing, insertion, deletion, and search operations. Understanding the foundation of ArrayList, Vector, and Python lists.

Interactive Operations
Dynamic Resizing
O(1) Access

Dynamic Array Visualization

[0]
[1]
[2]
[3]
Size: 0 / Capacity: 4
Load Factor: 0.0%
Memory: 16 bytes (assuming 4 bytes per integer)

Current Step:

Select an operation to begin visualization

Complexity Analysis

O(1)
Access
O(n)
Insert/Delete
O(n)
Search
O(n)*
Append*
O(n) Space
Dynamic allocation with capacity buffer
*Append is O(1) amortized due to doubling strategy

Operations

Insert

Add element at specific index, shift others right

Delete

Remove element at index, shift others left

Access

Direct access by index calculation

Search

Linear scan through elements

Dynamic Resizing

• Growth Factor: Double capacity when full
• Amortized Cost: O(1) for append operations
• Memory Trade-off: Some wasted space for performance
• Copy Cost: O(n) when resizing occurs
• Frequency: Resizing becomes less frequent as array grows

Pros & Cons

Advantages

• O(1) random access by index
• Cache-friendly memory layout
• Dynamic size without manual management

Disadvantages

• Expensive insertion/deletion in middle
• Memory reallocation overhead
• Wasted space when not at capacity

Applications

• ArrayList (Java): Resizable arrays
• Python Lists: Dynamic arrays with extra features
• JavaScript Arrays: Dynamic and sparse
• C++ vector: High-performance dynamic arrays
• Databases: Index structures and record storage

Implementation

class DynamicArray:
    def __init__(self, initial_capacity=4):
        self.data = [None] * initial_capacity  # Fixed-size array
        self.size = 0                          # Number of elements
        self.capacity = initial_capacity       # Current capacity
    
    def _resize(self):
        # Double the capacity when array is full
        old_capacity = self.capacity
        self.capacity *= 2
        new_data = [None] * self.capacity
        
        # Copy existing elements
        for i in range(self.size):
            new_data[i] = self.data[i]
        
        self.data = new_data
        print(f"Resized from {old_capacity} to {self.capacity}")
    
    def insert(self, index, value):
        # Validate index
        if index < 0 or index > self.size:
            raise IndexError("Index out of bounds")
        
        # Resize if necessary
        if self.size >= self.capacity:
            self._resize()
        
        # Shift elements to the right
        for i in range(self.size, index, -1):
            self.data[i] = self.data[i - 1]
        
        # Insert new element
        self.data[index] = value
        self.size += 1
    
    def delete(self, index):
        # Validate index
        if index < 0 or index >= self.size:
            raise IndexError("Index out of bounds")
        
        # Get value to return
        value = self.data[index]
        
        # Shift elements to the left
        for i in range(index, self.size - 1):
            self.data[i] = self.data[i + 1]
        
        self.size -= 1
        return value
    
    def search(self, value):
        # Linear search through the array
        for i in range(self.size):
            if self.data[i] == value:
                return i
        return -1  # Not found
    
    def access(self, index):
        # Direct access by index
        if index < 0 or index >= self.size:
            raise IndexError("Index out of bounds")
        return self.data[index]
    
    def append(self, value):
        # Insert at the end
        self.insert(self.size, value)
    
    def get_size(self):
        return self.size
    
    def get_capacity(self):
        return self.capacity