An introduction to Array

In this blog, I will be discussing about one of the oldest and widely used data structure called array and will be answering the following questions –

1. What is an array ?
2. What are the advantages and disadvantages?
3. Dynamic arrays
4. Applications / When should we use it ?  
5. Various operations associated with array DS

So let’s start

What is an array ?

An array is a collection of the same type of items stored at contiguous memory locations. It is also known as linear data structure. So, there are two important keywords in this definition – same type and contiguous.

Let’s say we have an array of integers containing 5 elements {10, 20, 30, 40, 50} all integer values.

Same type means – all the items present in an array should belong to one data type, for example -they can be either integers or float values, strings or chars and each of them is identified by an index value starting from zero.

array memory allocation

Now suppose the first value stored in memory at an address 2000 and each integer element takes up 4 bytes memory, so we can calculate the position of next value of an array with the help of the formula (2000 + ( i x 4 )), which is exactly what contiguous means, all elements in an array are present together in a sequence.

Advantages and Disadvantages of using an array

Advantages

  1. Arrays are particularly useful when we are dealing with a lot of variables of the same type. For example, let’s say I need to store the marks in a math subject of 100 students. To solve this particular problem, either I have to create the 100 variables of int type or create an array of int type with the size 100.
  2. Arrays are cache friendly – As arrays are contiguous memory blocks, so large chunks of them will be loaded into the cache upon first access. This makes it comparatively quick to access future elements of the array.
  3. As arrays are stored in contiguous memory locations, we need to predefined the size of an array. Hence there is no chance of extra memory being allocated in case of arrays. This avoids memory overflow or shortage of memory in arrays.
  4. Arrays allow random access of elements in O(1) time by using the index number. Remember we discussed that values in an array are marked by an index number which starts from zero.  

Disadvantages

  1. The number of elements to be stored in an array should be known in advance.
  2. An array is of fixed size (Known as static array). Once declared, the size of the array cannot be modified. The memory which is allocated to it cannot be increased or decreased.
  3. Insertion and deletion are quite difficult in an array as the elements are stored in consecutive memory locations and the shifting operation is costly.
  4. Allocating more memory than the requirement leads to wastage of memory space and less allocation of memory also leads to a problem.

Dynamic arrays

Static arrays have a size that is fixed when they are created and do not allow elements to be inserted or removed. However, by allocating a new array and copying the contents of the old array to it, it is possible to effectively implement a dynamic version of an array. In Java dynamic arrays can be created using arrayLists, in which we don’t need to declare the size of an array initially.

Applications

  1. Arrays can be used for sorting data elements. Different sorting techniques like Bubble sort, Insertion sort, Selection sort use arrays to store and sort elements easily.
  2. Arrays can be used for performing matrix operations. Many databases, small and large, consist of one-dimensional and two-dimensional arrays whose elements are records.
  3. Arrays can be used for CPU scheduling.
  4. Lastly, arrays are also used to implement other data structures like Strings, Stacks, Queues, Heaps, Hash tables etc.

Operations

Now there are various operations associated with array DS.

  • Insertion (beginning (O(n)), middle (O(n)) , end (O(1)) ), if memory is available or using a dynamic array
  • Deletion  (beginning (O(n)) , middle (O(n)) , end (O(1)) )
  • Searching (usually O(n), but binary search can be used if array is sorted and bring down the complexity to O(log n))
  • Read O(1), if index position is given
  • Traverse
  • Update (O(n))

Time for some basic problem solving


So, that’s all. I hope you enjoyed reading this blog as much as I enjoyed while writing it. In case of any query please leave your comment below or you can message us also.

Thank you.

1 Response

Leave a Reply

%d bloggers like this: