Data structure- Array Quick lookup for interview

The array is one of the most common primitive data type in programming languages.

An array is a collection of homogeneous data items stored in contiguous memory locations. That is one chunk of memory that can be either on the stack or the heap. The allocated memory is divided into equally spaced memory locations and each of these locations are indexed by contiguous integers.

Here is a classic example of an array of four elements. here the memory locations are indexed with Zero-based indexing method. However, one based indexing also supported in few languages.

What makes Arrays special?

There are few things that make the array a key data structure,

• Array provides constant access time

let's assume we have the following array,

sampleArray = [99, 10, 20, 45, 12, 13, 18, 19, 16, 3];

An array of 10 integer variables, with indices 0 through 9, maybe stored as 10 words at memory addresses 2000, 2004, 2008, … 2036, so that the element with index ihas the address 2000 + 4xi. This process takes one multiplication and one addition. Since these two operations take constant time.so we can say the access can be performed in constant time.

• Array facilitates random access

An array is called a random-access structure because the order that you access an element in it doesn’t matter. That is to say, I can access any random element in the structure and it will take the same amount of CPU time: the CPU multiplies the index by the block size as mentioned above, adds it to the starting location, and it has the address of the block of memory needed. so it does not matter whether we are accessing 0th element or 5th element of an array as long as they are stored in contiguous memory.

• Array is cache-friendly

In particular, arrays are contiguous memory blocks, so large chunks of them will be loaded into the cache upon first access of any of the element in the array. This makes it comparatively quick to access future elements of the array.

                    Address      Contents
                    ffff 0000    data[0]        
                    ffff 0040    data[1]       
                    ffff 0080    data[2]       
                    ffff 00c0    data[3]       
                    ffff 0100    data[4]

If we wanted to loop through this array, the first access ffff 0000 would require us to go to memory to retrieve (a very slow operation in CPU cycles). However, after the first access, the rest of the array would be in the cache, and subsequent accesses would be much quicker.

• Lesser memory overhead

An array requires memory space only for the values, the start address and its length. On the contrary, a linked list needs a pointer for every value which is inserted. It acquires memory for every address and also when extra data is inserted it also needs memory for the same.

• Time complexity

As this data is stored in a sequential manner it is efficient to track it by using just its index values. In these cases every time you need to traverse to a particular desired position and then access its value.

          Operation      Average case      Wrost case
          --------------------------------------------
            Read            O(1)               O(1)
          --------------------------------------------
            Insert          O(n)               O(n)
          --------------------------------------------
            Delete          O(n)               O(n)
          --------------------------------------------
            Search          O(n)               O(n)
          --------------------------------------------

Multi-dimensional array warrants a separate discussion of their own. we will see that in another article in detail.

Summary

In summary, an array consists of a contiguous area of memory.because if it were non-contiguous then we couldn’t just do this simple arithmetic to get where we’re going. We have to have equal-size elements again so our arithmetic works. And indexed by contiguous integers again so our arithmetic works. We have constant time access to any element, constant time to add or remove at the end and linear time to add and remove at any arbitrary location. let's see Linked list in the next article.