When Array’s dimensionality is one, this types of array comes under the 1-D Array Category. One Dimensional Array or 1-D array contain only single row but more than one column.This is an Linear array.
Declaration & Initialization of 1-D Array
In C and C++ ,Syntax of 1-D array is following :
DataType NameOfArray [Size of Array]- First we have to define DataType of array ,Data types can be int , float,char ,bool etc
- NameOfArray can be any valid name , means It depend upon the programming Language restriction. Like In C & C++ we can not give any name which start with a number.Example : 12ArrName this is wrong name of array in C & C++.
- Size of Array define the length of array, means how many block of memory compiler will allocate for the array, and this allocated Size will be fixed. we can not grow out of the allocated size.Size can be any positive integer.Size always written inside the [].
We can declare an 1-D array as following :
int Arr1D[10] // Arr1D is array of integer of size 10.
char Arr1D[8] // Arr1D is array of char of size 8.
bool Arr1D[20] // Arr1D is array of bool of size 20.For 1-D array Initialization , we can do by two ways :
- First way : we can declare an array and then initialize the data into declared array.
- Second way : we can initialize an array during the declaration.
int Arr1D[4] // Array Declaration
Arr1D[4]={90,100,200,80} //Initialization of Arr1D.
char Arr1D[3] = {'A','V','U'} // declaration and initialization - We have to initialize the data into array as per the data type, means if we our Array data type is int and we initialize it by another data type like char,bool etc, So this is wrong implementation of array,means if Array Data type is int then we can initialize integer type data element into an array . Example :
int Arr1D[4]={'A','B','C','E'}; // Wrong initialization of an arrayHere Arr1D[4] is int type ,but we storing char type data,So this is wrong initialization
Accessing of 1-D Array
- We can access the array by the index value of every element.
- We can also access by the address value of every element , for this we need one extra pointer variable to access it.
Example :
/*Index Accessing*/
#include <stdio.h>
#define SIZE 5 //size of an array
int main()
{
int Arr[SIZE] ={20,90,60,19,75}; // This is Array Initialization.
printf("%d",Arr[3]); // Print the value if index-3
Printf("%d",Arr[0]); // Print the value if index-0
return 0;
} /*Pointer Accessing*/
#include <stdio.h>
#define SIZE 5 //size of an array
int main()
{
int Arr[SIZE] ={20,90,60,19,75}; // This is Array Initialization.
// Initialization of an pointer p which contain the address of Base Element(Arr[0])
int *p=Arr;
printf("%d\n",*p); // Print the value if index-0
printf("%d\n",*(p+1)); // Print the value if index-1
printf("%d\n",*(p+4)); // Print the value if index-4
return 0;
}Operations on 1-D Array
- Insert Operation : See the following C Program to understand the insertion process at any specific index.
#include <stdio.h>
#include <conio.h>
int main() {
int Arr1D[] = {20,100,200,300,50}; // Array Initilization
int ElementForAddition = 80; //Element for Addition
int IndexForAddition= 4; // index on which Element will Insert
int size=sizeof(Arr1D)/sizeof(Arr1D[0]); // length of array.
int j = size; // Initilization of Size in another variable j
printf("Array before Inserting :\n");
for(int i = 0; i<size; i++) {
printf("%d ",Arr1D[i]);
}
size = size + 1; // we are inserting one Element ,So length will increase by one.
while( j >= IndexForAddition) { // For Relocation of elements
Arr1D[j+1] = Arr1D[j];
j = j - 1;
}
Arr1D[IndexForAddition] = ElementForAddition; // insert new Element into Arr1D at specified index
printf("\nArray After Insertion :\n");
for(int i = 0; i<size; i++) {
printf("%d ",Arr1D[i]);
}
return 0;
}
- Delete Operation : Below C implementation is for Delete operation of 1-D Array.
#include <stdio.h>
#include <conio.h>
int main() {
int Arr1D[] = {20,100,200,300,50}; // Array Initilization
int IndexForDeletion= 4; // index on which Element will delete
int size=sizeof(Arr1D)/sizeof(Arr1D[0]); // length of array.
int j;
printf("Array before deletion :\n");
for(int i = 0; i<size; i++)
{
printf("%d ", Arr1D[i]);
}
j = IndexForDeletion;
while( j < size) // // For Relocation of elements
{
Arr1D[j] = Arr1D[j+1];
j = j + 1;
}
size = size -1; // decrease the array size by one.
printf("\nArray after deletion :\n");
for(int i = 0; i<size; i++) {
printf("%d ", Arr1D[i]);
}
return 0;
}
- Traverse Operation :Traversing means we have to visit on every element. It is similar to the printing all the element of array. Refer to the following C implementation to understand Traverse Operation :
#include <stdio.h>
#include<conio.h>
int main() {
int Arr1D[] = {200,300,89,90,800,54}; // Array Initialization
int SIZE=sizeof(Arr1D)/sizeof(Arr1D[0]); // Length of array
printf("Traversed Elements are :\n");
for(int i = 0; i<SIZE; i++) { // Traverse the elements and print it.
printf("%d ",Arr1D[i]);
}
return 0;
}
- Search Operation : if we want to check whether an element is present or not in the array ,then we have to perform search operation.
below C implementation is for Search operation of an 1-D Array :
#include <stdio.h>
#include <conio.h>
int main() {
int Arr1D[] = {200,300,100,90,80,56,53}; // Array initilization
int elementToSearch=300; // Element for searching
int SIZE =sizeof(Arr1D)/sizeof(Arr1D[0]); //Length of array
int flag=0; // to check element is Present or not.
for(int i = 0; i<SIZE; i++) {
if(Arr1D[i]==elementToSearch) // check for availability of element
{
flag=0;
printf("Yes Element is Present at index %d ,that is %d",i,Arr1D[i]);
break;
}
else
flag=1;
}
if(flag!=0)
{
printf("\nSorry...Element is not availabel...");
}
return 0;
}
Time & Space Complexity of 1-D
Lets see one example to determine the complexities of 1-D for different different operations :
- For Search Operation :
1- Worst Case : If required element is present at last index then we need to traverse all the element then Complexity will be O(n).
2- Best Case : if required element is present at first index, then in first iteration we will get it, So complexity will be O(1).
3- Average Case : when required element is not present at first index and also not available at last .then we have to consider all possible complexities and take the average of all,then Complexity will be O(n). - For Insertion Operation :
1- Worst Case :If we want to add an element 70 at index 0 into Arr1D ,then first we have to relocate all the element to the one index further and then insert at index 0. In this situation Complexity T(n) will be :
T(n) = T(Relocation) + T(insertion)
T(n) = O(n) + O(1) =O(n).
2- Best Case : If we want add an element at last ,then directly we can insert by using index value.So Complexity will be O(1).
3- Average Case :if we are adding an element on the middle location ,then we have to consider all the possible complexity, So Complexity will be O(n). - For Deletion Operation :
1- Worst Case :If we want to delete first element of an array,then after deleting we have to relocate all the element to the one index back. In this situation Complexity T(n) will be :
T(n) = T(Relocation) + T(Deletion)
T(n) = O(n) + O(1) = O(n).
2- Best Case : If we want to delete last element of an array ,then we can delete very easily by using index ,and the Complexity will be O(1).
3- Average Case : If we are not deleting first and last index element ,means element can be present at any location except first and last,So we have consider all the possible complexities and take the average ,In this situation Complexity will be O(n). - For Traverse Operation :
Traverse means visiting on every element ,So we have to access all the element , Complexity will be O(n). - Worst Case Space Complexity will be O(n).