This article is the first in a series of articles about data structures.
Arrays are one of the more basic data structures and very broadly-used. Arrays are stored in contiguous memory chunks which provides some benefits and drawbacks. In some languages like JavaScript however, arrays are objects and thus not of a fixed size or necessarily stored contiguously.
Indexing into an array is done in constant time, while iterating through an array is done in linear time.
One Dimensional Arrays
Advantages
- because the data is stored in contiguous memory, sequential access is fast as we’re able to take advantage of cache efficiency
- accessing a known index is done in constant time ($O(1)$)
Disadvantages
- because the data is stored in contiguous memory, arrays can not be resized and need to be declared with a size up front
- certain programming languages make it appear that an array is being resized, but usually a larger copy is made elsewhere in memory which comes at a cost
- insertions and deletions happens in $O(n)$
Usage Examples
- list of integers like a list of employees
- implementation of a stack
Multi Dimensional Arrays
Multi-dimension arrays are, in essence, arrays where the indexes contain arrays. This depth or dimension of this structure is limited by the amount of memory you have. In reality one rarely needs more than two dimensions.
Indexing into the array is done in constant time, while iterating through the array is done in linear time.
Example of a two-dimensional array:
Example of a three-dimensional array:
Advantages
- because the data is stored in contiguous memory, sequential access is fast as we’re able to take advantage of cache efficiency
- accessing a known index is done in constant time ($O(1)$)
Disadvantages
- because the data is stored in contiguous memory, arrays can not be resized and need to be declared with a size up front
- certain programming languages make it appear that an array is being resized, but usually a larger copy is made elsewhere in memory which comes at a cost
Usage Examples
- the board of a board game like chess
Code Examples
