Difference between Static Array and Dynamic Array

 An array is a collection of similar types of data. Each data item present in the array is called the element of the array. The elements of the array share the same variable name but each element has a different index number. Arrays used to organize data and provide operations such as searching and sorting of data.

There are two types of arrays:

  1. Static Arrays
  2. Dynamic Arrays

Static Arrays

Static Arrays is a collection of similar types of data stored at contiguous memory location. Store multiple item of a same type together.


In Java: 

char[] arr = new char[size of Array];

To access element:
0 based indexing.
arr[0] - 1st element of the array.
Size of arr = arr.length;
last element of the array = arr[arr.length-1];

Dynamic Arrays:

In dynamic array, we store the collection of similar types of element but we cannot define the size of the array. In Java dynamic array is created using ArrayList which is the implementation of List interface. When we declare the ArrayList, it creates an array with default size(i.e. 10) and when the array is full it creates a new array of double size and copies the elements of the old array and frees the space of the old array. The same method is followed in other programming languages also.
Time complexity to insert an element is Amortized O(1).
In Dynamic Arrays, when the array becomes full then we create a new array of double the size of the old array and copy the elements of the old array to the new array and free the space occupied by the old array this whole operation takes O(n) time. But these operations are very few. So on average, we say that the overall insertion of an element takes Amortized O(1) time.
 
ArrayList<Object> arr = new ArrayList<>();

Comments

Post a Comment

Popular posts from this blog

Beggars Outside Temple

Problem There are   N   ( N > 0 ) beggars sitting in a row outside a temple. Each beggar initially has an empty pot. When the devotees come to the temple, they donate some amount of coins to these beggars. Each devotee gives a fixed amount of coin(according to his faith and ability) to some   K   beggars sitting next to each other. Given the amount donated by each devotee to the beggars ranging from   i   to   j   index, where   1   <=   i   <=   j   <=   N , find out the final amount of money in each beggar's pot at the end of the day, provided they don't fill their pots by any other means. Example Input: N = 5, D = [[1, 2, 10], [2, 3, 20], [2, 5, 25]] Return: [10, 55, 45, 25, 25] Explanation: => First devotee donated 10 coins to beggars ranging from 1 to 2. Final amount in each beggars pot after first devotee: [10, 10, 0, 0, 0] => Second devotee donated 20 coins to beggars ranging from 2 to...
Read more

Rain Water Trapped

Problem Given an array arr[]  of N non-negative integers representing height of blocks at index i as A i where the width of each block is 1. Compute how much water can be trapped in between blocks after raining. Problem Constraints 1 <=   |arr|   <= 100000 Example Input Input 1: A = [0, 1, 0, 2] Input 2:  A = [1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] Example Output Output 1: 1 Output 2: 6  Question Link https://leetcode.com/problems/trapping-rain-water/ https://practice.geeksforgeeks.org/problems/trapping-rain-water/0   Solution We have to calculate the amount of water to be stored in between the blocks. Solution 1: Brute Force In Brute force approach, We do what it says in the question. For each element in the array, we find the maximum amount of water it can trap. we calculate the minimum of the maximum of left side and right side of the element. Algorithm Initialize res = 0 ; Iterate the array from left to right : Initialize left_max = Integer.MIN_VAL...
Read more