Array – Data Structure

What is an array?

The textbook definition of an Array is a collection of data that are of same nature and are stored in a contiguous fashion. An array is a systematic arrangement of similar objects, usually in rows and columns.

What do these words mean anyway? Let’s start by defining what a data structure is. In computer science, a data structure is a data organization, management and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data. In terms of programming, a class in c++ programming language can be considered as a data structure, if you have no idea what I am talking about don’t worry, you will learn that in the future, most probably in my blog xD.

Basically, you store stuff in data structure and since an array is a data structure, you can store stuff in an array. In our definition of the array, the is another phrase about data of similar nature. This boils down to the fact who data is stored in the memory in your case RAM. And each type of data takes up a fixed amount of memory, for example: in most computers these days, an integer number takes 4 bytes of memory (or 32 bits) and a decimal point number takes exactly 8 bytes (or 64 bits). When two data is of similar nature, that means that they are of the same type hence take up the same amount of memory in the RAM.

Another thing about an array is that the data is stored in a contiguous fashion, this means in the memory or RAM, all the data will be stored one after the other. To understand this concept consider this diagram.

The image above is a representation of RAM and how an array is stored in the memory. Consider that the array starts at the memory location 1000 (bytes) and also assume that in this array, integer numbers are stored which means that each number would take 4 bytes in the memory. So the first number will be stored from 1000 to 1004 as you can see in the diagram, what being stored in contiguous manner means that in the array the next number will be stored from memory location 1004 to 1008 and the next one from 1008 to 1012 and so on. The last element in an array is always NULL which is a special character used by the computer that tells the CPU that this is the end of this data structure, you don’t have to look further.

In this blog, I’m not touching the machine level concepts of how data is actually stored in the memory. We will look at that part when we talk about bit manipulation and bit-wise operators. Make sure you follow this blog if you want to get an email when I publish that blog are any other blog.

Following is a C++ initialize an array:

void main(){
    int arr[10];
    // this will create space
    // for an array of length 10 in the memory.
}

Properties of an Array

From the definition of an array we can deduce the following properties of an array:

1. The data stored in an Array is of the same type, ie, it takes the same amount of memory.
2. All the elements in an array are stored one after the other, ie, in a contiguous manner.
3. All elements can be accessed if we know only the location of the first element of that array.
4. The name of an array is actually a pointer to the location of the first element in the array.

Operations on an array

Now that I have bored you with the theory of an array, let’s talk about different things you can do on an array.

Look ups

Look up is a fancy way of saying to access an element in an array or any other data structure. In an array, you can access any element directly if you know the address of the first element of that array. Consider this C++ code.

void main(){
    int arr[] = [1,2,3,4,5];
    cout << arr[3];
    // This will print the 4th element
    // of the array because array index
    // starts from 0 and ends at n-1
}

Traversal

This is looping through each element in the array one by one. This can be done by incrementing the index by one for accessing the next element. Consider this code.

void main(){
    int arr[] = [1,2,3,4,5];
    int i = 0;
    int size = 5;
    while(i < size){
        cout << arr[i];
        i++;
    }
}

Searching

There are two most common ways or algorithms to search and element in an array.

Linear Search

This algorithm postulates to search an element by going through each element in that array until the required element is found. Consider this C++ code.

int linearSearch(int arr[], int item){
    int i = 0;
    while (arr[i] != '/0'){
        if (arr[i] == item){
            return i;
        }
    }
    return -1;   
}

The condition in the while loop arr[i] != ‘/0’ refers to the fact that the last element of each array is a NULL, which when converted to ASCII standards becomes 0.

Binary Search

Unlike linear search, Binary Search works by dividing the array in half at every iteration. Consider this code.

int binarySearch(int arr[], int l, int h, int item){
    while(l<h){
        int m = (h+l)/2;
        if (arr[m] == item){
            return m;
        } else if (arr[m] < item){
            h = m-1;
        } else {
            l = m+1;
        }
    return -1;
}

In the above code, you see there are two more parameters than linear search. int l and int h, l is for the lowest index of the array and h is for the highest index. The binary search has the capability of searching an element in an array of 1 Million in just 20 steps or mathematically log2(size), unlike linear search which would have taken 1 Million steps (worst case).

That is all you need to know about an Array. There are many data structures that are based on array, we will be talking about that in the future posts.