Static Array and Dynamic Arrays.

Static Vs Dynamic

An array is the most useful data structure because it forms a fundamental building block for all other data structures. With the use of array and pointers, we can construct almost every data structure.

What is a Static Array?

A static array is a fixed-length container containing n elements indexable from the range [0, n-1].

What is meant by being ‘indexable?

This means that each slot/index in the array can be referenced with a number.

When and Where is a static Array used?

  • Storing and accessing sequential data.
  • Temporarily storing objects.
  • Used by IO routines as buffers.
  • Lookup tables and inverse lookup tables.
  • Can be used to return multiple values from a function.
  • Used in dynamic programming to cache answers to sub-problems.

Static Array Example:
Static Array

A[0] = 44
A[1] = 12
A[4] = 6
A[7] = 9
A[9] => index out of bounds!
Elements in A are referenced by their index. There is no other way to access elements in an array. Array indexing is zero-based, meaning the first element is found in position zero.

What is a Dynamic Array?

The dynamic array is the array that can grow and shrink in size dynamically as needed.

How can we implement a dynamic array?

One way is to use a static array!
Create a static array with an initial capacity.
Add elements to the underlying static array, keeping track of the number of elements.

If adding another element will exceed the capacity, then create a new static array with twice the capacity and copy the original elements into it.

The complexity of Static Array and Dynamic Array.

Operations Static Array Dynamic Array
Access O(1) O(1)
Search O(n) O(n)
Insertion N/A O(n)
Appending N/A O(1)
Deletion N/A O(n)
The access time of static and dynamic array is constant because the array is indexable.

The search time of static and dynamic array is linear because sometimes we have to traverse all the elements in the worst cases.

The other operations like inserting, appending, and deletion are not possible with a static array because a static array is fixed in size, it cannot grow larger or smaller.

However, inserting, appending and deletion is possible with a dynamic array. Insertion and deletion take linear time because in this process we have to shift elements from their position. Appending is the constant time because it adds an element at the end of the array. 

If you like this post and find it useful then you can show your support by donating a small amount from your heart. You can also show your support by following us on Facebook and Twitter. 

Post a Comment

Previous Post Next Post