Data structure & Algorithms

Array

In Computer science an Array is a data structure. It is an container which consist the list of element of same type.

1: What is an Array?

Array is an contiguous memory location of element of same data type. Now next question is - what is meaning of "contiguous memory location". Contiguous memory location means - A memory blocks with consecutive memory location. Below image describes it more clearly.

In above image you can identify the memory blocks start from 100 & end to 106. Index of array strat from 0 that means if you allocate array of size 100 it's index will be from 0 to 99.


2: How to declare an define an Array

Let us learn this with example : i.e.
a: Define an array of integer of size 5

int arr[5];
							
b: Define an array of character of size 10
char arr[10];
							
c: Define an array of structure of size 10

typedef struct _myStruct
{
char name[10];
char address[100];
}MyStruct;

MyStruct structArray[10];
d: Dynamic allocation of array of size 10 of type MyStruct

#include <stdio.h>
#include <malloc.h>
typedef struct _myStruct
{
char name[10];
char address[100];
}MyStruct;

MyStruct *structArray = NULL;
structArray = (MyStruct *) malloc(sizeof(MyStruct)*10);


3: Insert an element at beginning of an Array

Insertion of an element is basic property of an array. This section describes how to insert an element at beginning of an array and code to insert_at_beginning of array
Problem statement:
- define an integer type array of size 100.
- Insert an element at beginning of an array.
A. Solution Steps:
- check if array is full return false i.e.


if(total_inserted_element >=100)
        return false;
							   
- Shift all array element at right side by position 1 .

total_inserted_element++;
      for(int i =total_inserted_element;i>0;i--)
      {
         array[i] = array[i-1];
      }
							   
- Insert at 0th index of array

array[0] = input;
							  
							  
B. Complete Code is below

#include <stdio.h>
#include <malloc.h>

#define MAX_ELEMENT 100
int array[MAX_ELEMENT]; //define array of size 100 of type integer
int total_inserted_element = 0;

//this function will initialize the array total_inserted_element variable.
void init()
{
  total_inserted_element = 0;
}

/*
  this function will insert at beginning
  return true - meaning successfully inserted
  return false - meaning unable to insert
*/
bool insert_at_beginning (int input)
{
   if(total_inserted_element >=100)
        return false;
   else
   {
      total_inserted_element++;
      for(int i =total_inserted_element;i>0;i--)
      {
         array[i] = array[i-1];
      }
      array[0] = input;
   }
   return true;
}

//print the array
void printArray()
{
  for(int i=0;i< total_inserted_element;i++)
    printf(" %d ",array[i]);
}

int main()
{
    int input = 0;
    while(input !=-1) //insert element until user enter -1
    {
        printf("Please enter number : ");
        scanf("%d",&input);
        if(input != -1)
            insert_at_beginning(input); //calling function to insert the element at beginning
    }
   //print the array
    printArray();
    return 0;
}
							
							



4: Insert an element as a last of an Array

This insertion section describes how to insert an element as a last element of an array.
Problem statement:
- define an integer type array of size 100.
- Insert an element at end of an array.
A. Solution steps:
- check if array is full, return false.
- insert element at last index of array
- increase Index
B. Code is below


#include <stdio.h>
#include <malloc.h>

#define MAX_ELEMENT 100
int array[MAX_ELEMENT]; //define array of size 100 of type integer
int total_inserted_element = 0;

//this function will initialize the array total_inserted_element variable.
void init()
{
  total_inserted_element = 0;
}

/*
  this function will insert at last
  return true - meaning successfully inserted
  return false - meaning unable to insert
*/
bool insert_at_last(int input)
{
   if(total_inserted_element >=100)
        return false;
   else
   {
     array[total_inserted_element] = input;
     total_inserted_element++;
   }
   return true;
}
//print the array
void printArray()
{
  for(int i=0;i< total_inserted_element;i++)
    printf(" %d ",array[i]);
}

int main()
{
    int input = 0;
    while(input !=-1) //insert element until user enter -1
    {
        printf("Please enter number : ");
        scanf("%d",&input);
        if(input != -1)
            insert_at_last(input); //calling insert_at_last
    }
    printArray();
    return 0;
}
							
							


5: Insert an element in an array before an element

This section explains & provide code to how to insert an element in an array before an existing element in an array.
Problem statement:
- define an integer type array of size 100.
- Insert an element at before an given element present in an array.
- if element if not present insert as last element of an array.
A. Solution Steps
- search the element in array.
- if element found shift all element right side to array
- insert the element after shift
- if element not found insert as last element of an array
B. See below the complete Code


#include <stdio.h>
#include <malloc.h>

int array[MAX_ELEMENT]; //define array of size 100 of type integer
int total_inserted_element;

//this function will initialize the array total_inserted_element variable.
void init()
{
  total_inserted_element = 0;
}
//print the array
void printArray()
{
  for(int i=0;i< total_inserted_element;i++)
    printf(" %d ",array[i]);
}
/*
  this function will search the given number i.e. insert_before_this_element
  After finding the number it will shift all number at right side.
  insert the given number
  return true - meaning successfully inserted
  return false - meaning unable to insert
*/

bool insert_element_before_an_element(int input, int insert_before_this_element)
{
   if(total_inserted_element >=99)
        return false;
   else
   {
       int index = -1;
       for(int i=0;iindex;i--)
            array[i] = array[i-1];
          array[index] = input;
       }
       else
       {
          array[total_inserted_element] = input;
          total_inserted_element++;
       }
   }
   return true;
}

int main()
{
    int input = 0;
    int insert_before_this_element;
    while(input !=-1) //insert element until user enter -1
    {
        printf("Please enter number to be inserted in array: ");
        scanf("%d",&input);
        if(input != -1)
        {
            printf("\nEnter number to be searched: ");
            scanf("%d",&insert_before_this_element);
            insert_element_before_an_element(input, insert_before_this_element);
        }
    }
    printArray();
    return 0;
}						
							


6. Insert an element in an array after an element

This section is to explain how to insert an element after an existing element of an array.
Problem statement:
- define an integer type array of size 100.
- Insert an element in a array after finding an exsiting element in an array.
- if element if not present insert as last element of an array.
A. Solution Steps
- search the element in array.
- if element found shift all element right side to array excluding the find element
- insert the element after shift at current postion
- if element not found insert as last element of an array
B. See below the complete Code


#include <stdio.h>
#include <malloc.h>
#define MAX_ELEMENT 100
int array[MAX_ELEMENT]; //define array of size 100 of type integer
int total_inserted_element;

//this function will initialize the array total_inserted_element variable.
void init()
{
  total_inserted_element = 0;
}
//print the array
void printArray()
{
  for(int i=0;i< total_inserted_element;i++)
    printf(" %d ",array[i]);
    printf("\n");
}

/*
  this function will search the given number i.e. insert_after_this_element
  After finding the number it will shift all number at right side.
  insert the given number
  return true - meaning successfully inserted
  return false - meaning unable to insert
*/

bool insert_element_after_an_element(int input, int insert_after_this_element)
{
   if(total_inserted_element >=99)
        return false;
   else
   {
       int index = -1;
       for(int i=0;iindex +1;i--)
            array[i] = array[i-1];
          index++;
          printArray();
          array[index] = input;
          printArray();
       }
       else
       {
          array[total_inserted_element] = input;
          total_inserted_element++;
          printArray();
       }
   }
   return true;
}


int main()
{
    int input = 0;
    int insert_after_this_element;
    while(input !=-1) //insert element until user enter -1
    {
        printf("Please enter number to be inserted in array: ");
        scanf("%d",&input);
        if(input != -1)
        {
            printf("\nEnter number to be searched: ");
            scanf("%d",&insert_after_this_element);
            
            insert_element_after_an_element(input, insert_after_this_element);
        }
    }
    printArray();
    return 0;
}


							



7. Delete an element at beginning of an Array

Deletion of an element is another important operation. In this section we will describe how to delete an from beginning
Problem statement:
- define an integer type array of size 100.
- Insert some element in a array
- Delete an element from beginning of an array.
A. Solution Steps
- Create an array of size 100.
- insert some element in array we will use insert at last you can check above codes
- Delete an element from beginning of array
B. See below the complete Code


#include <stdio.h>
#include <malloc.h>
#define MAX_ELEMENT 100
int array[MAX_ELEMENT]; //define array of size 100 of type integer
int total_inserted_element;

//this function will initialize the array total_inserted_element variable.
void init()
{
  total_inserted_element = 0;
}
/*
  this function will insert at last
  return true - meaning successfully inserted
  return false - meaning unable to insert
*/
bool insert_at_last(int input)
{
   if(total_inserted_element >=100)
        return false;
   else
   {
     array[total_inserted_element] = input;
     total_inserted_element++;
   }
   return true;
}
//print the array
void printArray()
{
  for(int i=0;i< total_inserted_element;i++)
    printf(" %d ",array[i]);
    printf("\n");
}

/*
  this function will delete from beginning
  if total_inserted_element is greater than 0 shift all element to left by one step 
*/
void delete_from_beginning()
{
    if(total_inserted_element>0)
    {
        for(int i=1; i < total_inserted_element; i++)
            array[i-1] = array[i];
        total_inserted_element--;
    }
    if(total_inserted_element<0)
        total_inserted_element = 0;
}
int main()
{
    int input = 0;
    int insert_after_this_element;
    while(input !=-1) //insert element until user enter -1
    {
        printf("Please enter number to be inserted in array: ");
        scanf("%d",&input);
        if(input != -1)
        {
            insert_at_last(input);
        }
    }
    printArray();
    delete_from_beginning();
    printf("After delete at beginning Array");
    printArray();
    return 0;
}
							

8. Delete an element at last of an Array

Deletion of an element is another important operation. In this section describe how to delete last element of an array
Problem statement:
- define an integer type array of size 100.
- Insert some element in a array
- Delete an element from last in an array.
A. Solution Steps
- Create an array of size 100.
- insert some element in array we will use insert at last you can check above codes
- Reduce the current index of array
B. See below the complete Code


#include <stdio.h>
#include <malloc.h>
int array[MAX_ELEMENT]; //define array of size 100 of type integer
int total_inserted_element;

//this function will initialize the array total_inserted_element variable.
void init()
{
  total_inserted_element = 0;
}

/*
  this function will insert at last
  return true - meaning successfully inserted
  return false - meaning unable to insert
*/
bool insert_at_last(int input)
{
   if(total_inserted_element >=100)
        return false;
   else
   {
     array[total_inserted_element] = input;
     total_inserted_element++;
   }
   return true;
}
//print the array
void printArray()
{
  for(int i=0;i< total_inserted_element;i++)
    printf(" %d ",array[i]);
    printf("\n");
}


/*
  this function will delete last element from an array

*/
void delete_from_last()
{
   if(total_inserted_element>0)
   {
      total_inserted_element--;
   }
   if(total_inserted_element<0)
    total_inserted_element = 0;

}
int main()
{
    int input = 0;
    while(input !=-1) //insert element until user enter -1
    {
        printf("Please enter number to be inserted in array: ");
        scanf("%d",&input);
        if(input != -1)
        {
            insert_at_last(input);
        }
    }
    printArray();
    delete_from_last();
    printf("After delete an element from Array");
    printArray();
    return 0;
}
							
							



9. Delete an element in an array before an element

In this section we describe how to delete an element before any element
Problem statement:
- define an integer type array of size 100.
- Insert some element in a array
- Find the given element from array
- Delete an element from array that exist before given number.
- e.g. given an array of 5 element 1 ,2,3,4,5 delete an element before 3 i.e. 2
A. Solution Steps
- Create an array of size 100.
- insert some element in array we will use insert at last you can check above codes
- Find the given element in array
- Shift all element of array by 1 step left from find index -1
B. See below the complete Code


#include <stdio.h>
#include <malloc.h>

#define MAX_ELEMENT 100
int array[MAX_ELEMENT]; //define array of size 100 of type integer
int total_inserted_element;

//this function will initialize the array total_inserted_element variable.
void init()
{
  total_inserted_element = 0;
}
/*
  this function will insert at last
  return true - meaning successfully inserted
  return false - meaning unable to insert
*/
bool insert_at_last(int input)
{
   if(total_inserted_element >=100)
        return false;
   else
   {
     array[total_inserted_element] = input;
     total_inserted_element++;
   }
   return true;
}
//print the array
void printArray()
{
  for(int i=0;i< total_inserted_element;i++)
    printf(" %d ",array[i]);
    printf("\n");
}

/*
    this function delete an element that exist before data
*/
bool delete_element_before_an_element(int data)
{
   if(total_inserted_element>0)
   {
      int index = -1;
      for(int i=0;i< total_inserted_element;i++)
      {
        if(array[i] == data)
        {
           index = i;
           break;
        }
      }
      if(index == -1)
        printf("\nGiven element : %d not found in array\n",data);
      else if(index ==0)
        printf("\nNo element exist before given element : %d not found in array\n",data);
      else
      {
          for(int i = index;i< total_inserted_element;i++)
          {
             array[i-1] = array[i];
          }
          total_inserted_element--;
          return true;
      }
      return false;
   }
   return false;
}
int main()
{
    int input = 0;
    int delete_data_before_this_element;

    while(input !=-1) //insert element until user enter -1
    {
        printf("Please enter number to be inserted in array: ");
        scanf("%d",&input);
        if(input != -1)
        {
            insert_at_last(input);
        }
    }
    printArray();
    printf("Enter an number before which data is deleted: ");
    scanf("%d",&delete_data_before_this_element);
    delete_element_before_an_element(delete_data_before_this_element);
    printf("After delete an element from Array");
    printArray();
    return 0;
}							
							



10. Delete an element in an array after an element

In this section we describe how to delete an element after any element
Problem statement:
- define an integer type array of size 100.
- Insert some element in a array
- Find the given element from array
- Delete an element from array that exist after given number.
- e.g. given an array of 5 element 1 ,2,3,4,5 delete an element after 3 i.e. 4
A. Solution Steps
- Create an array of size 100.
- insert some element in array we will use insert at last you can check above codes
- Find the given element in array
- Shift all element of array by 1 step right from find index +1
B. See below the complete Code


#include <stdio.h>
#include <malloc.h>

#define MAX_ELEMENT 100
int array[MAX_ELEMENT]; //define array of size 100 of type integer
int total_inserted_element;

//this function will initialize the array total_inserted_element variable.
void init()
{
  total_inserted_element = 0;
}

/*
  this function will insert at last
  return true - meaning successfully inserted
  return false - meaning unable to insert
*/
bool insert_at_last(int input)
{
   if(total_inserted_element >=100)
        return false;
   else
   {
     array[total_inserted_element] = input;
     total_inserted_element++;
   }
   return true;
}
//print the array
void printArray()
{
  for(int i=0;i< total_inserted_element;i++)
    printf(" %d ",array[i]);
    printf("\n");
}

/*
   this function delete an element that exist after given data
*/
bool delete_element_after_an_element(int data)
{
   if(total_inserted_element>0)
   {
      int index = -1;
      for(int i=0;i< total_inserted_element;i++)
      {
        if(array[i] == data)
        {
           index = i;
           break;
        }
      }
      if(index == -1)
        printf("\nGiven element : %d not found in array\n",data);
      else if(index == total_inserted_element -1)
        printf("\nNo element exist after given element : %d not found in array\n",data);
      else
      {
          for(int i = index+1;i< total_inserted_element -1;i++)
          {
             array[i] = array[i+1];
          }
          total_inserted_element--;
          return true;
      }
      return false;
   }
   return false;
}

int main()
{
    int input = 0;
    int delete_data_after_this_element;

    while(input !=-1) //insert element until user enter -1
    {
        printf("Please enter number to be inserted in array: ");
        scanf("%d",&input);
        if(input != -1)
        {
            insert_at_last(input);
        }
    }
    printArray();
    printf("Enter an number after which data is deleted: ");
    scanf("%d",&delete_data_after_this_element);
    delete_element_after_an_element(delete_data_after_this_element);
    printf("After delete an element from Array");
    printArray();
    return 0;
}
							



11. Search an element in an Array

section describes how to do linear search in array to find the element
Problem statement:
- define an integer type array of size 100.
- Insert some element in a array
- Find the index of given element from array
- Return the index , if not found return -1.
A. Solution Steps
- Create an array of size 100.
- Insert some element in array we will use insert at last you can check above codes
- Start looking array from 0 index till end of array
- If found stop the searching if end of array then return -1
B. See below the complete Code


#include <stdio.h>
#include <malloc.h>

#define MAX_ELEMENT 100
int array[MAX_ELEMENT]; //define array of size 100 of type integer

int total_inserted_element;

//this function will initialize the array total_inserted_element variable.
void init()
{
  total_inserted_element = 0;
}

/*
  this function will insert at last
  return true - meaning successfully inserted
  return false - meaning unable to insert
*/
bool insert_at_last(int input)
{
   if(total_inserted_element >=100)
        return false;
   else
   {
     array[total_inserted_element] = input;
     total_inserted_element++;
   }
   return true;
}
//print the array
void printArray()
{
  for(int i=0;i< total_inserted_element;i++)
    printf(" %d ",array[i]);
    printf("\n");
}


/*
    find given element in array if not return -1
*/
int find(int data)
{
   for(int i =0;i< total_inserted_element;i++)
   {
      if(array[i] == data)
        return i;
   }
   return -1;
}

int main()
{
    int input = 0;
    int data;

    while(input !=-1) //insert element until user enter -1
    {
        printf("Please enter number to be inserted in array: ");
        scanf("%d",&input);
        if(input != -1)
        {
            insert_at_last(input);
        }
    }
    printArray();
    printf("Enter an number to be find: ");
    scanf("%d",&data);
    int index = find(data);
    printf("\nIndex of data is : %d\n", index);
    if(index == -1)
        printf("\nelement not found\n");
    printArray();
    return 0;
}
							
							



12. Complete Array operation code

This code will perform all Array operation until user enter 12 to exit.


#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

#define MAX_ELEMENT 100
int array[MAX_ELEMENT]; //define array of size 100 of type integer
int total_inserted_element;

//this function will initialize the array total_inserted_element variable.
void init()
{
  total_inserted_element = 0;
}
/*
  this function will insert at beginning
  return true - meaning successfully inserted
  return false - meaning unable to insert
*/
bool insert_at_beginning (int input)
{
   if(total_inserted_element >=100)
        return false;
   else
   {
      total_inserted_element++;
      for(int i =total_inserted_element;i>0;i--)
      {
         array[i] = array[i-1];
      }
      array[0] = input;
   }
   return true;
}

/*
  this function will insert at last
  return true - meaning successfully inserted
  return false - meaning unable to insert
*/
bool insert_at_last(int input)
{
   if(total_inserted_element >=100)
        return false;
   else
   {
     array[total_inserted_element] = input;
     total_inserted_element++;
   }
   return true;
}
//print the array
void printArray()
{
  for(int i=0;i< total_inserted_element;i++)
    printf(" %d ",array[i]);
    printf("\n");
}

/*
  this function will search the given number i.e. insert_after_this_element
  After finding the number it will shift all number at right side.
  insert the given number
  return true - meaning successfully inserted
  return false - meaning unable to insert
*/

bool insert_element_after_an_element(int input, int insert_after_this_element)
{
   if(total_inserted_element >=99)
        return false;
   else
   {
       int index = -1;
       for(int i=0;iindex +1;i--)
            array[i] = array[i-1];
          index++;
          printArray();
          array[index] = input;
          printArray();
       }
       else
       {
          array[total_inserted_element] = input;
          total_inserted_element++;
          printArray();
       }
   }
   return true;
}



/*
  this function will search the given number i.e. insert_before_this_element
  After finding the number it will shift all number at right side.
  insert the given number
  return true - meaning successfully inserted
  return false - meaning unable to insert
*/

bool insert_element_before_an_element(int input, int insert_before_this_element)
{
   if(total_inserted_element >=99)
        return false;
   else
   {
       int index = -1;
       for(int i=0;iindex ;i--)
            array[i] = array[i-1];

          array[index] = input;
       }
       else
       {
          array[total_inserted_element] = input;
          total_inserted_element++;
       }
   }
   return true;
}
void delete_from_beginning()
{
    if(total_inserted_element>0)
    {
        for(int i=1;i0)
   {
      total_inserted_element--;
   }
   if(total_inserted_element<0)
    total_inserted_element = 0;

}
/*
    this function delete an element that exist before data
*/
bool delete_element_before_an_element(int data)
{
   if(total_inserted_element>0)
   {
      int index = -1;
      for(int i=0;i< total_inserted_element;i++)
      {
        if(array[i] == data)
        {
           index = i;
           break;
        }
      }
      if(index == -1)
        printf("\nGiven element : %d not found in array\n",data);
      else if(index ==0)
        printf("\nNo element exist before given element : %d not found in array\n",data);
      else
      {
          for(int i = index;i< total_inserted_element;i++)
          {
             array[i-1] = array[i];
          }
          total_inserted_element--;
          return true;
      }
      return false;
   }
   return false;
}


/*
   this function delete an element that exist after given data
*/
bool delete_element_after_an_element(int data)
{
   if(total_inserted_element>0)
   {
      int index = -1;
      for(int i=0;i< total_inserted_element;i++)
      {
        if(array[i] == data)
        {
           index = i;
           break;
        }
      }
      if(index == -1)
        printf("\nGiven element : %d not found in array\n",data);
      else if(index == total_inserted_element -1)
        printf("\nNo element exist after given element : %d not found in array\n",data);
      else
      {
          for(int i = index+1;i< total_inserted_element -1;i++)
          {
             array[i] = array[i+1];
          }
          total_inserted_element--;
          return true;
      }
      return false;
   }
   return false;
}
/*
    find given element in array if not return -1
*/
int find(int data)
{
   for(int i =0;i< total_inserted_element;i++)
   {
      if(array[i] == data)
        return i;
   }
   return -1;
}
int main_menu()
{
   int index = 0;
   printf("\n Main Menu\n");
   printf("\n==============================\n");
   printf("1: Initialize the array");
   printf("\n2: Insert at Beginning");
   printf("\n3: Insert at Last");
   printf("\n4: Insert Before an Element");
   printf("\n5: Insert After an Element");
   printf("\n6: Delete at Beginning");
   printf("\n7: Delete at Last");
   printf("\n8: Delete Before an Element");
   printf("\n9: Delete after an Element");
   printf("\n10: Find/search an Element");
   printf("\n11: Print an Element");
   printf("\n12: Exit");
   printf("\n==============================\n");
   printf("\nEnter Your Input: ");
   scanf("%d",&index);
   return index;
}
int main()
{
    int index = 0;
    do{

        index = main_menu();
        if(index == 1)
            init();
        else if(index ==2)
        {
            int input ;
            printf("\nEnter Data:");
            scanf("%d",&input);
            bool add = insert_at_beginning(input);
            if(add)
                printf("\nAdded Successfully");
            else
                printf("\nArray Full");
        }
        else if(index == 3)
        {
            int input ;
            printf("\nEnter Data:");
            scanf("%d",&input);
            bool add = insert_at_last(input);
            if(add)
                printf("\nAdded Successfully");
            else
                printf("\nArray Full");
        }
        else if(index == 4)
        {
            int input ;
            int insert_before_this_element;
            printf("\nEnter Data:");
            scanf("%d",&input);
            printf("\nEnter number to be searched: ");
            scanf("%d",&insert_before_this_element);
            insert_element_before_an_element(input, insert_before_this_element);
        }
        else if(index == 5)
        {
            int input ;
            int insert_after_this_element;
            printf("\nEnter Data:");
            scanf("%d",&input);
            printf("\nEnter number to be searched: ");
            scanf("%d",&insert_after_this_element);
            insert_element_after_an_element(input, insert_after_this_element);
        }
        else if(index == 6)
        {
            delete_from_beginning();
        }
        else if(index == 7)
        {
            delete_from_last();
        }
        else if(index == 8)
        {
            int delete_data_before_this_element;
            printf("Enter an number before which data is deleted: ");
            scanf("%d",&delete_data_before_this_element);
            delete_element_before_an_element(delete_data_before_this_element);
        }
        else if(index == 9)
        {
            int delete_data_after_this_element;
            printf("Enter an number after which data is deleted: ");
            scanf("%d",&delete_data_after_this_element);
            delete_element_after_an_element(delete_data_after_this_element);
        }
        else if(index == 10)
        {
            int data;
            printf("Enter an number to be find: ");
            scanf("%d",&data);
            int index = find(data);
            printf("\nIndex of data is : %d\n", index);
            if(index == -1)
                printf("\nelement not found\n");
        }
        else if(index == 11)
        {
            printf("\n Array is \n");
            printArray();
        }
    }while(index != 12);

    return 0;
}