Implementation of Dynamic Array in Python

In this tutorial, we will learn how to implement a Dynamic array in Python. A Dynamic array in Python is similar to a regular array, but the only difference is that a dynamic array can ‘dynamically change’ its size. This dynamic change of the size occurs at runtime. A dynamic array’s size does not need to be defined beforehand.

Our dynamic array is going to take some methods like add, delete, and many more. We will define a class for the array. This class will contain the methods stated before. Firstly, we need to import the ctypes library in Python. It provides C compatible data types and allows calling functions in DLLs or shared libraries.

Importing Libraries in Python

import ctypes

Now we create a class that consists of the first method.

class DynamicArray(object): 
    def __init__(self): 
        self.n = 0 
        self.size = 1 
        self.A = self.make_array(self.size)
    def __len__(self):
        return self.n

The second step is to create an add and remove method for this dynamic array.

def add(self, ele): 
    if self.n == self.size: 
        self._reshape(2 * self.size) 
    self.A[self.n] = ele
    self.n += 1

def remove(self): 
    if self.n==0: 
        print("Array is empty, Please add an element to delete") 
        return	
    self.A[self.n-1]=0
    self.n-=1

If the array is empty the above code will print an error message. The array is not empty so it will delete the element and decrease the size of the array.

def appendAt(self, item, ind):
    if ind < 0 or ind > self.n:
        print("Please enter with the range of the index !")
        return
    if self.n == self.size:
        self._reshape(2*self.size)
    for i in range(self.n-1, ind-1, -1):
        self.A[i+1] = self.A[i]
    self.A[ind] = item
    self.n += 1

If the index specified is less than or greater than the current index size it will print an error message. A simple for loop is used to add the element and also to increase the size of the array.

def deleteAt(self, ind):
    if self.n == 0:
        print("Array is empty, Please add an element first !!")
        return
    if ind < 0 or ind >= self.n:
        return indError("The index is not within the range !! ")
    if ind == self.n-1:
        self.A[ind] = 0
        self.n -= 1
        return
    for i in range(ind, self.n-1):
        self.A[i] = self.A[i+1]
    self.A[self.n-1] = 0
    self.n -= 1

The above function will delete an element in the specified index and if the index is not present will display an error message. If the array is empty it will also display an error message. As soon as the element is deleted, the size of the dynamic array reduces by 1.

def __getiele__(self, k):
    if not 0 <= k < self.n:
        return indError('k is out of bounds !')
    return self.A[k]

def _reshape(self, new_size):
    B = self.make_array(new_size)
    for k in range(self.n):
        B[k] = self.A[k]
    self.A = B
    self.size = new_size

def make_array(self, new_size):
    return (new_size * ctypes.py_object)()

The above three functions will get the element at the specified index. The second function will resize the shape of the dynamic array and the third function will make a dynamic array of the specified size.

Now to test our code we will add use the functions defined above and check whether our dynamic array works.

arr = DynamicArray()
arr.add(1)
arr.add(23)
arr.appendAt(25,2)
arr.add(12)
arr.add(34)

print(arr.__len__())
print(arr.__getiele__(1))

arr.remove()
print(arr.__getiele__(3))
print(arr.__len__())

arr.add(10)
arr.add(70)
print(arr.__len__())

arr.deleteAt(1)
print(arr.__getiele__(2))
print(arr.__len__())

The output will for the above code is:

5
23
12
4
6
12
5
5

The complete code:

import ctypes

class DynamicArray(object):
    def __init__(self):
        self.n = 0
        self.size = 1
        self.A = self.make_array(self.size)
    
    def __len__(self): 
        return self.n 

    def add(self, ele):
        if self.n == self.size:
            self._reshape(2 * self.size)
        self.A[self.n] = ele
        self.n += 1

    def remove(self):
        if self.n == 0:
            print("Array is empty, Please add an element first.")
            return
        self.A[self.n-1] = 0
        self.n -= 1

    def appendAt(self, item, ind):
        if ind < 0 or ind > self.n:
            print("Please enter with the range of the index !")
            return
        if self.n == self.size:
            self._reshape(2*self.size)
        for i in range(self.n-1, ind-1, -1):
            self.A[i+1] = self.A[i]
        self.A[ind] = item
        self.n += 1

    def deleteAt(self, ind):
        if self.n == 0:
            print("Array is empty, Please add an element first !!")
            return
        if ind < 0 or ind >= self.n:
            return indError("The index is not within the range, Deletion is not possible.")
        if ind == self.n-1:
            self.A[ind] = 0
            self.n -= 1
            return
        for i in range(ind, self.n-1):
            self.A[i] = self.A[i+1]   
        self.A[self.n-1] = 0
        self.n -= 1

    def __getiele__(self, k):
        if not 0 <= k < self.n:
            return ('k is out of bounds !')

        return self.A[k]

    def _reshape(self, new_size):
        B = self.make_array(new_size)
        for k in range(self.n):
            B[k] = self.A[k]
        self.A = B
        self.size = new_size

    def make_array(self, new_size):
        return (new_size * ctypes.py_object)()


arr = DynamicArray()
arr.add(1)
arr.add(23)
arr.appendAt(25,2)
arr.add(12)
arr.add(34)

print(arr.__len__())
print(arr.__getiele__(1))

arr.remove()
print(arr.__getiele__(3))
print(arr.__len__())

arr.add(10)
arr.add(70)
print(arr.__len__())

arr.deleteAt(1)
print(arr.__getiele__(2))
print(arr.__len__())

To know more about dynamic array in different programming languages, you can visit these sites:

Leave a Reply

Your email address will not be published. Required fields are marked *