Dynamic Array implementation in Python

I am trying to learn data structures by taking this Udemy Course, Easy to Advanced Data Structures by William Fiset. The course provided an implementation of Dynamic Array in Java. To ensure I fully understood the material, I tried to re-implement it in Python. Have provided the code below. Please let me know if I am doing it right or if there is anything wrong with it. Much thanks for your help!

"""
A generic dynamic array implementation

"""
class DynamicArray:
def __init__(self, capacity=0):
self._index = 0
self.capacity = capacity # actual array size
self.arr = [None for _ in range(self.capacity)]
self.size = 0 # length user thinks array is

def __len__(self):
return self.size

def isEmpty(self):
return self.size == 0

def __getitem__(self, index):
return self.arr[index]

def __setitem__(self, index, elem):
self.arr[index] = elem

def clear(self):
for i in range(self.size): self.arr[i] = None

# To resize
if self.size + 1 >= self.capacity:
if self.capacity == 0:
self.capacity = 1
else:
self.capacity *= 2
new_arr = DynamicArray(self.capacity)
for i in range(self.size):
new_arr[i] = self.arr[i]
self.arr = new_arr
self.arr[self.size] = elem
self.size += 1

# Removes an element at the specified index in this array
def removeAt(self, rm_index):
if rm_index >= self.size or rm_index < 0:
raise IndexError
data = self.arr[rm_index]
new_arr = DynamicArray(self.size - 1)
i, j = 0, 0
while i < self.size: #self.size = 3
if i == rm_index:
j -= 1
else:
new_arr[j] = self.arr[i]
i += 1
j += 1
self.arr = new_arr
self.size -= 1
return data

def remove(self, elem):
index = self.indexOf(elem)
if index == -1: return False
self.removeAt(index)
return True

def indexOf(self, elem):
for i in range(self.size):
if elem == self.arr[i]:
return i
return -1

def __contains__(self, elem):
return self.indexOf(elem) != -1

def __iter__(self):
return self

def __next__(self):
if self._index > self.size: raise StopIteration
else:
data = self.arr[self._index]
self._index += 1
return data

def __str__(self):
if self.size == 0: return "[]"
else:
ans = "["
for i in range(self.size - 1):
ans += str(self.arr[i]) + ", "
ans += str(self.arr[self.size - 1]) + "]"
return ans


Your code looks good, but there are four things I would improve:

Style

Overall your code follows the PEP 8 Style Guide, but:

• Names should use snake_case, so index_of instead of indexOf, etc
• Comments after code should leave 2 white spaces after the code:
self.size = 0 # length user thinks array is  <- wrong
self.size = 0  # length user thinks array is <- correct


I don't know if this is just my preference, but I think it's better to group the public methods like is_empty, index_of etc and group the overloads like __getitem__, __setitem__

Clear

At least for me, what I would expect of a method called clear is that it removes all objects, leaving the array empty. So in my opinion your clear method should just set self.size = 0. You don't need to set the elements to null because they don't matter anymore.

Is empty?

In Python, you can check if a list contains any elements by doing:

if my_list:


I think users would expect the same behaviour for your class, which you can implement with the __bool__ (Python 3.x) or __nonzero__ (Python 2.x) methods. Just return not is_empty()

Iterator

The biggest flaw I see in the code is your implementation of iteration. You are keeping the index in the array object; this means that the user cannot do:

for x in my_array:
for y in my_array:


Because the _index is shared in both loops.

You can solve this by implementing the iterator in a different class. I would declare it as a nested class, starting with an underscore to indicate the user that it should be considered private:

class DynamicArray:
class _Iterator:
def __init__(self, dynamic_array):
# ....
# Implement '_index' and '__next__' in this class

def __iter__(self):
# Return a different object every time you are requested an iterator
return _Iterator(self)


In order to adhere to the interface defined by list, some methods should have different names:

indexOf -> find
removeAt -> __delitem__
isEmpty -> __bool__


Currently you don't have consistent bound checks:

x = DynamicArray(10)
x[0] = None
x[0]  # returns None as expected
x[5]  # also returns None although was not set
x[10] # raises IndexError because of the size of the internal array


Instead, add a check in __getitem__:

def __getitem__(self, index):
if not -self.size <= index < self.size:
raise IndexError(...)
return self.arr[index]


Initially the internal array is a list, but after the first resize it is suddenly another DynamicArray. I would stick to one, probably the list.