Last Updated on April 25, 2023 by Prepbytes
An array is a collection of elements that are stored in contiguous memory locations. In traditional arrays, the size of the array is fixed at the time of initialization. This makes them rigid and unable to adapt to changing program requirements. To overcome this limitation, dynamic arrays were introduced. In this article, we will learn what a dynamic array is, the features of a dynamic array, how to resize a dynamic array, and how to build a dynamic array.
What is a Dynamic Array?
A dynamic array, also known as a resizable array, is an array whose size can be changed during runtime. Unlike traditional arrays, the size of dynamic arrays can be increased or decreased as per the program’s requirement.
To understand dynamic arrays with a real-life example, let’s consider a grocery shopping list. Suppose you have a shopping list with a fixed number of items that you need to buy every week. A traditional array can be used to represent this list, where each item is stored in a fixed index of the array. However, what if you want to add more items to the list? You would need to create a new array with a larger size and copy the existing items over, which can be time-consuming and inefficient.
This is where dynamic arrays come in. With a dynamic array, you can add or remove items from the list as needed without worrying about the size of the array. For example, if you need to add a new item to your shopping list, you can simply append it to the end of the dynamic array, which will automatically resize to accommodate the new item.
Similarly, if you decide to remove an item from the list, the dynamic array can resize itself to remove the item and adjust the size accordingly. This flexibility of dynamic arrays makes them an essential tool in many programming applications, especially when dealing with large data sets or uncertain data requirements.
Key Features of Dynamic Array
Dynamic arrays have many key features that make them a popular choice among programmers. Some of the key features of dynamic arrays are:
1. Add Element in Dynamic Array
The key feature of a dynamic array when adding an element is the ability to increase the array size when it is insufficient. This is done automatically, allowing an element to be added at the end of the existing array with a specified index. However, this resizing process can be expensive in terms of time and memory usage, as it takes O(n) time to perform all of the copying, where n is the number of entries in our array. Therefore, adding typically takes O(1) time and occasionally O(n) time. In contrast, appends in a fixed-length array only require O(1) processing time.
2. Delete Element in Dynamic Array
Another key feature of dynamic arrays is the ability to remove an element from the 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. This process is essential for maintaining the dynamic nature of the array, as it allows elements to be removed from anywhere within the array.
3. Resize of Array Size in Dynamic Array
Dynamic arrays are designed to be flexible, so their size can be changed as required. 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. The resize operation is a key feature of dynamic arrays that allows them to adapt to changing program requirements.
4. Efficient Memory Usage
Another key feature of dynamic arrays is that they use memory efficiently. Dynamic arrays only consume as much memory as required, which is because they are created using memory allocation routines that allow for the allocation of memory on an as-needed basis. This feature is particularly useful when dealing with large data sets, as it ensures that memory usage is optimized.
How Does Dynamic Array Work?
Let’s say we want to create an array of integers to store the grades of students in a class. We start with an empty dynamic array of size 0.
We then add the first grade, let’s say it’s 85. The dynamic array checks if there is enough space in its current block of memory. Since the array is empty, there is no memory allocated yet, so the dynamic array allocates a block of memory for one integer and stores the grade 85 in it.
Next, we add another grade, let’s say it’s 90. The dynamic array again checks if there is enough space in its current block of memory. Since there is only space for one integer in the current block, the dynamic array allocates a new block of memory for two integers and copies the existing grade 85 into the new block. It then stores the new grade 90 in the second slot of the new block.
We continue adding grades to the dynamic array, and every time the array runs out of space, it allocates a new, larger block of memory and copies the existing elements into it. The new block is typically twice the size of the old block to minimize the number of reallocations needed.
Now, let’s say we want to delete the second grade (90) from the array. The dynamic array shifts all the elements after the deleted element one position to the left, filling in the gap left by the deleted element. This results in unused memory at the end of the array, which can be reclaimed using the shrinkSize() function if needed.
Implementation of Dynamic Array
Below is the code implementation of a dynamic array in various programming languages.
#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: 8Conclusion
In conclusion, dynamic arrays are a fundamental data structure that provides flexibility and efficient memory usage. Their key features include the ability to add and delete elements, resize the array size, and efficient memory usage. While resizing can be costly, dynamic arrays are optimized for frequent access and infrequent resizing, making them a popular choice for a wide range of programming applications.
FAQs on Dynamic Array
Here are some frequently asked questions on the dynamic array.
Q1: How does a dynamic array differ from a static array?
Ans: A static array has a fixed size that cannot be changed during runtime, whereas a dynamic array can resize itself to accommodate additional elements.
Q2: What is the time complexity of adding an element to a dynamic array?
Ans: Adding an element to a dynamic array typically takes O(1) time, but occasionally takes O(n) time when the array needs to be resized.
Q3: What is the time complexity of deleting an element from a dynamic array?
Ans: Deleting an element from a dynamic array typically takes O(n) time, as all the remaining elements after the deletion point need to be shifted to fill the gap.
Q4: Can a dynamic array be multidimensional?
Ans: Yes, a dynamic array can be multidimensional, allowing for the storage of data in multiple dimensions, such as rows and columns.
Q5: What happens if you try to access an index that is out of bounds in a dynamic array?
Ans: If you try to access an index that is out of bounds in a dynamic array, it can cause a runtime error or segmentation fault.
Q6: What is the difference between a dynamic array and a linked list?
Ans: A dynamic array stores its elements in contiguous memory locations, allowing for random access to its elements. A linked list, on the other hand, stores its elements in a chain of nodes, allowing for efficient insertion and deletion of elements.
Q7: What are some common use cases for dynamic arrays?
Ans: Dynamic arrays are commonly used in programming applications where the number of elements to be stored is not known beforehand, such as in data structures like stacks, queues, and hash tables. They are also used in applications that require frequent additions or deletions of elements, such as in text editors and spreadsheet programs.