# Dynamic Array in Data Structures A homogenous, fixed-size data structure is an array. The constant size of arrays is one of its drawbacks. It implies that when declaring the array, the number of items must be specified. Here, the issue of what to do if we want to introduce an element but there isn’t enough room for it to fit emerges. The idea of a dynamic array is created in this situation. It dynamically increases the array’s size.

We will learn what a dynamic array is, what its features are, how to resize a dynamic array, and how to build a dynamic array in this part.

## What is a Dynamic Array?

A list data structure with changing sizes is the dynamic array. If there is not enough capacity for the new element to be inserted, it expands automatically. We may add and remove parts due to it. At runtime, memory is allocated via the heap. During operation, its size may alter.

When we try to insert anything into a dynamic array (a vector in C++ or an ArrayList in Java), and there isn’t enough space, the array immediately extends. The space typically doubles in size. By creating a fixed-size array that is often bigger than the number of elements immediately needed, a straightforward dynamic array may be created. The dynamic array’s items are placed consecutively at the beginning of the underlying array, while the remaining slots at the end are either reserved or unoccupied. In a dynamic array, elements can be added at the end indefinitely by utilizing the reserved space up until it is used up entirely. The size of the underlying fixed-sized array must be expanded when all available space has been used and an extra element is to be added. Resizing typically requires extra because before we can ultimately attach our item, we must allocate a larger array and copy over all of the elements from the array we have outgrown.

## Approach:

When we input an element into an array but the array is already full, we build a function that produces a new array that is either double the size of the original array or as large as we like and copies all of the items into it before returning the new array. We can also make the array smaller in size. delete the element at the end default and at the position also, and add an element at the specified position.

## Key Features of Dynamic Array

The following are the features of Dynamic Array.

### Add Element in Dynamic Array:

Including anything towards the end If the array size is insufficient, increase the array size and add one element at the end of the existing array along with a specified index. It takes O(n) time to perform all of the copying, where n is the number of entries in our array. That is a hefty price to pay for an appendage. Appends in a fixed-length array only require O(1) processing time. But when we insert into a complete array, appends only require O(n) time. And if we increase the array size each time we run out of room, that becomes very uncommon. Thus, adding typically takes O(1) time and occasionally O(n) time. When adding extra components to a dynamic array as needed, you may build a fixed-size array using the following method: ### Delete Element in Dynamic Array:

Remove an element from an array by invoking the removeAt(i) function, where i is an index. The remove() method’s default behavior is to remove an element from the end of the array by simply storing zero at the last position. All right elements on the left side of the provided index are shifted using the removeAt(i) method. ### Resize of Array Size in Dynamic Array:

The function shrinkSize() can release unnecessary memory from an array when the right side of the array has null or zero data (apart from an element you inserted). The size of the underlying fixed-size array must be increased when all available space has been used and an extra element has to be added. Resizing typically costs money because before we can ultimately attach our item, we must allocate a larger array and copy over all of the elements from the array we have outgrown. For the dynamic array, use simple code. When the array in the code below reaches its maximum size, we copy all of its elements to a new double-size array (variable size array). Below is an example of code.

Code Implementation:

```#include <iostream>
using namespace std;

class DynamicArray {
private:
// Pointer to store array created
// using new keyword
int* array = NULL;
// Size of array
int size;

// Container size
int capacity;

public:
// Default constructor with size 1
DynamicArray()
{
capacity = 1;
size = 0;
array = new int[capacity];
}

// Taking size from the user
DynamicArray(int capacity)
{
this->capacity = capacity;
array = new int[capacity];
size = 0;
}

// Returns the size of Array
// i.e Total elements stored currently
int getSize() { return size; }

// Returns the size of container
int getCapacity() { return capacity; }

// Inserting element after last stored index
void push_back(int value)
{
// check is array having size to store element or
// not
if (size == capacity) {

// if not then grow the array by double
growArray();
}

// insert element
array[size] = value;
// increment the size or last_index+1
size++;
}

// Deleting element at last stored index
void pop_back()
{
// Replace the last index by 0
array[size - 1] = 0;

// Decrement the array size
size--;

// Reduce if the container half element of its
// capcity
if (size == (capacity / 2)) {
shrinkArray();
}
}

// Increase the array size by double of current capacity
void growArray()
{

// Creating new array of double size
int* temp = new int[capacity * 2];

capacity = capacity * 2;
// copy element of old array in newly created array
for (int i = 0; i < size; i++) {
temp[i] = array[i];
}

// Delete old array
delete[] array;

// Assign newly created temp array to orignal array
array = temp;
}

// Reduce the size of array by half
void shrinkArray()
{

// Creating new array of half size
capacity = size;
int* temp = new int[capacity];

// copy element of old array in newly created array
for (int i = 0; i < size; i++) {
temp[i] = array[i];
}

// Delete old array
delete[] array;

// Assign newly created temp array to orignal array
array = temp;
}

// Seaching element in the given array
int search(int key)
{
for (int i = 0; i < size; i++) {
if (array[i] == key) {
// If element found return its index
return i;
}
}

return -1;
}

// Insert element at given index
void insertAt(int index, int value)
{
// check is array having size to store element or
// not
if (size == capacity) {

// if not then grow the array by double
growArray();
}

for (int i = size - 1; i >= index; i--) {
array[i + 1] = array[i];
}

array[index] = value;
size++;
}

// Delete element at given index
void deleteAt(int index)
{
for (int i = index; i < size; i++) {
array[i] = array[i + 1];
}

// Replace the last index by 0
array[size - 1] = 0;

// Decrement the array size
size--;

// Reduce if the container half element of its
// capcity
if (size == (capacity / 2)) {
shrinkArray();
}
}

// To Print Array
void printArrayDetails()
{
cout << "Elements of array : ";
for (int i = 0; i < size; i++) {
cout << array[i] << " ";
}
cout << endl;
cout << "No of elements in array : " << size
<< ", Capcity of array :" << capacity << endl;
}

bool isEmpty()
{
if (size == 0) {
return true;
}
else {
return false;
}
}
};

int main()
{
DynamicArray da;

da.push_back(1);
da.push_back(2);
da.push_back(3);
da.push_back(4);
da.push_back(5);
da.push_back(6);
da.push_back(7);
da.push_back(8);
da.push_back(9);
da.push_back(10);
da.push_back(11);

da.printArrayDetails();

da.shrinkArray();
cout << "\nCapcity of array after shrinking : "
<< da.getCapacity() << endl;

cout << "\nAfter inseting at index 3 " << endl;
da.insertAt(3, 50);
da.printArrayDetails();

cout << "\nAfter delete last element ";
da.pop_back();
da.printArrayDetails();

cout << "\nAfter deleting at index 3 ";
da.deleteAt(3);
da.printArrayDetails();

cout << "\nSearching 5 in array ";
int index = da.search(5);
if (index != -1) {
cout << "Element found at index : " << index << endl;
}
else {
}
return 0;
}
```
```class DynamicArray {

private int array[];
private int count;
private int size;

public DynamicArray()
{
array = new int;
count = 0;
size = 1;
}

{

// check no of element is equal to size of array
if (count == size) {
growSize(); // make array size double
} // insert element at end of array
array[count] = data;
count++;
}

// function makes size double of array
public void growSize()
{

int temp[] = null;
if (count == size) {

// temp is a double size array of array
// and store array elements
temp = new int[size * 2];
{
for (int i = 0; i < size; i++) {
// copy all array value into temp
temp[i] = array[i];
}
}
}

// double size array temp initialize
// into variable array again
array = temp;

// and make size is double also of array
size = size * 2;
}

// function shrink size of array
// which block unnecessary remove them
public void shrinkSize()
{
int temp[] = null;
if (count > 0) {

// temp is a count size array
// and store array elements
temp = new int[count];
for (int i = 0; i < count; i++) {

// copy all array value into temp
temp[i] = array[i];
}

size = count;

// count size array temp initialize
// into variable array again
array = temp;
}
}
// function add an element at given index

public void addAt(int index, int data)
{
// if size is not enough make size double
if (count == size) {
growSize();
}

for (int i = count - 1; i >= index; i--) {

// shift all element right
// from given index
array[i + 1] = array[i];
}

// insert data at given index
array[index] = data;
count++;
}

// function remove last element or put
// zero at last index
public void remove()
{
if (count > 0) {
array[count - 1] = 0;
count--;
}
}

// function shift all element of right
// side from given index in left
public void removeAt(int index)
{
if (count > 0) {
for (int i = index; i < count - 1; i++) {

// shift all element of right
// side from given index in left
array[i] = array[i + 1];
}
array[count - 1] = 0;
count--;
}
}

public static void main(String[] args)
{
DynamicArray da = new DynamicArray();

// add 9 elements in array

// print all array elements after add 9 elements
System.out.println("Elements of array:");
for (int i = 0; i < da.size; i++) {
System.out.print(da.array[i] + " ");
}

System.out.println();

// print size of array and no of element
System.out.println("Size of array: " + da.size);
System.out.println("No of elements in array: "
+ da.count);

// shrinkSize of array
da.shrinkSize();

// print all array elements
System.out.println("Elements of array "
+ "after shrinkSize of array:");
for (int i = 0; i < da.size; i++) {
System.out.print(da.array[i] + " ");
}
System.out.println();

// print size of array and no of element
System.out.println("Size of array: " + da.size);
System.out.println("No of elements in array: "
+ da.count);

// add an element at index 1

// print Elements of array after adding an
// element at index 1
System.out.println("Elements of array after"
+ " add an element at index 1:");
for (int i = 0; i < da.size; i++) {
System.out.print(da.array[i] + " ");
}

System.out.println();

// print size of array and no of element
System.out.println("Size of array: " + da.size);
System.out.println("No of elements in array: "
+ da.count);

// delete last element
da.remove();

// print Elements of array after delete last
// element
System.out.println("Elements of array after"
+ " delete last element:");
for (int i = 0; i < da.size; i++) {
System.out.print(da.array[i] + " ");
}

System.out.println();

// print size of array and no of element
System.out.println("Size of array: " + da.size);
System.out.println("No of elements in array: "
+ da.count);

// delete element at index 1
da.removeAt(1);

// print Elements of array after delete
// an element index 1
System.out.println("Elements of array after"
+ " delete element at index 1:");
for (int i = 0; i < da.size; i++) {
System.out.print(da.array[i] + " ");
}
System.out.println();

// print size of array and no of element
System.out.println("Size of array: " + da.size);
System.out.println("No of elements in array: "
+ da.count);
}
}
```

Output

``````Elements of array:
1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0
Size of array: 16
No of elements in array: 9
Elements of array after shrinkSize of array:
1 2 3 4 5 6 7 8 9
Size of array: 9
No of elements in array: 9
Elements of array after add an element at index 1:
1 22 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0
Size of array: 18
No of elements in array: 10
Elements of array after delete last element:
1 22 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0
Size of array: 18
No of elements in array: 9
Elements of array after delete element at index 1:
1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0
Size of array: 18
No of elements in array: 8``````

Conclusion
This blog helps you for a better understanding of dynamic array in data structures. We hope this blog enhances your knowledge and boosts your confidence for solving more complex problems.