When we create a regular array, its size is fixed. For example, if we make an array of length 5, we can add only five items to it, not more. On the other hand, dynamic arrays are resizable, i.e., the size of an array can change in the program. It can be changed by adding new items or removing existing ones. Therefore, we do not need to determine the size ahead of time, we can add elements on the go, and the size of an array will increase automatically.
How to implement Dynamic Arrays?
So, let’s get started and see how we can implement dynamic arrays.
- Initially, we create an array of a specific capacity, let’s say 2, and it represents our dynamic array. At this time, the size is 0, i.e., from the user’s perspective, the array is empty. However, internally, it is still a fixed-sized array having a temporary capacity of 2. It is temporary because it can change if required.
- Later on, when the user appends an item, the program checks whether the current size of the dynamic array is equal to its capacity or not. If it is not, then the element gets inserted at this position, and the size gets incremented.
- If the size is equal to the capacity, then the array gets resized, and the item gets appended in the new resized array.
- To resize it, we create a new array of an increased capacity, let’s say double the previous one. Then, we copy all the items from the previous array to the new one. This new array represents our dynamic array now.
- To pop the last item from the array, we decrement the size and return the deleted element.
Consider the following implementation of a dynamic array in Python. It contains the following functionalities.
- DynamicArray(type) creates a dynamic array of a given type. It supports integer, float, double, and character type.
- append() inserts an item at the end of an array.
- pop() removes the last element and returns it.
- length() returns the size of the array.
- getItem() returns the item at a given index.
The code
import array
class DynamicArray(object):
def __init__(self, type):
self.__capacity = 2 # initial capacity of 2
self.__size = 0 # size of the array/ index for the next item
self.__type = type
self.__array = self.__createArray(
self.__capacity
) # initially create an array of size 2
def length(self): # return length of the array
return self.__size
def append(self, item):
if self.__size == self.__capacity: # resize array if the capacity is full
self.__resize(2 * self.__capacity)
self.__array[self.__size] = item # append item
self.__size = 1
def pop(self):
if self.__size == 0:
raise Exception("Array is empty")
self.__size -= 1 #
item = self.__array[self.__size]
return item
def getItem(self, k):
if k < 0 or k >= self.__size:
raise Exception("Index Out of Bound")
else:
return self.__array[k]
def __resize(self, cap):
new_array = self.__createArray(cap)
for i in range(0, self.__size): # copy previous items
new_array[i] = self.__array[i]
self.__array = new_array
self.__capacity = cap
def __createArray(self, cap): # create array of a specific type
if self.__type == "i":
return array.array("i", [0] * cap)
elif self.__type == "u":
return array.array("u", ["-"] * cap)
elif self.__type == "f":
return array.array("f", [0.0] * cap)
elif self.__type == "d":
return array.array("d", [0.0] * cap)
else:
raise Exception(
"Invalid data type. Available data types are: i for int, u for character, f for float, and d for double."
)
arr = DynamicArray("i") # dynamic array of type int
arr.append(2)
arr.append(4)
arr.append(1)
arr.append(8)
print("Array Items:")
for i in range(0, arr.length()):
print(arr.getItem((i)))
print("Delete the last item:", arr.pop())
print("New length:", arr.length())
Output
Array Items:
2
4
1
8
Delete the last item: 8
New length: 3