A static array is a fixed length container containing n elements indexable from the range [0, n-1].
Indexable means that each slot/position in the array is referenced with a number.
In arrays, indexing always starts with 0 and as it is contiguous,
continues with currentIndex + 1 consecutively.
Applications of static arrays
Storing and accessing sequential data.
For temporarily storing objects.
Used as buffers by I/O routines.
Lookup tables and inverse lookup tables.
Used to return multiple values from a function.
In dynamic programming, arrays can be used to cache answers to subproblems.
Complexity Analysis
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)
Dynamic Array
Dynamic arrays have flexible and resizable container, that is to say that they can shrink and grow in size.
Implementation of dynamic array
Create a static array with an initial capacity.
Add elements to the underlying static array till its capacity limit is reached.
Then create an array twice the static array size and copy the contents of the original array to this array.
Applications of Dynamic Arrays
Flexible Storage: They are used when the number of elements is not known in advance or may change over time.
Stack and Queue Implementations: Dynamic arrays can serve as the underlying data structure for stack and queue implementations, where elements are added and removed frequently.
Array Lists: In many programming languages, dynamic arrays are implemented as array lists (e.g., ArrayList in Java, List in Python) which provide dynamic resizing and additional functionality.
Caching: Similar to static arrays, dynamic arrays can be used for caching where the size of the cache may vary.
Data Structures: Dynamic arrays are foundational for various advanced data structures like hash tables, heaps, and certain types of priority queues.