Reading time: 30 minutes | Coding time: 15 minutes

Array is collection of data at adjacent/ continuous memory allocation. But problem here is that Array has fixed size. If user does not know then size of array or data beforehand then the solution is to use Linked List.

The problem with Linked list is the memory access is slow. Hence, Dynamic Array comes into picture which is a modified version of Array.

Dynamic Array is also called ArrayList in Java and Vector in C++

In Dynamic array, the size of the array can be changed at time of execution of program. Basically, what we do in Dynamic Array is create a resize function and the size is adjusted according to input by user.

The key idea is both adding and deleting element will continue as if it is an ordinary array but when there is no space left in the array, the size of the array will be doubled and all exisiting elements will be copied to the new location.

With addition to resize function, all elements of previous array is copied to new array and then new element is appended. This new array is Dynamic Array.
The previous array memory is then disallocated.

Normally, we twice the size of array but that totally depend upon situation or what user wants.

Operations in a Dynamic Array

• Resize Method
• Add Method (with add at a specific index)
• Delete Method (with delete at a specific index)

Following is the summary table:

Operation	Worst case time	Average case time	Best time
Resize	O(N)	O(1)	O(N)
Add	O(1)	O(1)	O(1)
Add at an index	O(N)	O(N)	O(1)
Delete	O(1)	O(1)	O(1)
Delete at an index	O(N)	O(N)	O(1)

Time Complexity

When we increase the size of array by 1, then elements are copied from previous to new array and then new element is appended , it takes O(N).

When we double the size of array, it will takes O(1) and sometimes O(N). Basically when we increase size one by one, then all elements all copied everytime, create again array and then append. But when we double the size, elements all copied only once and then append so the average time becomes O(1).

Hence, the resize operation takes O(1) in average and O(N) in the worst case.

Resize Method

This method is used to increase the size of Array basically we are creating a new array with double size of previous array.
This method only works when the condition is satisfied i.e. there is no more space left to enter new elements.

Pseudo Code

Pseudo code for resize()

• First, we will create a new Array called tempArray[] and assign it null.
• Then, if condition to check there is no more space left to enter new elements.
  if(count == size)
• Assign size of array
• Apply for loop to copy all elements from array to tempArray

for (int i = 0; i < size; i++){    
		tempArray[i] = array[i];
     } 

• Then assign: array = tempArray
• Double the size of array

Add Method

We can add elements in Dynamic Array by using two methods:

1. add(): It will add element at the end of array.
2. addAt(index, data): It will add element at the specific position.

Pseudo Code

Pseudo code for add()

• This method will help to add new element.
• Resize function will be call to resize the array.
• Then we will assign the element at end position:

array[count] = element
count++ 

Pseudo code for addAt()

• This method will help to add array at specific position
• First resize method will be called to resize array
• Then we will shift all element from right from given index

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

• Then we will insert element at given index

array[index] = data; 
count++;

Delete Method

Similary, we can delete elements in Dynamic Array by using two methods:

1. remove(): It will remove element at the end of array.
2. removeAt(index): It will remove element at the specific position.

Pseudo Code

Pseudo code for remove()

• This method will help to remove element from end.
• First we will check if (count > 0) i.e. Array has elements or not
• Then we will assign value 0 at end.

if (count > 0) { 
  array[count - 1] = 0; 
  count--; 
  } 

Pseudo code for removeAt()

• This method will help to remove element from specific positon.
• First we will check if (count > 0) i.e. Array has elements or not
  if (count > 0)
• Then we will shift all element of right side from given index in left

for (int k = index; k < count - 1; k++) {  
     array[k] = array[k + 1]; 
     } 

• Then assign value 0 at that index

array[count - 1] = 0; 
count--; 

Implementation

Following is the Java implementation of Dynamic Array:

public class DynamicArray 
{
	private int array[];
	private int count;
	private int size;

	 public DynamicArray()
     {
		array = new int[1];
		count = 0;
		size = 1;
	}
    
// add Method	
public void add(int element)
{
  resize();
  array[count] = element;
  count++;	
}

public void addAt(int index, int data) 
{ 
    resize();  
    for (int j = count - 1; j >= index; j--) 
    { 
      // shifting all element from right from given index 
      array[j + 1] = array[j]; 
    } 

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

// Delete Method
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 k = index; k < count - 1; k++) { 
  
     // shift all element of right side from given index in left 
     array[k] = array[k + 1]; 
     } 
  array[count - 1] = 0; 
  count--; 
 } 
}

//Resize Method
private void resize(){
	
	int tempArray[] = null;
	if(count == size){
	tempArray = new int[size*2];
	for (int i = 0; i < size; i++){    
		tempArray[i] = array[i];   // Copy element from array to tempArray
     } 	
	array = tempArray;
	size = size*2;			  // Doubling the size of array
   }
}

public static void main(String [] args)
{
	DynamicArray a = new DynamicArray();
		
	System.out.println("Before Insertion of New elements");
	System.out.println("Count " + a.count);
	System.out.println("Size " + a.size);
	
	System.out.println("Elements that are inserted");
	a.add(5);
	a.add(7);
	a.add(9);
	a.add(22);
	a.add(11);
	a.addAt(2,8);
	a.remove();
	a.removeAt(1);
	
	for(int i = 0; i< a.count; i++){  	// Printing elements of array
		System.out.println(a.array[i]);
	}

	System.out.println("After Insertion of New elements");
	System.out.println("Count " + a.count);
	System.out.println("Size " + a.size);

	}
}

Output