Dynamic Array implementation in Python

Question

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
 def add(self, elem):
 # 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

Answer 1

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)

Answer 2

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

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

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.