Dynamic Array

What is Dynamic Array?

Dynamic Array will auto grows/resized when we make an insertion (arrays grow) and there is no more space left. No need to specify the array size when initialization. Usually, we will double in array size based on the default size, and different languages may have default size.

When we append, delete, pop, etc to the array, we have a pointer that tells us that the last index element of this array. Therefore when we pop the value, we know the time operation of pop is O(1) because we have that pointer to the last element when they add new element into it.

When we resized the array, we will create a new brand array and this new brand array will have new space allocated for it in memory. Then, all the array elements will be copied from the old array to new array, and the old array will be deallocated (free this from memory).

• Double the capacity called Amortized time complexity. Amortized time complexity averages the running times of operations in a sequence over that sequence (average time taken per operation, if you do many operations). That means, we resize the array operation is O(n) and for adding elements part is O(1), since this operation is not performed every time we add an element, so the average time taken per operation is O(1).
• Therefore, we can see that operation time for overall is O(1), just only resize part operation is O(n), so it is much lower than worst-case.

class DynamicArray:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.length = 0
        self.array = [0] * capacity
 
    def get(self, i: int) -> int:
        return self.array[i]
 
    def set(self, i: int, n: int) -> None:
        self.array[i] = n
 
    def pushback(self, n: int) -> None:
        if self.length == self.capacity:
            self.resize()
        self.array[self.length] = n
        self.length += 1
 
    def popback(self) -> int:
        if self.length > 0:
            self.length -= 1
        return self.array[self.length]
 
    def resize(self) -> None:
        self.capacity = self.capacity * 2
        new_array = [0] * self.capacity
 
        for i in range(self.length):
            new_array[i] = self.array[i]
        self.array = new_array
 
    def getSize(self) -> int:
        return self.length
 
    def getCapacity(self) -> int:
        return self.capacity