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)
< class ' list ' >
Example 2: Adding items to empty list:
list1= list1.append(1) list1.append(5) print(list1)
[ 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:
[ 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)()
We have first created a dynamic array class which will behave like a Python list. Let us understand the different functions in detail:
- self.n -> count the actual number of elements
- self.capacity -> default capacity is set as 1
- self.A -> array with the given capacity
- Returns the number of elements stored in the array
- 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
- 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
- Insert the given element in the specified index
- Delete the array element from the end of the array
- Remove the element at the specified index
- 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
- Return a new array with new_cap capacity
- Python Memory Error | How to Solve Memory Error in Python
- Working with CRUD in Python
- Knapsack Problem in Python With Various Ways to Solve
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.