An array is the most useful data structure because it forms a fundamental building block for all other data structures. Using arrays 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:
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 search time of static and dynamic arrays 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 we have to shift elements from their position in this process. Appending is the constant time because it adds an element at the end of the array.
No comments:
Post a Comment