The drawback of regular arrays is that we cannot adjust their size in the middle of the code execution. In other words, it will fail to add the (n + 1)th element if we allocate an array size equal to n. One idea would be to allocate a large array, which could waste a significant amount of memory. So what is an appropriate solution to this problem? Think! We solve this problem using the idea of the dynamic array where we can increase the array size dynamically as we need them.
Suppose we start with an array size 1 and double its size whenever we run out of space. This process involves allocating a new array of double size, copying the data of the old array to the lower half of the new one, and deleting the space used by the old array. The extra overhead involved in this process is recopying the old data to the new array on each doubling. The crucial question is: how many times does an element need to be recopied after n number of insertions? Let's visualize.
This doubling process continues if we insert the 8th, 16th, 32nd ... elements. In general, after the i number of doubling, the new array size would be 2^i, and there will be 2^(i-1) elements in the array. So there is no need to resize the array from 2^(i-1) + 1 to 2^i - 1 insertion. After the 2^i th insertion, the array will get full, and we need to double the array size to 2^(i + 1) and copy the 2^i elements in the new array.
From the above observations, after i number of doubling, if there are n elements in the array, then 2^i = n => i = logn. So after n insertion operations, we need to double the array size logn times. Think! So total number of copy operations after logn number of doubling = 1 + 2 + 4 + ..... n/4 + n/2 + n
= n + n/2 + n/4 + ..... + 4 + 2 + 1
= n (1 + 1/2 + 1/4 + ..... + 4/n + 2/n + 1/n)
≤ n (1 + 1/2 + 1/4 + ..... + 4/n + 2/n + 1/n + .... till infinity)
≤ n * 1/(1 - 1/2) ≤ 2n
Note: The sum of infinite geometric series: 1 + 1/r + 1/r^2 + 1/r^4 + ...till infinity = 1/(1 - r)
So for logn number of insertions (at each doubling point), we need to perform at max 2n copy operations. On another side, there is no need to perform copy operations for remaining n - logn insertions. Total copy operation per insertion = 2n / n = 2. So on average, each n element moves only two times, which is constant.
For implementing a dynamic array as an abstract data type in C++ or Java, or some other programming language, we need to define these things:
Now we define and implement dynamic array operations to work on the data. We can also define some other operations based on need.
To work with the oops principles, we declare array pointer A, currSize, and capacity as a private member of the class. This is encapsulation, where we hide the internal details of an object. Similarly, we declare a constructor and operations as public members of the class. This is an abstraction where we expose only relevant details to the outside world.
Note: For better abstraction, we can declare reSizeArray() and shrinkArray() methods as private members of the class, because both operations will be used internally by the insertion and deletion methods. So there is no need to provide public access to these methods. Think!
public class DynamicArray
{
Private
int A[]
int currSize
int capacity
void reSizeArray()
{
//Implementation code
}
void shrinkArray()
{
// Implementation code
}
public:
DynamicArray()
{
A = new int[1]
currSize = 0
capacity = 1
}
void insertAtEnd(int x)
{
// Implementation code
}
void insertAtMiddle(int index, int x)
{
// Implementation code
}
void deleteAtEnd()
{
// Implementation code
}
void deleteAtMiddle(int index)
{
// Implementation code
}
...//More dynamic array operations...
}
This operation is required when the allocated array space gets full with the defined capacity after some sequence of insertion. So we call this method when currSize == capacity during the insertion.
Pseudocode implementation
void resizeArray()
{
if (currSize == capacity)
{
int temp[2 * capacity]
for (int i = 0; i < capacity; i = i + 1)
temp[i] = A[i]
free(A)
A = temp
capacity = 2 * capacity
}
}
If(currSize < capacity), then we easily insert the element at index A[currSize] and increase currSize by 1. Otherwise, the array is full of its capacity. So we call the resizeArray() operation to double its size, add element x at index A[currSize] and increase currSize by 1.
Pseudocode implementation
void insertAtEnd(int x)
{
if (currSize == capacity)
resizeArray()
A[currSize] = x
currSize = currSize + 1
}
If(currSize == capacity), then we resize the array by double and move elements from index to currSize - 1 to one upward. This process will create a space for the newly arriving element x. Now we insert the element x at A[index] and increase currSize by 1. Note: If(currSize < capacity), we don't need to resize the array.
Pseudocode implementation
void insertAtMiddle(int index, int x)
{
if (currSize == capacity)
reSizeArray()
for (int i = currSize; i > index; i = i - 1)
A[i] = A[i - 1]
A[index] = x
currSize = currSize + 1
}
After some sequence of deletion, the currSize of the array may be significantly less in comparison to the current capacity. So dynamic array can also deallocate some of the space if its size drops below a certain threshold, such as 1/4th of the current capacity. This would help in reducing the wastage of extra space.
We perform this operation when currSize == capacity/4 during the deletion.
Pseudocode implementation
void shrinkArray()
{
if (currSize == capacity/4)
{
int temp[capacity/2]
for (int i = 0; i < currSize; i = i + 1)
temp[i] = A[i]
capacity = capacity/2
free(A)
A = temp
}
}
We need to check the current size of the array. if(currSize == 0), then array is empty or there will no element in the array. Otherwise, we remove the element at index currSize - 1 and reduce currSize by 1. During this process, if (currSize == capacity/4), then we call the shrinkArray() method to reduce the dynamic array size by half.
Pseudocode implementation
void deleteAtEnd()
{
if (currSize == 0)
print("dynamic array is empty!")
else
{
A[currSize - 1] = INT_MIN
currSize = currSize - 1
if (currSize == capacity/4)
shrinkArray()
}
}
We need to check the current size of the array. if(currSize == 0), array is empty or there will no element in the array. Otherwise, we move all the elements from currSize - 1 to index by 1 downward, set the value at A[currSize - 1] equal to 0, and decrement currSize by 1. During this process, if (currSize == capacity/4), then we call the shrinkArray() method to reduce the dynamic array size by half.
Pseudocode implementation
void deleteAtMiddle(int index)
{
if (currSize == 0)
print("dynamic array is empty!")
else
{
for (int i = index; i < currSize - 1; i = i + 1)
A[i] = A[i + 1]
A[currSize - 1] = INT_MIN
currSize = currSize - 1
if (currSize == capacity/4)
shrinkArray()
}
}
Enjoy learning, Enjoy algorithms!