Data Structure and Algorithms- ARRAYS (Quick Revision Series PART-2)

In this article, we are gonna learn all those important and interesting topics of the arrays which are very crucial if you are preparing for Data Structure and Algorithms.

So are you motivated and excited to learn something new, today??

Well I am too 💪🔥

So First thing First.

An array is a collection of items of the same data type stored at contiguous memory locations. This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array).

Generally, arrays are declared as:

dataType arrayName[arraySize];

An array is distinguished from a normal variable 
by brackets [ a ].

AAh! don't waste my time tell me something new, all this I already know.

LoOk DoWn 🙄

Advantages of using arrays:

• Arrays allow random access to elements. This makes accessing elements by their position faster.
• Arrays have better cache locality that can make a pretty big difference in performance.

Wait! wait! What's this cache locality??

Ans- why don't you find it your own? 😬

Basic Operations 🤔

Following are the basic operations supported by an array.

• Traverse: Print all the array elements one by one.
• Insertion: Adds an element at the given index.
• Deletion: Deletes an element at the given index.
• Search: Searches an element using the given index or by the value.
• Update: Updates an element at the given index.

So, let's discuss them one by one.

1. Traverse Operation 🐢

#include<bits/stdc++.h>
using namespace std;
int main ()
{
    int arr[5] = {1, 2, 3, 4, 5};
    for (auto &i : arr)
    {
        cout << i << " ";
    }
    return 0;
}

output: 1 2 3 4 5

Time complexity: O(n), in this approach, "n" is the size of an array.

Wait! what type of loop is this, what is this auto and all? 😦

hehehe😎

Let's learn something new!

First of all, this is a modern way of using for loop in C++. After C++11, two new major updates were Range Based Loop and Auto keyword. They are introduced in C++11 to reduce the syntax.

But they both have their own advantage and disadvantage based on which type of application you are implementing with them.

Learn more about them through yourself. Check this article.

2. Insertion Operation 📩

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int arr[5] = {1, 2, 3, 5};
    int element_to_insert = 6;
    int position_to_insert = 5;
    int index = position_to_insert - 1;
    // 0 based indexing in Array

    for (int i = index; i < 5; i++)
    {
        arr[i + 1] = arr[i];
    }
    arr[index] = element_to_insert;

    for (int i = 0; i < 5; i++)
    {
        cout << arr[i] << " ";
    }
}

output: 1 2 3 5 6

Time complexity: O(n), in this approach, "n" is the size of an array.

3. Deletion Operation 🔨

int main()
{
    int arr[5] = {1, 2, 3, 4, 5};
    int element_to_delete = 4;
    for (int i = 0 ; i < 5; i++)
    {
        if (arr[i] == 4)
        {
            for (int j = i; j < 5; j++)
            {
                arr[i] = arr[i + 1];
            }
        }
        else continue;
    }
    for (int i = 0; i < (5 - 1) ; i++)
    {
        cout << arr[i] << " ";
    }
}

output: 1 2 3 5

Time complexity: Worst-case, O(n^2), in this approach, "n" is the size of an array.

4. Search Operation 🔍

int main()
{
    int arr[5] = {1, 2, 3, 4, 5};
    int element_to_search = 3;
    int flag = 0, index;
    for (int i = 0; i < 5; i++)
    {
        if (arr[i] == element_to_search)
        {
            flag = 1;
            index = i;
        }
        else continue;
    }
    if (flag == 1)
    {
        cout << "Element Found at position " << index + 1;
    }
    else
    {
        cout << "Element not Found";
    }
}

output: Element Found at position 3.

Time complexity: O(n), in this approach, "n" is the size of an array.

Time Complexity of this search operation will be O(N) in the worst case as we are checking every element of the array from 1st to last, so the number of operations is N.

5. Update Operation

int main()
{
    int arr[5] = {1, 2, 3, 4, 20};
    int element_to_update = 20;
    int updated_value = 5;
    int index;

    for (int i = 0; i < 5; i++)
    {
        if (arr[i] == element_to_update)
        {
            index = i;
            break;
        }
    }
    arr[index] = updated_value;
    for (int i = 0; i < 5; i++)
    {
        cout << arr[i] << " ";
    }
}

output: 1 2 3 4 5

Time complexity: O(n), in this approach, "n" is the size of an array.

Yey! you have just seen all the Basic Operations that you can do on Arrays and using these operations only you can do more complex operations on arrays. 🥳

So don't forget to practice more questions.

Also, comment down your suggestions or any other better way of doing these operations on Arrays. 😇

Thank you, Cia 🤓