Arrays
chapter 1
What are arrays ?
Arrays are simple and widely used data structure in computer programming. Just forget about the computer programming they are most widely used in our day to day life too.
What I thought Arrays are specific to computer science and programming , Where do we use arrays in our day to day life tell me?
Have you ever visited a Library ? If yes then you may had noticed that books are there in the self like this ?
Look how the books have been arranged. They are arranged in linear manner one next to other right? This sort of arrangement called Array. What else have you observed ? Each self containing books representing an array of books. One more thing , you can easily take out any of the book which you want to read there is no need to displace the other books right?
Like the array of the books in the world of programming too we can use arrays to store or arrange the data. So in Computer programming the arrays are linear arrangement of similar types of data.
Why it needs to be similar type only?
Look arrays are there from the beginning of the computer science and they have been evolved to different forms but we consider them to different type of data structure. So primarily Arrays hold the same type of data. There is also a strong reason to be of similar type which you will get to understand as you read the article further. Just consider the below example array A holds Integer type data while B is holding the Character type data.
That’s I understood , but how to exactly computer store it ?
As you know computer stores data and programs in memory , arrays are no exception and they are part of your program and data and they too get placed in the memory of computer know ideally elements of the all the arrays should be placed in the memory in contiguous location.
What Do you mean by contiguous location ?
Well computers memory can be visualized as grid like this :
I have mentioned the address of the few of the initial memory cells so that you can have an idea of how each cell has an address and each cell can be accessed using this address by the computers memory management unit (what is this ? well you should go and read about the computer organization and architecture to know more ) what i want to say that data elements of an array are always stored in contiguous manner which means if our computer is going to place the array A in the memory then if the first elements it store at the address let say 0024 then the next element should be at 0025 and the third should be 0025 and all the other element should be stored in the same manner.
How to use arrays in the computer programming?
Almost each and every computer programming language has arrays as data structure , They may be differ from the underlying implementation (that means how the are going to instruct the computer to store it )
What that means?
Well in “C ” language the arrays are stored in memory get a contiguous allocation but “JavaScript” arrays are implemented like a hashmap and hence they are not stored in contiguous manner But this differentiation does not pose any major difference in the functionality to the programmer.
Declaration of the Arrays depends on the language you are using ?
in C it is declared as int marks_of_student[60]; here name or reference of array is marks_of_student which going to hold int type of data. And 60 is the size (number of the elements it have) of the array.
Ideally the size should be mentioned when you are Declaring the array but this too depends on the programming language you are using.
You can google for “how to declare arrays in different languages ” :) to know about the declaration syntax for arrays.
How to access the array elements ?
Array element are accessed using indexes. Indexes are nothing just it is the position of the element relative to the first element. Almost in all the languages the index start with 0.
So first element has index = 0 , second has 1 , third 2 and so on …..
To access the value of element index “ i ” just write like this :
array_name[i]
lets take an example of it
int marks_of_students[10];
// this array is going to hold marks_of_the 10 students// what if want to access of the marks of the 5 the element ?
// well the index for the 5th element is 4 hence to access to it you // have to write like this
printf("marks of the 5th student %d ",marks_of_students[4]);// marks_of_students[4] gives you the value of the 5th element
again the access method based on index may vary with programming language but most of the language support the [] notation access.
How do i can insert,delete or modify elements in Array?
Once you have the index you can access the element using index and can do following operations :
Insert : yes you can insert a value to a particular place using index right so if you want to assign value “ x ” to index i then just write array[i] = x this statement will simply override the existing value at i with x
Delete : No you cant delete You can replace the arrays element value but deletion is not possible “ When I say Delete it means you want to remove the element from the array and also array should release that memory cell ” .
Modify: Same as insertion in fact insert is in itself a modification operation
Note : Many programming languages come up with some addition functions and operation that can a array have . This makes the programmers work more easy. What are those features and functions we will discuss as we progress in the course.
Searching in an array ?
if you want to search something in an array then you have to traverse the whole array ( which means going and visiting each cell in the memory and checking if it has the matching value or not ).
Is Searching in array is easy or difficult ?
Well searching in an array depends on how many number of elements array have. Just look at the below code :
int arr = [10,12,1,34,5,6,8,10]
// total number of elements 8
// i want to search if 5 exist in the array or not
// for that i have to go and check the each element in the array
// I am going to use the for loop for this
for(int i= 0 ;i<8;++i)
{
if(arr[i]==5){ print("Number 5 exist in the array. I am happy now :) ");
}}
Suppose if I have an array containing ‘n’ number of elements , what will be the average number of cells i have to traverse to find an element say ‘ x ’ in the array?
Nice Question! let all elements have equal chances to get any place in the array , what i mean is any element can occupy any of the position in the array.
Our arrays length is N which means we have N positions right?
if element is at first position then number of cells you need to traverse is : 1
if element is at 2 — — — — — — — — — — — → 2
if element is at 3 — — — — — — — — — — — → 3
— — —
— — —
if element is at position n — — — — — — — -> n
Note that even if element is not in the array then you will traverse the whole array that mean n cells you have to visit . But why i am not considering it in my calculation ? See each and every traversal give you two out come whether element is present or not right so the last line which is “if element is at position n ” will tell you whether element is present or not so no need to traverse the array once again to check if element exist or not in the array.
Now average number of cell you need to traverse is = (1+2+3+4+…………..+n)/n
= [n(n+1)/2]/n
= (n+1)/2
hence the average number of cells needed to be traversed is (n+1)/2
This is all for this chapter. We will explore more about types of the arrays we can have in the next chapter of this series.
