Arrays

Array are the simplest data structures, build into most programming languages and we use them to store list of items like list of numbers, string, objects and literally anything. These items get stored sequentially in memory.

In many languages arrays are static – which means – when we allocate them we must specify their size and this size cannot change latter on. So we need to know ahead of time – how many items we are going to store in an array.

Arrays have a property called

• Length – that is Size of Array
• indexOf() – Index of the current element.

Runtime Complexity for Operations in Array.

1. Looking up an array by index is superfast. Give an array an index and it will figure out when exactly in memory it should access the value. Run Time Complexity of this operation – O (1), because the calculation of memory address is very simple, it doesn’t involve any loops or complex logic. We need to store a list of items and access them by their index.
2. Insert into an array – In many languages arrays are static – which means – when we allocate them we must specify their size and this size cannot change latter on. So we need to know ahead of time – how many items we are going to store in an array. What if we don’t know (we still have to guess – if our guess is too large we will waste memory and it too low our array get filled too quickly and to add another item – we have to resize the array –which means we should allocate a larger array and copy all the items in the old array in to the new array. This operation can be costly – The Run time complexity of this operation is O(n) which means the cost of copying the items in to the new array increases linearly and is directly proportional to the size of the array.
3. Removing / Delete an item from array. – There are different scenarios.
   1. Deleting / Removing the last item – it’s easy – we can quickly look it up by its index and clear the memory location and we are done  –  Delete O(1)
   2. Thing of Worst Case Scenario – Removing item from beginning from Array – we have to shift all the items on the right one we delete the first item from beginning. The more items we have the more the shifting is going to cost, so in wort case scenario deletion is O(n)

If you want to grow shrink or delete – use linked List.

Happy Learning