Advanced Array Data Structures

📌 What is an Array?

An array is a data structure that stores elements in contiguous memory locations. It provides efficient access to elements using an index.

✅ Characteristics of an Array:

• Fixed size (for static arrays)
• Stores elements of the same data type
• Supports random access with O(1) complexity
• Insertion and deletion require shifting elements (O(n) time complexity)

🔥 Dynamic Arrays

A dynamic array is a resizable version of an array. It grows when needed, doubling in size when it reaches its capacity.

✅ Characteristics of a Dynamic Array:

• Can resize dynamically (typically doubling in size)
• Uses amortized analysis for efficient append operations
• Still supports O(1) access but has O(n) insertions when resizing

⚖️ Comparison: Static vs Dynamic Arrays

🛠 Example Implementation: AdvancedArray Class

from typing import Any

class AdvancedArray:
    """
    AdvancedArray class that supports both fixed-size and dynamic array behavior.
    Implements various dunder methods for advanced operations.
    """

    def __init__(self, capacity: int = None, dynamic: bool = False):
        """
        Initializes the AdvancedArray.
        :param capacity: Maximum number of elements the array can hold (ignored if dynamic is True).
        :param dynamic: If True, behaves like a dynamic array (resizes automatically).
        Time Complexity: O(1)
        """
        if capacity is not None and capacity <= 0:
            raise ValueError("Capacity must be greater than zero")

        self._dynamic = dynamic
        self._capacity = capacity if capacity is not None else 4  # Default capacity for dynamic array
        self._size = 0
        self._data = [None] * self._capacity  # Preallocated memory

    def __repr__(self):
        """
        Returns a string representation of the array.
        Time Complexity: O(n)
        """
        return f"AdvancedArray({self._data[:self._size]})"

    def __len__(self):
        """
        Returns the number of elements in the array.
        Time Complexity: O(1)
        """
        return self._size

    def __getitem__(self, index: int) -> Any:
        """
        Retrieves an element by index.
        Time Complexity: O(1)
        """
        if index < 0 or index >= self._size:
            raise IndexError("Index out of bounds")
        return self._data[index]

    def __setitem__(self, index: int, value: Any):
        """
        Sets an element at a specific index.
        Time Complexity: O(1)
        """
        if index < 0 or index >= self._size:
            raise IndexError("Index out of bounds")
        self._data[index] = value

    def _resize(self):
        """
        Resizes the array when dynamic mode is enabled.
        Time Complexity: O(n)
        """
        new_capacity = self._capacity * 2
        new_data = [None] * new_capacity
        for i in range(self._size):
            new_data[i] = self._data[i]
        self._data = new_data
        self._capacity = new_capacity

    def append(self, value: Any):
        """
        Appends an element to the array, resizing if dynamic.
        Time Complexity: O(1) amortized for dynamic, O(1) for fixed.
        """
        if self._size >= self._capacity:
            if self._dynamic:
                self._resize()
            else:
                raise OverflowError("Array capacity exceeded")
        self._data[self._size] = value
        self._size += 1

    def insert(self, index: int, value: Any):
        """
        Inserts an element at a given position.
        Time Complexity: O(n) (due to shifting elements)
        """
        if self._size >= self._capacity:
            if self._dynamic:
                self._resize()
            else:
                raise OverflowError("Array capacity exceeded")
        if index < 0 or index > self._size:
            raise IndexError("Index out of bounds")

        # Shift elements to the right
        for i in range(self._size, index, -1):
            self._data[i] = self._data[i - 1]

        self._data[index] = value
        self._size += 1

    def remove(self, index: int):
        """
        Removes the element at the specified index and shifts elements left.
        Time Complexity: O(n)
        """
        if index < 0 or index >= self._size:
            raise IndexError("Index out of bounds")

        for i in range(index, self._size - 1):
            self._data[i] = self._data[i + 1]

        self._data[self._size - 1] = None  # Clear last element
        self._size -= 1

    def clear(self):
        """
        Clears all elements from the array.
        Time Complexity: O(1)
        """
        self._size = 0
        self._data = [None] * self._capacity

    def index(self, value: Any) -> int:
        """
        Returns the index of the first occurrence of a value.
        Time Complexity: O(n)
        """
        for i in range(self._size):
            if self._data[i] == value:
                return i
        raise ValueError("Value not found in array")

    def count(self, value: Any) -> int:
        """
        Returns the count of occurrences of a value.
        Time Complexity: O(n)
        """
        count = 0
        for i in range(self._size):
            if self._data[i] == value:
                count += 1
        return count

# Example Usage
fixed_array = AdvancedArray(5)  # Fixed size
fixed_array.append(1)
fixed_array.append(2)
fixed_array.append(3)
print(fixed_array)  # AdvancedArray([1, 2, 3])

fixed_array.insert(1, 5)
print(fixed_array)  # AdvancedArray([1, 5, 2, 3])

fixed_array.remove(2)
print(fixed_array)  # AdvancedArray([1, 5, 3])

dynamic_array = AdvancedArray(dynamic=True)  # Dynamic mode
for i in range(10):
    dynamic_array.append(i)
print(dynamic_array)  # Should expand automatically