Array data structure

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).

-1941-10513
100010041008101210161020
array of 6 integers.

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.

  1. Insert
  2. Delete
  3. 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.

-19-10513

Now let’s try to insert 41 in index 2. Need to move -10, 5, 13 to one position right.

-1941-10513

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 O(n) 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 O(n) 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 O(n) 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!.