Dynamic array Implementation in Python

In languages like Python, array(aka list) is automatially resizable. The array will grow as you append items. You don’t have to resize it manually.

In some languages like Java, array comes with fixed length. The size is defined when you create it. When you need a data structure with dynamic resizing, you can use ArrayList.

In this post, we learn to implement the dynamic array in Python. This is to understand how dynamic array works regardless of any programming language.

class ArrayList:
    def __init__(self, size=10):
        self.capacity = size  # max size
        self.list = [None] * self.capacity
        self.size = 0  # current size

    def add(self, value):
        # check if there is enough capacity
        if self.size >= self.capacity:
            self._increase_capacity()

        # add value to the list
        self.list[self.size] = value
        self.size += 1

        print("{} is added to list".format(value))

    def _increase_capacity(self):
        # double the capacity
        new_capacity = self.capacity * 2

        # create a new list with new capacity
        new_list = [None] * new_capacity

        # copy the items from old to new list
        for i in range(self.capacity):
            new_list[i] = self.list[i]

        # update new capacity and list
        self.capacity = new_capacity
        self.list = new_list

        print("capacity is doubled to {}".format(self.capacity))

    def get(self, index):
        if index < 0 or index >= self.size:
            raise Exception("invalid index")

        return self.list[index]

    def delete(self, index):
        if index < 0 or index >= self.size:
            raise Exception("invalid index")

        # check if this is the last item to be deleted
        if index == self.size - 1:
            self.list[index] = None
            return

        # shift items left
        for i in range(index, self.size - 1):
            self.list[i] = self.list[i + 1]

        # update the last item to None
        self.list[self.size - 1] = None

        # update the size
        self.size -= 1

To test the code:

list1 = ArrayList(5)
list1.add(1)
list1.add(2)
list1.add(3)
list1.add(4)
list1.add(5)
list1.add(6)
list1.add(7)
print(list1.list)
list1.delete(6)
print(list1.list)

Output:

1 is added to list
2 is added to list
3 is added to list
4 is added to list
5 is added to list
capacity is doubled to 10
6 is added to list
7 is added to list
[1, 2, 3, 4, 5, 6, 7, None, None, None]
[1, 2, 3, 4, 5, 6, None, None, None, None]