Array
1
Array
• An array is a finite ordered collection of similar type of data items, stored at contiguous memory
locations.
• Array is a derived (non-primitive) data type which can store homogenous elements of primitive data
types such as integers, characters, floats, etc.
• The character array is called a string, whereas an integer or float array is called simply an array.
• Each element of an array has the same data type and carries the same size [int = 4 bytes].
• Arrays are the simplest data structure, where each data element can be randomly accessed by using
its index number.
• Traversing an array is very simple
• The position of each element can be calculated by simply adding an offset to a base value, i.e.,
the memory location of the first element (index 0).
• Remember: “Location of next index depends on the data type we use”
2
Array Representation
The two important terms to understand the concept of Array:
• Element − Each data item stored in an array is called an element.
• Index − Each location of an element in an array has a numerical index (used to identify the element).
• Index of an array starts at 0 and goes up to size-1. |--------------------------------|
• So, first element of an array is stored at index [0] Array Size: 5
and the last element is stored at index [size-1]
Ref: [Link] 3
Declaring and Initializing an Array
• Arrays must be declared before they are used.
<datatype array_name[size]>;
int arr[10]; int is the data type, arr is the name of the array and 10 is the size of array.
char s[3]; It means array arr can only contain 10 elements of int type.
float marks[5];
• After declaration array must be initialized, else it will contain garbage values.
<datatype array_name[size]>; <datatype array_name[size] = { list of values }>;
<array_name[index] = {value}>;
int age[4] = { 12, 17, 5, 15 };
int age[4];
age[0] = 12; float area[5] = { 23.4, 6.8, 5.5};
age[1] = 17;
age [2] = 5;
4
Declaring and Initializing an Array
• An array can be initialized at either Compile time or at Runtime
int age[4] = {12, 17, 5, 15}; #include <iostream>
using namespace std;
float area[5] = {23.4, 6.8, 5.5};
int main()
int age[4] = {12, 17, 5, 15 , 9}; //Is this correct? {
int arr[4], i;
int age[4] = {12, 17, 5}; //Is this correct? int i;
cout<<"Enter elements in the array :";
Note: If we initialize only a few elements of an array,
then the remaining elements get initialized with zero for(i=0; i < 4; i++)
value. cin>>arr[i];
return 0;
}
In C++, most standard library functions and objects are inside the std namespace, eg. cout, cin, endl, vector and string
5
Memory Allocation in an Array
• There is contiguous memory allocation for different elements of an array.
An integer array having12 elements.
Indexes are from 0 to 11
Why does the memory location of each array element differ by 4?
Assuming integer takes four bytes and the base address of the array is 200.
So, the address of first element is 200, address of second element is 204,
address of third element 208, and so on.
Ref: [Link] 6
Array Traverse Operation
#include <iostream>
using namespace std;
int main()
{
int arr[6], i;
cout<<"Enter elements in the array : ";
for(i=0; i < 6; i++)
cin>>arr[i];
cout<<"\n Elements in the array are:\n";
for(i=0; i < 6; i++)
cout<<arr[i]<<" ";
return 0;
}
7
Linear Search Operation
#include <iostream>
using namespace std;
int main()
{
int arr[5] = {1,3,5,7,9}, search_el, i, found=0;
cout<<"\nOriginal array\n";
for(i=0; i < 5; i++)
{cout<<arr[i]<<" ";}
cout<<"\n\nInput element to be searched:";
cin>>search_el;
for(i=0; i<5; i++)
{ if(arr[i] == search_el)
found=1;
break;
}
if(found==1)
cout<<"\nFound element "<<search_el<<" at position "<<i+1; Time complexity : O(n)
else
cout<<"\n Element not found;
return 0;
}
8
Binary Search Operation
#include <iostream>
using namespace std;
int main()
{ int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int size = sizeof(arr) / sizeof(arr[0]);
int left=0, right=size-1, f=0, key;
cout << "Enter the Element to be searched";
cin >> key;
while (left <= right)
{ // calculate mid point
int mid = left + (right - left) / 2;
if (arr[mid] == key)
{
cout<< " Element found at" << mid+1<<"position";
f=1;
break;
}
Time complexity : O(log2 n)
// If key greater than arr[mid], ignore left half
if (arr[mid] < key)
{ left = mid + 1; }
else // If key less than or equal to arr[mid], ignore right half
{ right = mid - 1; }
}
if (f==0)
cout<< " Element Not Found";
}
9
Insert Operation
• An element can be inserted at the beginning, end, or any given position in an array
• For inserting an element at a particular position, all elements from that position onwards must be shifted forward.
Initial Array
a[0] a[1] a[2] a[3] a[4] a[5] …
2 4 8 10 12
Elements shifted forward
starting from position 3
a[0] a[1] a[2] a[3] a[4] a[5] …
2 4 8 10 12
Final array with new element inserted at position 3
a[0] a[1] a[2] a[3] a[4] a[5] …
2 4 6 8 10 12
10
Insertion Operation
Following program demonstrates how to insert an element at a given index/ end of the array
#include <iostream>
using namespace std;
int arr[10] = {2,4,8,10,12}, count=5;
void insert_element(int new_el, int indx); void insert_element(int new_el, int
int main() indx)
{ {
int i, new_el, indx; int i;
if (indx >= count)
cout<<"\nInitial array\n";
arr[count] = new_el;
for(i=0; i < 5; i++)
cout<<arr[i]<<" "; else
{
cout<<"\n\nInput element to be inserted and its position:"; for(i=count-1; i>=indx-1; i--
cin>>new_el>>indx; )
arr[i+1] = arr[i];
insert_element(new_el, indx); arr[indx-1] = new_el;
}
cout<<"\nFinal array\n";
for(i=0; i < count; i++) count++;
cout<<arr[i]<<" "; }
return 0;
}
11
Insertion Operation
Inserting 6 at position 3
Inserting 14 at position 6 [at the end of the array]
12
Deletion Operation
• An element can be deleted from the beginning, end, or any given position in an array
• For deleting an element at a particular position, all elements from that position onwards must be shifted backwards.
Initial Array
a[0] a[1] a[2] a[3] a[4] a[5] …
2 4 6 8 10 12
Elements shifted backwards from position 3
a[0] a[1] a[2] a[3] a[4] a[5] …
2 4 8 10 12
Final array with element
deleted at position 3
a[0] a[1] a[2] a[3] a[4] a[5] …
2 4 8 10 12
13
Deletion Operation
Following program demonstrates deletion of an element at a given index
#include <iostream> int delete_element(int indx)
using namespace std; {
int arr[10] = {2,4,6,8,10,12}, count=6; int i,k;
int delete_element(int indx); k=arr[indx-1];
int main() for(i=indx-1; i<count; i++)
{ arr[i] = arr[i+1];
int i, del_el, indx;
count--;
cout<<"\nInitial array\n"; return k;
for(i=0; i < 6; i++) }
cout<<arr[i]<<" ";
Deleting element at position 3
cout<<"\n\nInput position of element to be deleted: ";
cin>>indx;
del_el = delete_element(indx);
cout<<"\nDeleted element: "<<del_el<<"\n";
cout<<"\nFinal array\n";
for(i=0; i < count; i++)
cout<<arr[i]<<" ";
return 0;
}
14
Sorting of Array : Bubble sort
#include <iostream>
using namespace std;
int main()
{
int i, j, temp;
int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int size = sizeof(arr) / sizeof(arr[0]);
for (i=0;i<size; i++)
{
for (j=i+1;i<size; i++)
{
if (arr[j]>arr[j+1])
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
} Time complexity : O(n²)
}
}
for (i=0;i<size; i++)
{
cout << arr[i] << "\t";
}
}
15
Passing Array to Function
• Like any simple variable, an array can also be passed to a function.
• By default an array is passed using call by reference, as its name points to the address of the first
element of array.
• Individual elements of the array can be passed using call by value.
Example 1:
void fun1(int ar[]); // function declaration
fun1(ar); // function calling… passing entire array
Example 2:
void fun2(int x); // function declaration
fun2(ar[2]); // function calling… passing the value of ar[2]
16
Declaring & Initializing a 2D Array
datatype array_name[row_size][column_size] Runtime initialization of a 2D Array
int a[3][4]; #include <iostream>
using namespace std;
int arr[][3] = {{0,0,0},{1,1,1}}; int main()
{
int arr[3][4], i, j, k;
cout<<"Enter array element";
Note: We have not assigned any row value to our for(i = 0; i < 3;i++)
array here. It means we can initialize any number {
of rows. But, we must always specify number of for(j = 0; j < 4; j++)
columns, else it will give a compile time error. cin>>arr[i][j];
}
for(i = 0; i < 3; i++)
{
for(j = 0; j < 4; j++)
cout<<arr[i][j];
cout<< "\n";
}
return 0;
}
17
Array: Complexity Analysis
Insertion Position Time Why
At end O(1) (amortized) No shifting if space exists
At end (full array) O(n) Resize + copy
At beginning O(n) Shift all elements right
At middle / index i O(n) Shift elements
At given index (random access) O(1) Index is directly accessible
Deletion Position Time Why
From end O(1) No shifting
From beginning O(n) Shift elements left
From middle / index i O(n) Shifting required
Delete by value O(n) Search + shift
18
Advantages and Disadvantages of Array
Advantages
• Arrays store multiple elements of the same type with the same name.
• Faster search time, as you can access elements in the array by adding an offset to the base value of the array.
• Arrays avoid memory overflow.
• 2D arrays can efficiently represent the tabular data.
Disadvantages
• Array size should be predefined.
• An array is static. It cannot alter its size after declaration.
• Arrays have slow insertion and deletion times, as both insertion and deletion require shifting of elements.
• Allocating excess memory than required may lead to memory wastage.
19