Python Dynamic Array: Implementation with Examples

Hello coders!! In this article, we will be discussing python dynamic array implementation. We will also cover various examples to make our concept clear. An array in Python is a container that holds a fixed number of items having the same data type. So, let us now get into our topic in detail.

What is a Dynamic array in Python?

A dynamic array is just like a normal array. The difference between the two is that the size of a dynamic array can be dynamically modified at runtime. We don’t need to specify the size of the array beforehand. In a dynamic array, once the contagious memory is filled, a bigger chunk of memory is allocated. The contents of the original array are copied to this new space, and the available slots are filled continuously.

In Python, list objects are mutable. This means that we can easily add or remove an item from the list during run time without specifying any size. So, a list acts as a dynamic array in Python.

Example1: Creating an empty python dynamic array :

list1 = []
type (list1)

OUTPUT:

< class ' list ' >

Example 2: Adding items to empty list:

list1=[]
list1.append(1)
list1.append(5)
print(list1)

OUTPUT:

[ 1 , 5 ]

Here, we have used the append() method to add the elements to the list dynamically. This method adds the element to the end of the list.

Example 3: Removing an element from list:

list1.pop()
print(list1)

OUTPUT:

[ 1 ]

We have used the pop() method to remove the last element of the list. This method removes the element of the specified position. If the position is not specified, it removes the last element.

Logic for Python dynamic array implementation:

If a list, say arr1, having a size more than that of the current array needs to be appended, then the following steps must be followed:

  • Allocate a new array,say arr2 having a larger capacity
  • Set arr2[i] = arr1[i], for i = 0,1….n-1, where n is the current number of the item.
  • Set arr1=arr2, as now arr2 is our new list.
  • Now, just append a new item to arr1.

Let us see its implementation in Python:

import ctypes 

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

		return self.n 
	
	def __getitem__(self, k): 

		if not 0 <= k <self.n: 

			return IndexError('K is out of bounds !') 
		
		return self.A[k] 
		
	def append(self, ele): 

		if self.n == self.capacity: 

			self._resize(2 * self.capacity) 
		
		self.A[self.n] = ele 
		self.n += 1

	def insertAt(self,item,index): 

		if index<0 or index>self.n: 
			print("please enter appropriate index..") 
			return
		
		if self.n==self.capacity: 
			self._resize(2*self.capacity) 
			
		
		for i in range(self.n-1,index-1,-1): 
			self.A[i+1]=self.A[i] 
			
		
		self.A[index]=item 
		self.n+=1


		
	def delete(self): 

		if self.n==0: 
			print("Array is empty deletion not Possible") 
			return
		
		self.A[self.n-1]=0
		self.n-=1
	
	
	def removeAt(self,index): 
	

		if self.n==0: 
			print("Array is empty deletion not Possible") 
			return
				
		if index<0 or index>=self.n: 
			return IndexError("Index out of bound....deletion not possible")		 
		
		if index==self.n-1: 
			self.A[index]=0
			self.n-=1
			return		
		
		for i in range(index,self.n-1): 
			self.A[i]=self.A[i+1]			 
			
		
		self.A[self.n-1]=0
		self.n-=1

		
	def _resize(self, new_cap): 

		B = self.make_array(new_cap) 
		
		for k in range(self.n):  
			B[k] = self.A[k] 
			
		self.A = B 
		self.capacity = new_cap 
		
	def make_array(self, new_cap): 

		return (new_cap * ctypes.py_object)() 

Explanation:

We have first created a dynamic array class which will behave like a Python list. Let us understand the different functions in detail:

def __init__(self):

  • self.n -> count the actual number of elements
  • self.capacity -> default capacity is set as 1
  • self.A -> array with the given capacity

def __len__(self):

  • Returns the number of elements stored in the array

def __getitem__(self, k):

  • Return the element at position k
  • At first it checks if the position k is within the bounds of the array
  • If it is within the bound of the array, the element in that position is returned

def append(self, ele):

  • Add the element at the end of the array
  • If there is not enough capacity available in the array, the size of the array is doubled
  • self.n is set to the index of the element and incremented

def insertAt(self,item,index):

  • Insert the given element in the specified index

def delete(self):

  • Delete the array element from the end of the array

def removeAt(self,index):

  • Remove the element at the specified index

def _resize(self, new_cap):

  • Resize the array to a bigger size
  • Declare a new array having bigger size
  • Reference all existing values
  • Call A the new bigger array
  • Reset the capacity

def make_array(self, new_cap):

  • Return a new array with new_cap capacity

Must Read

Conclusion:

With this, we come to an end with this article. The Python dynamic array is relatively easy using Python as the list acts as a dynamic array itself. However, one can implement their own code in Python using the ctype module.

However, if you have any doubts or questions, do let me know in the comment section below. I will try to help you as soon as possible.

Happy Pythoning!

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments