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.