Last Updated on July 15, 2024 by Abhishek Sharma
Dynamic arrays are a fundamental data structure in computer science, offering flexibility and efficiency for managing collections of elements. Unlike static arrays with a fixed size, dynamic arrays can grow and shrink as needed, providing significant advantages in scenarios where the size of the data set is unpredictable. This adaptability makes dynamic arrays a crucial tool for various applications, from simple list management to complex algorithm implementations. Understanding the underlying mechanics of dynamic arrays, including their memory allocation and resizing strategies, is essential for optimizing performance and resource utilization in software development.
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
Dynamic arrays are a versatile and powerful data structure that addresses the limitations of static arrays by offering adjustable storage capacity. Their ability to dynamically resize, combined with efficient indexing and manipulation operations, makes them ideal for a wide range of applications. However, it is important to be mindful of the potential performance trade-offs associated with resizing operations and memory usage. By leveraging dynamic arrays effectively, developers can build more flexible and efficient programs that handle varying data sizes with ease.
FAQs on Dynamic Array
Here are some frequently asked questions on the dynamic array.
Q1: What is a dynamic array?
A1: A dynamic array is a data structure that allows for automatic resizing as elements are added or removed. Unlike static arrays, which have a fixed size, dynamic arrays can grow or shrink to accommodate the number of elements they store.
Q2: How does a dynamic array differ from a static array?
A2: The primary difference is that static arrays have a fixed size determined at the time of creation, while dynamic arrays can change their size dynamically during runtime. This makes dynamic arrays more flexible for situations where the amount of data is not known in advance.
Q3: How is memory managed in a dynamic array?
A3: Dynamic arrays typically use a strategy of allocating an initial fixed size and then resizing by allocating a new array with a larger capacity and copying the elements to it when the original array becomes full. This process is known as dynamic resizing or reallocation.
Q4: What is the typical resizing strategy for dynamic arrays?
A4: A common resizing strategy is to double the array’s capacity when it becomes full. This helps to balance the time complexity of insertion operations, maintaining an average time complexity of O(1) for append operations over a series of insertions.
Q5: Are there any drawbacks to using dynamic arrays?
A5: One potential drawback is the overhead associated with resizing operations, which can be costly in terms of time and memory. Additionally, because dynamic arrays allocate memory in contiguous blocks, they may experience fragmentation and inefficiencies in memory usage.
Q6: How do dynamic arrays handle element removal?
A6: When elements are removed, dynamic arrays may reduce their size to free up unused memory. However, this is usually done less frequently than resizing for additions to avoid excessive reallocations. Some implementations use thresholds to determine when to shrink the array.
Q7: What are some common use cases for dynamic arrays?
A7: Dynamic arrays are used in various applications, including implementing list data structures, dynamic buffers for input/output operations, dynamic storage for elements in algorithm implementations, and more.