Arrays
An array is a data structure representing a finite sequence of elements that can be accessed efficiently by their position, or index, in the sequence. Elements can be of any type (Int, String, Objects…). Arrays keep the ordering.
Direct Access: While the array is one of the most used data structures, we should use it when we need direct access to any element or iterating following an order.
Sub-array: You can also get a sub-array, Array Slice; it’s fast as a constant cost because they share the same memory with the whole array. If you want a new array, you need to create it, but it will have a linear cost.
Loop: You can easily iterate over an array.
Updating Array: Because elements in arrays are contiguous in memory, it permits direct access. Still, it has an impact on inserting or deleting.
Appending: Most of the time, appending or adding at the end has a constant cost (not depending on the size of the array). Whenever the array gets full, it needs to reserve more space. It doubles it and moves all existing elements, which has a linear cost (depending on the number of elements).
Inserting: Inserting, in the worst case, is into the first position, which needs to move all elements; even if we don’t reach its capacity, it has a linear cost. If you need to always insert at the beginning of the array, then you should consider another data structure (have a look at the “Linked List”).
As inserting, deleting/removing force shifts all elements after the given position, which has a linear cost.
Contains: To know if an element is present inside the array, you can use the contains method, which has a linear cost. If you need to check this often, consider another data structure (Set, Dictionary, or build your own).
Index: If you want to find the position of an element, you can use firstIndex or lastIndex, which have a linear cost.
Count: When using arrays, we often need to know the number of elements or even if it is empty, which has a constant cost.
Time complexity:
- Direct access: O(1),
- Append: O(1) (average, worst case o(n)),
- Insert: O(n),
- delete: O(n),
- firstIndex: O(n),
- contains: O(n),
- Iterate: O(n),
- isEmpty: O(1),
- count: O(1).
