## Without Research An array is a linear data structure where the position of each element is known, and it is the index of element in the linear data structure. - Retrieving - O(1) time complexity if the index is known - O(n) if the index is not known if doing a linear search (comparing each value) and if it is not sorted - If it is sorted, then other searching implementations can be used, such as [[Binary Search]] - Storage - Storing is O(1) if the index is available - If the index is not available, then O(n) because the storing algorithm would need to traverse the array ## With Research - An array is a data structure that can store multiple variables as a single variable - They can have a fixed *size* or variable *size* - *Size* refers to the capacity of the array - Certain languages (lower-level languages like C) create arrays of fixed size - These lower-level languages also require that the all of the stored elements have the same data type (float, int, double, string, boolean, etc) - Other languages create arrays of variable size - Arrays can store arrays, thus creating multi-dimensional arrays - Insertion - At the beginning requires all elements to be shifted to the right by 1, and for the array to be resized - In the middle requires only the elements after the index to be shifted to the right by 1 and for the array to be resized if needed - At the end requires only array to be resized if needed - Deletion - At the beginning requires all elements to be shifted to the left by 1 - In the middle requires only the the elements after the index to be shifted to the left by 1 - At the end does not require any other modifications - Search - Forward linear search: works on all types of arrays, start from 0 and increment, checking elements - Reverse linear search: works on all types of arrays, start at the end and decrement the index, checking elements - Binary search: only works on sorted arrays, start in the middle index and compare; if it matches, return; else if middle element is greater than, find the mid-point between the beginning and the middle point and compare; else find the mid-point between the middle-point and the end and compare