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 if element not found;
        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 {
        cout << "Element not found " << endl;
    }
    return 0;
}
class DynamicArray {

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

    public DynamicArray()
    {
        array = new int[1];
        count = 0;
        size = 1;
    }
    
    public void add(int data)
    {

        // 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
        da.add(1);
        da.add(2);
        da.add(3);
        da.add(4);
        da.add(5);
        da.add(6);
        da.add(7);
        da.add(8);
        da.add(9);

        // 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
        da.addAt(1, 22);

        // 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.

Leave a Reply

Your email address will not be published. Required fields are marked *