As mentioned in its dictionary meaning, the array is “range of particular type of things”. Here in computer science array is a range of the same types of objects. Objects here represents any programming language objects i.e., char, short, int, float, double or Object…etc.
It stores in contiguous memory locations in the application memory. Let’s illustrate this with an example int array (size of an int in 32bit system is 4bytes).
-1 | 9 | 41 | -10 | 5 | 13 | |
1000 | 1004 | 1008 | 1012 | 1016 | 1020 |
Above array { -1, 9, 41, -10, 5, 13 } is stored starting at 1000th address location. So here starting address location represents the first element of the array. As arrays stored in continuous address locations, it is to represent them using index values ranges [0, 1, 2,… N-1]. Let’s see how to represent the arrays in C programming language.
arr[] = { -1, 9, 41, -10, 5, 13 }
So, here arr[0] represents
arr[0] = value in address 1000 = -1
arr[1] = value in address 1004 = 9
arr[2] = value in address 1008 = 41
...
So formula here is [latex display="true"]arr[n] = base + (n * sizeof(int))[/latex] // Value in address base + n*sizeof(int)
Array is Data Structure, for any data structure below few are the basic functionalities to support.
- Insert
- Delete
- Find
Insert
To insert a value in an array at any given position needs one position movement of all its right side values. Let’s take the below example.
-1 | 9 | -10 | 5 | 13 |
Now let’s try to insert 41 in index 2. Need to move -10, 5, 13 to one position right.
-1 | 9 | 41 | -10 | 5 | 13 |
41 inserted in index 2.
int insert(int arr[], int len, int index, int value)
{
for(int i=len-1; i>=0; i--)
{
// Put value at index then exit.
// No need to move elements lesser than index.
if(i == index)
{
arr[i+1] = arr[i];
arr[i] = value;
len++;
break;
}
else if(i>index)
{
// Move ith index in i+1 index.
arr[i+1] = arr[i];
}
}
return len;
}
The above insertion takes complexity.
Delete
Delete functionality is as similar as Insert in arrays. Here in deletion it shrinks array by one value. Remaining all right side elements moves left by one position. Let’s jump directly into the code for this.
int delete(int arr[], int len, int value)
{
int foundIndex = len;
for(int i=0; i<len; i++)
{
if(arr[i] == value)
{
foundIndex = i;
}
if(i>foundIndex)
{
// Move 1 position left to its position.
arr[i-1] = arr[i];
}
}
return len-1;
}
Deletion of an integer takes complexity.
Find
Here in arrays there are two to find any element. Those are found based on the index and based on value. It is easy to find a value with an index by using the above function mentioned in the representation of arrays.
To find a value in the array, Need to search for that element linearly as shown in the code below.
int find(int arr[], int len, int value)
{
// If not found it returns -1.
int found = -1;
for(int i=0; i<len; i++)
{
// Set the found index if value found in array.
if(arr[i] == value)
{
found = i;
}
}
return found;
}
Again for finding an element in array takes complexity.
Above is a basic explanation of arrays data structure with necessary options, please let us know if there are any questions by commenting below. Cheers!.