Hello friends, In this post, I will discuss about Array. In the journey of learning Data Structures and Algorithms, this is the most basic concept.  

An array is the most basic data structure. It is a collection of similar items stored at contiguous memory locations. It means, with the help of array, we store multiple elements of the same data type. This makes it easier to calculate the position of each element by simply adding an offset to a base value. Here, the base value means the memory location of the first element of the array. The base value is index 0 (in case of 0-based indexing) and the difference between the two indexes is the offset.


Array’s size

    In most of the languages, an array has a fixed size, which means, once the size is given to it, it cannot be changed i.e. you can neither shrink it nor expand it. The reason is, for expanding, if we change the size we can’t be sure ( it’s not possible every time) that we get the next memory location to us as free. The shrinking will not work because the array, when declared, gets memory statically allocated, and thus compiler is the only one who can destroy it.


Types of indexing in an array: 

  • 0 (zero-based indexing): The first element of the array is indexed by a subscript of 0. Some of the languages which support 0-based indexing are Java, C, Python, etc.
  • 1 (one-based indexing): The first element of the array is indexed by the subscript of 1. Some of the languages which support 0-based indexing are Fortran, Julia, APL, etc.
  • n (n-based indexing): The base index of an array can be freely chosen. Usually, programming languages allowing n-based indexing also allow negative index values, and other scalar data types like enumerations, or characters may be used as an array index.

Advantages of using arrays: 

1. Arrays allow random access to elements. This makes accessing elements by position faster.

2. Arrays have better cache locality that makes a pretty big difference in performance*. 3. Arrays represent multiple data items of the same type using a single name.


Disadvantages of using arrays: 

1. You can’t change the size i.e. once you have declared the array you can’t change its size because of static memory allocation. 

2. Insertion(s) and deletion(s) are difficult as the elements are stored in consecutive memory locations and the shifting operation is costly too.

Why we need Array: 

    In programming, most of the cases need to store a large amount of data of similar type. To store such a huge amount of data, we need to define numerous variables. It would be very tough to memorize all variable names while writing the programs. Instead, it is better to define an array and store all the elements into it.

* When we access a particular location in the memory, the processor generally caches the memory surrounding to that only. As in the array, all the elements are stores contiguously; so, after the first access, most of the elements come in the range of cache. But, if we compare it with other linear data structure like linked list, where elements are stored randomly, very few or may be no other element come in the range of cache region after the first access to memory.