Implement Dynamic Array (ArrayList) in Python

Dynamic Array (ArrayList)

  • ArrayList usually started with allocated memory of size n, and double (n*2) when maximum capacity is reached
class ArrayList:    def __init__(self, size=10):        self.max_size = size # maximum memory capacity        self.list = [None] * self.max_size # allocate array        self.size = 0 # current actual size (number of elements)    def add(self, value):        if self.size >= self.max_size: # check if enough memory capacity            self._increase_size()        self.list[self.size] = value        self.size += 1    def _increase_size(self):        new_max_size = self.max_size * 2 # double memory size        new_list = [None] * new_max_size        for i in range(0, self.max_size): # copy old list to new list            new_list[i] = self.list[i]        self.max_size = new_max_size        self.list = new_list    def get(self, index):        if index >= self.size or index < 0:            raise Exception('Invalid index')        return self.list[index]    def delete(self, index):        if index >= self.size or index < 0:            raise Exception('Invalid index')        # shift list from deleted index onwards        # element before index are not affected by deletion        for i in range(index, self.size):             self.list[index] = self.list[index+1]        self.size -= 1

ArrayList Usage

nums = ArrayList(size=1)nums.add(1)nums.add(2)nums.add(3)value = nums.get(1) # index=1, value=2nums.delete(1) # index=1, value=2 is deletedvalue = nums.get(1) # index=1, value=3

Validate max_size growth (capacity*2), asuming initial capacity=1

n elementmax_size (capacity)
11
22
34
44
58
nums = ArrayList(size=1)assert nums.max_size == 1nums.add(1)assert nums.max_size == 1nums.add(2)assert nums.max_size == 2nums.add(3)assert nums.max_size == 4nums.add(4)assert nums.max_size == 4nums.add(5)assert nums.max_size == 8nums.add(6)assert nums.max_size == 8

❤️ Is this article helpful?

Buy me a coffee ☕ or support my work via PayPal to keep this space 🖖 and ad-free.

Do send some 💖 to @d_luaz or share this article.

✨ By Desmond Lua

A dream boy who enjoys making apps, travelling and making youtube videos. Follow me on @d_luaz

👶 Apps I built

Travelopy - discover travel places in Malaysia, Singapore, Taiwan, Japan.