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 with a fixed number of items with 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, a bigger chunk of memory is allocated once the contagious memory is filled. 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 an 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 the 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 arr2 is our new list now.
- 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 first created a dynamic array class that behaves 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
- Python Memory Error | How to Solve Memory Error in Python
- Working with CRUD in Python
- Knapsack Problem in Python With Various Ways to Solve
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!