3
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.