DATA STRUCTURES AND ALGORITHMS : ARRAYS -->

DATA STRUCTURES AND ALGORITHMS :

ARRAY:

              An Array is a collection of data items of same data type which are stored at contiguous memory location. This memory allocation makes it easier to calculate the position and value of each element in an array simply by adding an index to the base address value of an array. Basically, index of an array starts from 0 and the difference between the two indexes is depends upon the size of data type holding by an array. Here, in array memory is allocated statically or in other words we can say that arrays are having fixed size.

INDEXING IN AN ARRAY:  We are having three ways for indexing of an array which are described below

1.   0-based indexing: - In this the first index of an array is indexed as 0.

2.   1-based indexing: - In this the first index of an array is indexed as 1.

3.   N-based indexing: - Here, base index of an array can be chosen freely. Generally, programming languages are allowing this N-based indexing. In this indexing negative indexes are also allowed to index.

INITIALIZATION OF AN ARRAY: Arrays can be initialized in so many ways such that …..

1.   PASSING NO VALUE: - In this way you have to mentioned the size of an array without passing specific values to the initializer.

SYNTAX à int a[4] = { };

2.   BY PASSING VALUES: - In this you are allowed to give the size to an array on passing specific values.

SYNTAX à int a[5] = {1,2,3,4,5};

3.   BY PASSING VALUES WITHOUT DECLARING THE SIZE OF AN ARRAY: - This describes that you are allowed to pass specific values to the initializer without defining the size of an array. Compiler will automatically interpret the size of an initialized array.

SYNTAX à int a[ ] = {1,2,3,4,5};

4.   UNIVERSAL INITIALIZER: - This was first adopted by C++ .

SYNTAX à int a[ ] {1,2,3,4,5};

OPERATIONS ON AN ARRAY: - Indexing in an array makes it easier and faster to access any element of an array. Hence, operations like searching, insertion, accessing becomes so efficient only because of indexing of an array.

1.   INSERTION IN AN ARRAY: You are allowed to insert a value at a particular index position by using an assignment operator. For insertion you need to define the index and its value only.

SYNTAX à a[2] = 20;

TIME COMPLEXITY:

1.   To insert a single element – O(1).

2.   To insert multiple elements according to the size of an array – O(N). Where N is the size of an array

#include <iostream>

using namespace std;

int main()

{

  // initialize an integer array with three elements.

  int arr[3] = {};

  //First element is 1

  arr[0] = 1;

  //Second element is 2

  arr[1] = 2;

  //Third element is 3

  arr[2] = 3;

  // print the elements of an array using

  // a for loop

  for (int i = 0; i < 3; i++) {

    cout << arr[i] << " ";

  }

  return 0;

}

2.   ACCESS ELEMENTS IN AN ARRAY: You can access any element of an array. Accessing become important to perform operations on an array.

SYNTAX à a[2];

TIME COMPLEXITY: Time complexity to access any element from an array is O(1).

#include <iostream>

using namespace std;

int main()

{

  int arr[] = { 1, 2, 3, 4 };

  // accessing element at index 2.

  cout << arr[2] << endl;

  return 0;

}

3.   SEARCHING IN AN ARRAY: If you want to search for a particular value in an array . You need to access all the elements of an array and then, make a search for a particular value of an array. We are having some searching techniques in an array i.e. Linear Search and Binary Search.

TIME COMPLEXITY: Time complexity to search any element in an array is O(N). Where N is the size of an array.

#include <iostream>

using namespace std;

int main()

{

  int arr[10];

  int check = 3;

  arr[0] = 1;

  arr[1] = 2;

  arr[2] = 3;

  arr[3] = 4;

  for (int i = 0; i < 4; i++)

    if (i == check)

      cout <<check<< " existing element of an array and it is present at index : "<<i << endl;

  return 0;

}

TYPES OF ARRAY :

1.   ONE – DIMENSIONAL ARRAY  (1-D Array):

#include <iostream>

using namespace std;

int main()

{

 int num [5] ;

 cout<<"Enter array elements : \n";

 for(int i = 0; i < 5 ; i++)

 {

  cin >> num[i] ;

 }

}

2.   MULTI-DIMENSIONAL ARRAY:

//Program to display all elements of 2D

// array.

#include <iostream>

using namespace std;

int main()

{

  int i, j;

  int matrix[3][2] = { { 4, 5 }, { 34, 67 }, { 8, 9 } };

  // use of nested for loop

  // access rows of the array.

  for (i = 0; i < 3; i++) {

    // access columns of the array.

    for (j = 0; j < 2; j++) {

      cout << "matrix[" << i << "][" << j

        << "]=" << matrix[i][j] << endl;

    }

  }

  return 0;

}

TYPES OF OPERATION IN AN ARRAY :

1.   Traversal

2.   Insertion

3.   Deletion

4.   Searching

5.   Sorting

ADVANTAGES OF ARRAY :

1.   Arrays allow faster accessing of elements.

2.   Arrays are capable to have best cache memory to ensure effective performance.

3.   Arrays allows random accessing of elements.

4.   Arrays can have multiple data items using a single variable.

DISADVANTAGES OF ARRAY:

1.   You are not allowed to change the size of an array once you declared. It is because of static memory allocation.

2.   Shifting of elements is so costly to perform certain operations on an array.

NOTE – An array of character is string. Where, an array of integer or float is simply an array.

APPLICATIONS OF AN ARRAY :

1.   Arrays are useful when we already know the size of an array.

2.   Arrays can efficiently solve all the problems related to matrix.

3.   Data inside databases are also implemented by arrays.

4.   Arrays are capable to implement other data structures like stack, queue, heap, etc.

5.   Arrays are helpful for sorting algorithms.