Do You Really Know Arrays?

Programmers take it lightly when dealing with arrays and linkedlists especially those who arent much familiar with the Data structures and focus only on the language specific concept about arrays and linkedlists.

So lets start with arrays first.

So As above images suggests arrays are contiguous area of memory ,so the memory allocation could be stack or heap based on the how you are working with it.

The speciality about arrays it helps us in constant-time access of an element.

Lets look at below image to find whats the exact way to figure out the memory address of each element inserted considering the first index to be 0.

So lets say we consider the initial address to be 1000 which is 0th index element memory address.

As per the formula the addresses would be 1000 + 8 * (1-0)

so element size i have taken as 8 which means 8 bits to single element and then i would be the first element in array and firs index would be zero.

So the memory address for 1st element would be 1008 this way it goes for other elements in the array.

Be careful the initial memory address for different compilers would be different.

So dont argue with your collegues if both of you get different memory address for same example on different machines.😄😂

Multidimentional Arrays

Now lets just into the multidimentional arrays.

So lets see the below image to understand whats going on with multidimensional arrays.

array_addr + elem_size × ((row − 1) × array_size + (col − 1))

So as the above formula shows how the above two dimentional arrays are allocated with the elements.

array address lets say 1000 , element size 8 bits then (row -1) so here row is 3.

6 here is the array size + (col -1) here column is 4.

so that way we find the element at row 3 and column 4. 

Below image shows the column major and row major.

Now Lets look at the time complexity for the operations on the array.

for adding an element at the start of index it becomes Big O(n)  operation reason being will need to shift all other elements to their current index +1 location which will be happeing to all the elements in the array.

Same case is with removing the first element from the array.

All the other elements would be needed to reassign with their new location which would be current index-1 location.

Now for adding or removing an element at the last wouldnt impact any other element in the array.

So the time complexity will just be Big O(1).

For adding or removing element in between the array it would still be required to shuffle remaining elements and that would take Big O(n) times to do that.

To Summarize all the above things we discussed.

So the best part about array is to add and remove elements in the end.

The worst part to add and remove elements in between or start of the array.

The retrieval of element is based on index so even that becomes a faster process in array.