Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

python
community creator

How to implement dynamic array in Python

Sai Manoj Reddy

A dynamic array automatically grows when you try to make an insertion into a fully occupied list. Once all the space is consumed, and an additional element is ready to be added, the underlying fixed-sized array needs to increase in size.

Resizing is usually expensive because you have to allocate a bigger array and copy all of the elements over from the array we have overgrown before we can append our item.

Implementation

import ctypes

class DynamicArray:
  def __init__(self):
    self.n=0 # count actual elements
    self.size=1 # default array capacity
    self.A=self._make_array(self.size) # low level arrays-->creating an array
  def __len__(self):
    return self.n
  def append(self,item):
    if self.n==self.size: # not enough memory or rooms
      self._resize(2*self.size) # double the capacity
    self.A[self.n]=item # I am inserting element into the array
    self.n+=1
  def _resize(self,new_capacity):
    # 1.Creata new Array
    B=self._make_array(new_capacity)
    self.size=new_capacity
    # 2.Copy the elemnts from old array to new array
    for i in range(self.n):
      B[i]=self.A[i]
    #3 .Reassign(delete the previous array)
    self.A=B
  def _make_array(self,new_capacity):
    return (new_capacity*ctypes.py_object)()
  def __str__(self):
    temp=""
    for i in range(self.n):
      temp=temp+str(self.A[i])+","
    temp=temp[:-1]
    return "["+temp+"]"
arr=DynamicArray() # object creation
arr.append(100)
arr.append(200)
arr.append(500)
print(len(arr))
print(arr)
The highlighted code part gives information about the Dynamic Allocation of a new size, for inserting new elements.

RELATED TAGS

python
community creator
RELATED COURSES

View all Courses

Keep Exploring