Dynamic Array

Dynamic Array

  • In Array, I pre-defined the capacity
  • The array’s size need to be smaller than its capacity
  • Now I will define a dynamic array whose capacity will grow or shrink depending on array’s length
    • if size is approaching capacity, grow capacity by 2
    • if size is approaching 25% of capacity, shrink capacity by 2
  • Most of the array’s methods will remain the same, just add a new method resize

Code

class DynamicArray:
    """
    Implement a dynamic array in python
    """
    def __init__(self, data=None, capacity=10):
        """
        Initialization, if data is a type of list(array),
        copy the conent over; else create a new _data
        """
        if isinstance(data, list):
            self._data = data[:]
            self._size = len(data)
            self._capacity = capacity
            return
        self._capacity = capacity
        self._data = [None] * self._capacity
        self._size = 0

    def _resize(self, new_capacity):
        # resize based on new_capacity
        self._capacity = new_capacity
        new_data = [None] * self._capacity

        for i in range(self._size):
            new_data[i] = self._data[i]

        self._data = new_data


    def get_size(self):
        """
        check number of elements in array
        """
        return self._size

    def get_capacity(self):
        """
        check array capacity
        """
        return len(self._data)

    def is_empty(self):
        """
        check if an array is empty
        """
        return self._size == 0

    def add_last(self, ele):
        """
        add element to the end of an array
        """
        return self.add_ele(ele, self._size)

    def add_first(self, ele):
        """
        add an element to the beginning of an array
        """
        return self.add_ele(ele, 0)


    def add_ele(self, ele, idx):
        """
        add element to the array at idx
        """

        # once the size is approaching capacity, resize
        if self._size == self._capacity:
            # for grow size, the default is capacity * 2
            self._resize(self._capacity*2)

        # make sure idx is valid
        if not 0<= idx <= self._size:
            raise Exception("add failed, idx must be between 0 and {a}".format(a=self._size))

        # move 1 position for all the elements starting from idx
        # start to move the last element, then loop to idx
        # otherwise, idx+1 will be replaced with idx
        for i in range(self._size - 1, idx - 1, -1):
            self._data[i+1] = self._data[i]

        self._data[idx] = ele
        self._size += 1
        return self._data

    def get_ele(self, idx):
        """
        get the element with index idx
        """
        if not 0<=idx<=self._size:
            raise Exception("get failed, idx must be between 0 and {a}".format(a=self._size))
        return 1


    def set_ele(self, idx, val):
        """
        set self._data[idx] as ele
        """
        if not 0<=idx<=self._size:
            raise Exception("set failed, idx must be between 0 and {a}".format(a=self._size))
        self._data[idx] = val
        return self._data

    def contains(self, target):
        """
        check if the array contains the target
        """
        for num in self._data:
            if num == target:
                return True
        return False

    def find(self, target):
        """
        if the array contains target, return its position/index
        """
        if self.contains:
            for i in range(self._size):
                if self._data[i] == target:
                    return i
        print("{a} doesn't exist in the array".format(a = target))
        return -1

    def delete(self, target):
        """
        delete target from the array
        start from idx, move up one position for all elements behind idx
        """
        if self.find(target) == -1:
            print("{a} doesn't exist in the array".format(a = target))
        idx = self.find(target)

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

        self._size -= 1

        # shrink size if size is approaching 1/4 of capacity
        # also make sure that capacity / 2 won't be 0, as it's meaningless to have an array of capacity 0
        if (self._size <= 0.25 * self._capacity) and (self._capacity / 2 != 0):
            self._resize(int(self._capacity / 2))

        return res



    def __str__(self):
        return "Array: {a}, Size: {b}, Capacity: {c}".format(a=self._data[:self._size], b=self._size, c=self._capacity)

    def __repr__(self):
        return self.__str__()

Test

arr = DynamicArray(capacity=10)
print(arr)

for i in range(10):
    arr.add_first(i)
print(arr)

print("Testing Resize to Grow")
arr.add_ele(100,1)
print(arr)

arr.add_first(-1)
print(arr)

arr.add_first(None)
print(arr)

arr.add_last("Python")
print(arr)

print(arr.get_ele(7))

arr.set_ele(7,5**5)
print(arr)

print(arr.contains("Python"))
print(arr.contains("Java"))

print(arr.find("Python"))
print(arr.find("Java"))

print(arr.delete(3125))

print("Test resize: shrink")
arr.delete(9)
arr.delete(100)
arr.delete(8)
arr.delete(7)
arr.delete(0)
arr.delete(-1)
arr.delete(6)
arr.delete(4)
arr.delete(None)
print(arr)
Array: [], Size: 0, Capacity: 10
Array: [9, 8, 7, 6, 5, 4, 3, 2, 1, 0], Size: 10, Capacity: 10
Testing Resize to Grow
Array: [9, 100, 8, 7, 6, 5, 4, 3, 2, 1, 0], Size: 11, Capacity: 20
Array: [-1, 9, 100, 8, 7, 6, 5, 4, 3, 2, 1, 0], Size: 12, Capacity: 20
Array: [None, -1, 9, 100, 8, 7, 6, 5, 4, 3, 2, 1, 0], Size: 13, Capacity: 20
Array: [None, -1, 9, 100, 8, 7, 6, 5, 4, 3, 2, 1, 0, 'Python'], Size: 14, Capacity: 20
1
Array: [None, -1, 9, 100, 8, 7, 6, 3125, 4, 3, 2, 1, 0, 'Python'], Size: 14, Capacity: 20
True
False
13
Java doesn't exist in the array
-1
3125
Test resize: shrink
Array: [3, 2, 1, 'Python'], Size: 4, Capacity: 10

Complexity Analysis

addLast

  • O(1)

addFirst

  • O(n)

add

  • O(n)

removeLast

  • O(1)

remove First

  • O(n)

remove

  • O(n)

resize

  • O(n)

set

  • if we know the index, then it’s O(1)
  • support random search via index

find

  • O(n)

Different Complexity

best case time complexity

worst case time complexity

average case time complexity

amortized time complexity

  • For resize, assume the capacity is n, resize will only be triggered after n+1 addLast, totaling 2n+1 operations
  • so the amortized time complexity for addLast is O(1)
  • similarly the amortized time complexity for removeLast is also O(1)

Complexity Volatility