Skip to main content

What is Array

 An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together. This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array). The base value is index 0 and the difference between the two indexes is the offset.

For simplicity, we can think of an array as a fleet of stairs where on each step is placed a value (let’s say one of your friends). Here, you can identify the location of any of your friends by simply knowing the count of the step they are on. 
Remember: “Location of next index depends on the data type we use”. 

The above image can be looked at as a top-level view of a staircase where you are at the base of the staircase. Each element can be uniquely identified by its index in the array (in a similar way as you could identify your friends by the step on which they were on in the above example). 

Array’s size

In C language, array has a fixed size meaning once the size is given to it, it cannot be changed i.e. you can’t shrink it neither can you expand it. The reason was that 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 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.
  • 1 (one-based indexing): The first element of the array is indexed by the subscript of 1.
  • 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: 

  • Arrays allow random access to elements. This makes accessing elements by position faster.
  • Arrays have better cache locality that makes a pretty big difference in performance.
  • Arrays represent multiple data items of the same type using a single name.

Disadvantages of using arrays: 
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. Here Insertion(s) and deletion(s) are difficult as the elements are stored in consecutive memory locations and the shifting operation is costly too.
Now if take an example of implementation of data structure Stack using array there are some obvious flaw. 

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.

Following example illustrates, how array can be used while writing a code-

In the following example, we have given marks of a student in 5 different subjects. Aim is to calculate the average of all the marks of a student.

Popular posts from this blog

Optimal Substructure Property in Dynamic Programming

  As we discussed in   Set 1 , following are the two main properties of a problem that suggest that the given problem can be solved using Dynamic programming:  1) Overlapping Subproblems  2) Optimal Substructure  We have already discussed Overlapping Subproblem property in the  Set 1 . Let us discuss Optimal Substructure property here.  2) Optimal Substructure:  A given problems has Optimal Substructure Property if optimal solution of the given problem can be obtained by using optimal solutions of its subproblems.  For example, the Shortest Path problem has following optimal substructure property:  If a node x lies in the shortest path from a source node u to destination node v then the shortest path from u to v is combination of shortest path from u to x and shortest path from x to v. The standard All Pair Shortest Path algorithm like  Floyd–Warshall  and Single Source Shortest path algorithm for negative weight edges like  Bellman–Ford  are typical examples of Dynamic Programming.  O

Overlapping Subproblems Property in Dynamic Programming

  Dynamic Programming is an algorithmic paradigm that solves a given complex problem by breaking it into subproblems and stores the results of subproblems to avoid computing the same results again. Following are the two main properties of a problem that suggests that the given problem can be solved using Dynamic programming. In this post, we will discuss the first property (Overlapping Subproblems) in detail. The second property of Dynamic programming is discussed in the next post i.e.  Set 2 . 1)  Overlapping Subproblems  2)  Optimal Substructure 1) Overlapping Subproblems:   Like Divide and Conquer, Dynamic Programming combines solutions to sub-problems. Dynamic Programming is mainly used when solutions of the same subproblems are needed again and again. In dynamic programming, computed solutions to subproblems are stored in a table so that these don’t have to be recomputed. So Dynamic Programming is not useful when there are no common (overlapping) subproblems because there is no po

About Us

       A team of dedicated and experienced software engineers sharing their knowledge and experience on a regular basis.