Implement Dynamic Array (ArrayList) in Python

February 21, 2019

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=2

nums.delete(1) # index=1, value=2 is deleted

value = nums.get(1) # index=1, value=3

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

n element max_size (capacity)
1 1
2 2
3 4
4 4
5 8
nums = ArrayList(size=1)

assert nums.max_size == 1

nums.add(1)

assert nums.max_size == 1

nums.add(2)

assert nums.max_size == 2

nums.add(3)

assert nums.max_size == 4

nums.add(4)

assert nums.max_size == 4

nums.add(5)

assert nums.max_size == 8

nums.add(6)

assert nums.max_size == 8

This work is licensed under a
Creative Commons Attribution-NonCommercial 4.0 International License.