An array is a container that stores and organizes items sequentially.
They are an ordered collection of elements and each value belongs to the same data type.
Indexing of the array start from 0 to n-1.
Accessing elements in arrays
During code execution, computers need to track variables (numbers, strings, arrays, etc.).The variables are stored in random access memory (RAM). RAM is sometimes called “working memory” or “memory.”
RAM is connected to a memory controller, and read and written by the memory controller. It has a direct connection to each shelf of RAM. Thus, we can access address 0 and then access address 1000 or any other address immediately.
We can think of an array as a RAM. Just like RAM, the elements of an array are numbered. We call that number the index of the array element.
And remember the direct connection to memory processor. This means looking up the contents of a given array index is O(1) time. This fast lookup capability is the most important property of arrays.
Insertion in Arrays
In order to insert something into an array, we have to make space by moving everything starting at the index we want to insert.
In the worst case we’re inserting into the 0th index in the array, so we have to move all the elements in the array. That will be O(n) time.
Deletion in Arrays
Since array elements are stored sequentially, when we remove an element, we have to fill in the gap by moving all the elements that were after the index from where the element was deleted.
In the worst case we’re deleting the 0th item in the array, so we have to move all the elements in the array. That will be O(n) time.
Array: Strengths and Weakness
Strengths
Fast lookups. Retrieving the element at a given index takes O(1) time, regardless of the length of the array.
Fast appends. Adding a new element at the end of the array takes O(1) time, if the array has space.
Weakness
Fixed size. We need to specify how many elements you’re going to store in your array ahead of time.
Costly inserts and deletes. we need to move elements to create space, which takes O(n) time.
Static vs Dynamic Array
Static Arrays are of fixed size, that means we need to specify the number of elements your array will hold ahead of time.
Dynamic arrays expand as we add more elements. Thus we don’t need to determine the size ahead of time.
Note – Dynamic arrays are also know as the array lists. In python language, dynamic array are implemented using lists.
Creating a Dynamic Array
We can create a dynamic array by allocating an array of fixed-size, typically larger than the number of elements that are going to be immediately added.
Let’s say our implementation uses 6 indices. Now we append 3 items to our dynamic array. At this point, our dynamic array has a size of 3,but actually has a capacity of 6.
Dynamic Array: Strengths and Weakness
Strengths
Fast lookups. Just like arrays, retrieving the element at a given index takes O(1) time.
Variable size. We can add as many items as we want, and the dynamic array will expand to hold them.
Weakness
Costly inserts and deletes. Just like arrays, we need to move elements to create space, which takes O(n) time.
