Arrays are one of the most important and most common data structures out there. Any respectable application, framework or library will probably be using arrays in some form. Also, when it comes to coding interviews, arrays are still the most frequently asked data structure. In this post, we will understand Array Data Structure. And also, we will look at how to use Arrays in C++.
So let’s begin from the beginning.
What is an Array?
As I already mentioned, Array is a data structure. But that does not seem quite intuitive. There are scores of data structures out there.
However, array is one of the most basic data structure. In fact, it forms the backbone of many other complex data structures like Heaps, Hash-maps and so on.
Without getting too academic, I will put out this simple description of Array Data Structure.
An array is a collection of n data elements of the same type.
I know this isn’t the most thorough definition out there. Some pretty heavy and amazing books written on the subject will have pages defining array. However, this is good enough for an initial understanding. And of course, if you have the time, definitely go for the books as well.
The important point in the above definition are the words ‘same type‘. Basically, what this means is that we can have an integer array, a float array or a character array. But we can’t have an int-float array. In other words, each and every element an array should be of the same data type.
Now, some programming languages do provide different abstractions that allow us to have mixed data types. For example, Python lists can have elements of different types and behave mostly like arrays. However, they are basically known as Lists.
But we won’t be getting into those right now.
Why Array?
After defining array, the next obvious question is why do we need an array? In other words, what are the applications of array?
Let’s consider an example here.
Imagine we have an organization. And our organization has 10 employees. And for some strangely convoluted business reason we have to store the employee numbers of all those 10 employees. Creepy, isn’t it?
How can we implement this?
Well, the first thing that might come to mind is that to declare 10 variables for storing 10 employee numbers in our program. Next, we can assign them the respective employee numbers.
And if more employees join our company, it will be super easy to just declare more variables.
If a thousand employees join our company, we just rinse and repeat.
Simple, isn’t it?
Oops, there seems to be a glitch in the matrix. Well, this will definitely be a horrible solution. And the point is that such a solution will be considered very rarely. This is because we know that arrays exist.
So, instead of declaring one variable per employee, we will declare an array.
Above illustration describes the array data structure for storing employee numbers. Currently, we have 10 employees. And the length of the array is 10. However, we can increase the length of the array if needed to accommodate more employee numbers. The main point is that all elements of this array store employee numbers only.
Declaring an Array
Moving on, the next important piece of the puzzle is about how to declare an array.
Different programming languages have different ways of declaring an array. For this post, we will be using C++ (everyone’s favorite to-be-hated language that should be learnt).
But really, C++ is amazing language for getting into data structures. And it is the most useful if we want to really get into stuff like Competitive Programming where data structures are used heavily. More on that later!
Basically, they are 3 different ways of declaring an array:
By Specifying Size
In this approach, we declare an array and also specify the size of the array. By size, it means the number of elements in the array.
We can do it as below in C++:
int array[5];Here, int is the data type of the elements that will go in this array. The word ‘array’ is actually the name of our array. This could be anything we want. Lastly, 5 within the [] is the size of the array. In other words, the number of elements it can contain.
Array Declaration using size can also be done as below:
int n = 5;
int array[n];Basically, we have made the size of the array as dynamic. It will be set to the value of the variable n. And n can depend on some user input or other logic in the program.
We use this approach when we have no idea about any of the elements that will go in the array except the overall size we require.
By Initializing Elements
The next approach for declaring an array is by initializing the elements at the time of declaration.
This can be done as follows:
int array[] = {1, 2, 3, 4, 5};Here, we have an integer array. And we have initialized it with the values 1, 2, 3, 4, 5. Basically, the size of the array is automatically set to 5 elements.
This approach is used when we know what all elements will be in our array.
By Size and Initialization
As the name suggests, this approach is a mix of both the previous options.
Below is an example:
int array[6] = {1, 2, 3, 4};Here, the declared size of the array is 6. But we initialize it with only 4 elements having values 1, 2, 3 & 4. However, 2 places are still present and we can fill them if required.
Needless to say, this approach is used when we know some elements of the array in advance while some are dependent on the program execution.
Size & Length of the Array
We have been using the term size in our discussion. However, it can be a bit misleading in C++. While we mean size as the number of elements in the array, C++ treats it as the size of the memory allocated to the array.
And definitely, what C++ says is the correct thing.
If we print the size of the array as below, we will be getting 20.
int array[5];
std::cout << sizeof(array);This is because in C++, each integer takes 4 bytes. Since, we have 5 elements in our array so 5 multiplied by 4 becomes 20. And that’s the size of the array. Note that sizeof() is an in-built C++ function.
A better term to denote the number of elements in the array is length. However, funny part is that C++ doesn’t care about the length of the array. Unlike most programming languages, we can’t directly access the length of the array in C++.
Instead, we have to calculate it using the below:
int length = sizeof(array)/4Basically, we are dividing the size of the array by the size of a single integer. So, dividing 20 by 4, we get 5 and that’s the length of the array.
OK. So that last bit was probably a bit academic and not concerned with the actual Array Data Structure topic. However, it could be important to have a distinction between Size and Length of the array (at least in C++).
In this post, I will keep our discussion till this point only. In the next post in this series, we will get into accessing array elements and the various array operations.
Let me know your views in the comments section below.
0 Comments