Array Basics

The array data structure stores multiple elements of data of the same type. The data is stored on contiguous memory locations. The collection of data can be accessed via the name of the array and the position/index at which the data element is stored. We can create arrays of integers, strings or float values. But, an array of integers can just store integers, it cannot store strings or floats. Similarly an array of Strings cannot store integers.

Use cases for Arrays

Store and access and manipulate large data sets efficiently (example: lists of customer accounts, invoices etc.).

Arrays can be used to store multi-dimensional data like matrices.

Arrays can allow efficient implementation of search and sorting algorithms.

Arrays are used as a base data structure for other more complex data structures like stacks, queues etc.

Arrays may be used in implementation of data buffers, caches etc.

Arrays are also used for statistical analysis and image processing.

Advantages of Arrays

Fast access to array elements using index.

Arrays store values of one type only; thus avoiding multiple data type complexities.

Data elements are grouped together and easily accessible via array name and data element index.

Disadvantages of Arrays

Inserting and deleting items can be expensive as lot of data in array may need to be shifted.

Array size is allocated at initialization and cannot be incremented or decremented.

If allocated array size is not fully utilized (that is only few index are allocated, rest are unused) , it can lead to wastage of memory.

Time Complexity of array operations:

Following table shows time complexity metrics for an array with n elements

Operation	Complexity
Accessing element when index is known	O(1)
Search element when index is unknown for a sorted array using binary search	O(log n)
Search element via linear traversal when index is unknown for unsorted array	O(n)
Insertion or deletion at last index (no shifting of other elements is required)	O(1)
Insertion or deletion at specific instance (shifting of other elements will be required)	O(n)