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

"""
add element to the end of an array
"""

"""
add an element to the beginning of an array
"""

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):
print(arr)

print("Testing Resize to Grow")
print(arr)

print(arr)

print(arr)

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

• O(1)

• O(n)

• O(n)

• O(1)

• O(n)

• O(n)

• O(n)

set

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

• O(n)

Different 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)