Understanding Array Data Structure

Hello to all the readers!

After knowing the importance of data structures, let us see what are the different kinds of data structures. Array is the most simplest and basic data structure.

It is simply a list of items stored continuously one by one in the computer memory. There is a condition in array that the items should be of same type. Like all items in an array can be numbers or all items can be strings and so on. The compiler will throw error if we try to mix the types.

Array items or elements are stored in continuous memory locations. We can see below how are the elements stored in the memory.

Each element is accessed by the index value that starts from 0 and not 1. Above is the array of 9 elements (0…8 = 9).

What Are Array Operations?

Let us now talk about different operations that can be performed on the array.

1. The item can be accessed at a particular index value
2. A new item can be inserted in the beginning, end or anywhere in the array
3. Any item can be deleted
4. Any item can be searched by traversing the array

What Is The Time Complexity Of Array?

Now we know the different operations that can be performed on the array. We shall now see what is the time complexity of each operation.

1. Accessing element at specified index – This takes O(1) time since in one instruction value can be fetched e.g. items[4]
2. Inserting element – This takes O(n) time since in order to insert the element, a new array has to be created with increased size
3. Deleting element – This again takes O(n) time since this will create a new shorter sized array
4. Searching element – This also takes O(n) time since it requires (n) unknown number of iterations over the elements of the array in order to search a particular value

What Is The Memory Size Of Array?

This is an interesting and very important question to know. Because we are focusing on making efficient algorithms with efficient data structures. The least memory one can use is the best as memory is a limited resource. A good programmer will definitely want to do this.

The memory size of an array depends upon the memory size consumed by the element data type. If it is an integer, then it will consume 4 bytes or 8 bytes or whatever and if it is a character, then it will consume 8 bytes or whatever and so on. Therefore,

Memory size of array = Total number of elements in array * size of each element

Another important point to note is that the size of the same data type can be different in different programming languages. So do read the manual of that language in order to know how much memory space it takes.

Why Array Index Starts From 0?

Basically in the programming language, items[i] actually means *(items + i). This means it references the memory address of the first element. And then as the value of index i increases, so the memory address of the element.

So, *(items + 0) = x5000, *(items + 1) = x5004 and so on…

If the index was indeed started from 1, then compiler would have never accessed the first array element at the address x5000.

What Is 2D Array?

A 2D array is a 2 dimensional array. Two dimensions means that it has rows and columns. It is like a table or matrix.

The same set of operations that were there on 1D array will be applied on 2D arrays. And the time complexity of these operations on 2D array is also same as that of 1D array mentioned above.