Array

An array is a collection of elements of the same data type stored in contiguous memory
locations. It allows multiple values to be stored under a single name and accessed using an
index.
●​ All elements in an array must be of the same data type.
●​ Array indexing start from 0, enabling fast and direct access to elements.
Random Access: i-th item can be accessed in O(1) Time as we have the base address and
every item or reference is of same size.
Cache Friendliness: Since items / references are stored at contiguous locations, we get the
advantage of locality of reference.
Array Data Structure
An array is a linear data structure that stores a collection of elements of the same data type in
contiguous memory locations. Each element can be accessed directly using its index.
Key Characteristics
●​ Homogeneous: All elements are of the same type (int, float, char, etc.)
●​ Fixed size (in most languages like C/C++)
●​ Indexed access: Direct access using index (0-based in most languages)
●​ Contiguous memory allocation
Representation
If an array A has size n:
A[0], A[1], A[2], ..., A[n-1]
Each index points to a memory location.
Types of Arrays
1.​ One-Dimensional Array
o​ Example: int A[5] = {1,2,3,4,5};
o​ Used for lists, marks, temperatures
2.​ Two-Dimensional Array
o​ Example: int M[3][3];
o​ Used for matrices, tables
 3.​ Multi-Dimensional Array
o​ Example: int T[2][3][4];
o​ Used in image processing, tensors
Basic Operations
●​ Traversal: Visiting each element
●​ Insertion: Adding an element (costly due to shifting)
●​ Deletion: Removing an element (requires shifting)
●​ Searching: Linear search, Binary search (if sorted)
●​ Updating: Modifying an element at a given index
Time Complexity

Operation Time Complexity

Access O(1)

Search O(n)

Insertion O(n)

Deletion O(n)

Advantages
●​ Fast access using index
●​ Simple and easy to use
●​ Efficient for fixed-size data
Disadvantages
●​ Fixed size (static arrays)
●​ Wastage or shortage of memory
●​ Insertion and deletion are expensive
Real-Life Example
●​ Student marks list
●​ Days of the week
●​ Seats in a classroom row
Example (C++)
int marks[5] = {80, 85, 90, 75, 88};
cout << marks[2]; // Output: 90
Where Arrays Are Used
●​ Data storage
●​ Sorting and searching algorithms
●​ Image and signal processing
●​ Basis for other data structures (stack, queue, heap)
Example: Iterating an array element using a for loop
#include <iostream>
using namespace std;
int main() {
// declaring and initializing an array of size 5
int arr[5] = {2, 4, 8, 12, 16};
// printing array elements
for (int i = 0; i < 5; i++) {
cout << arr[i] << " ";
}
return 0;
}​
Output
2 4 8 12 16
Explanation:
●​ int arr[5] declares an array of 5 integers.
●​ The elements are initialized with {2, 4, 8, 12, 16}.
●​ The for loop is used to iterate over the array and print each element.
●​ Array indices in C++ start from 0, so arr[0] refers to the first element, and arr[4]
refers to the last one in this case.
Declaration of an Array
We can create/declare an array by simply specifying the data type first and then the name of
the array with its size inside [] square brackets (better known as array subscript operator).
Syntax:
data_type array_name [size]
This statement will create an array with name array_name that can store size elements of
given data_type. Once the array is declared, its size cannot be changed.
Example:
int arr[5];
This will create an array with name arr that can store 5 integers.
Array Declaration
When we declared an array, the elements of array do not contain any valid value.
Initialize the Array
Initialization means assigning initial values to array elements. We can initialize the array with
values enclosed in curly braces '{}' are assigned to the array.
Example:
int arr[5] = {2, 4, 8, 12, 16};
These values will be assigned sequentially. It means that the first element (index 0) will be 2,
second will be 4, and so on. The number of values in the list cannot be more than the size of
the array. But they can be less that the size. This is called partial initialization.
int arr[5] = {2, 4, 8};
Unused array elements become 0 automatically.
The size of the array can be skipped if the size should be same as the number of values.
int arr[] = {2, 4, 8, 12, 16};
Array Initialization
Moreover, all the elements can be easily initialized to 0 as shown below:
int arr[5] = {0};
This method only works for 0, but not for any other value.
{0} initializes all array elements to zero.
Note: The value assigned should be of the same type of the array elements specified in the
declaration
Operations on Array Elements
These are the common actions performed on arrays to store, access, modify, and manage data
efficiently. let's discuss one by one
1. Access Array Elements
Elements of an array can be accessed by their position (called index) in the sequence. In C++,
indexes of an array starts from 0 instead of 1. We just have to pass this index inside the []
square brackets with the array name as shown:
array_name[index];
It is important to note that index cannot be negative or greater than size of the array minus
1. (0 ≤ index ≤ size - 1). Also, it can also be any expression that results in valid index value.
Example:
C++
#include <iostream>
using namespace std;
int main() {
int arr[] = {2, 4, 8, 12, 16};
// Accessing fourth element
cout << arr[3] << " ";
// Accessing first element
cout << arr[0];
return 0;
}​
Output
12 2
2. Update Array Elements
To change the element at a particular index in an array, just use the = assignment
operator with new value as right hand expression while accessing the array element.
array_name[index] = value;
Example:
C++
#include <iostream>
using namespace std;
int main() {
int arr[] = {2, 4, 8, 12, 16};
// Updating first element
arr[0] = 90;
cout << arr[0] << endl;
return 0;
}​
Output
90
3. Traverse Array
Traversing means visiting each element one by one. The advantage of array is that it can be
easily traversed by using a loop with loop variable that runs from 0 to size - 1. We use this
loop variable as index of the array and access each element one by one sequentially.
Example:
#include <iostream>
using namespace std;
int main() {
int arr[5] = {2, 4, 8, 12, 16};
// Traversing and printing arr
for (int i = 0; i < 5; i++)
cout << arr[i] << " ";
return 0;
}​
Output
2 4 8 12 16

4. Size of Array
The size of the array refers to the number of elements that can be stored in the array. The
array does not contain the information about its size but we can extract the size
using sizeof() operator.
#include <iostream>
using namespace std;
int main() {
char arr[] = {'a', 'b', 'c', 'd', 'f'};
// Size of one element of an array
cout << "Size of arr[0]: " << sizeof(arr[0])
<< endl;
// Size of 'arr'
cout << "Size of arr: " << sizeof(arr) << endl;
// Length of an array
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Length of an array: " << n << endl;
return 0;
}​
Output
Size of arr[0]: 1
Size of arr: 5
Length of an array: 5
Multi-Dimensional Array (Two-Dimensional Array)
A multi-dimensional array can be defined as an array that has more than one dimension.
Having more than one dimension means that it can grow in multiple directions. Some popular
multidimensional arrays include 2D arrays which grows in two dimensions, and 3D arrays
which grows in three dimensions.
#include <iostream>
using namespace std;
int main() {
// declaring and initializing a 2D array
// with 3 rows and 4 columns
int matrix[3][4] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}
};
// printing the elements of the 2D array
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 4; j++) {
cout << matrix[i][j] << " ";
}
cout << endl;
}
return 0;
}
Output
1234
5678
9 10 11 12
Explanation:

int matrix[3][4] declares a 2D array with 3 rows and 4 columns.

The array is initialized using nested braces {} for each row.
We use two nested for loops to access and print each element: the outer loop for rows and the
inner loop for columns.
matrix[i][j] accesses the element at the i-th row and j-th column.
Example:
// Two dimensional array
int two_d[2][4];
Arrays Size
For 1D array, the length of the array is simply its size too. But multidimensional arrays have
extra dimensions. So, the size of each dimension is considered separately. The size of
multidimensional array is the product of all its dimensions' size. It is similar to calculating
area in 2D and volume in 3D.
For example, consider the below array:
int arr1[2][4];
The array int arr[2][4] can store total (2 * 4) = 8 elements (product of its dimensions).
The size in bytes can be calculated by multiplying the number of elements by size of each
element or we can just use sizeof operator.
In this case, size in bytes = 4*8 = 32 bytes.
To verify the above calculation, we can use sizeof() method to find the size of an array.
#include <iostream>
using namespace std;
​int main() {
// creating 2d and 3d array
int arr[2][4];
// using sizeof() operator to
 // get size of arr
cout << sizeof(arr) << " bytes";
return 0; }

Output
32 bytes
Two-Dimensional Array (2D Array)
A two-dimensional array in C++ is a collection of elements organized the form of rows and
columns. It can be visualized as a table or a grid.

Create 2D array
int arr[2][4];
Initialize 2D Array
Like 1D arrays, 2D arrays can also be initialized using a list of values enclosed inside {}
curly brackets, but as 2D arrays have two dimensions, the list is nested inside another list to
initialize each dimension one by one. It means that each row values are nested inside one big
list.
int arr[2][4] = {{0, 1, 2, 3}, {4, 5, 6, 7}};
Nesting can also be omitted, and values will still be assigned sequentially.
int arr[2][4] = {0, 1, 2, 3, 4, 5, 6, 7};
The above array has 2 rows and 4 columns. The elements are filled in a way that the first 4
elements are filled in the first row and the next 4 elements are filled in the second row. The
values will be initialized sequentially.
It is to be noted that the number of values should not exceed the total number of elements an
array can store. It can have less values (partial initialization) but cannot have more values.
If all the elements are to be initialized to 0, then this syntax can be used:
int arr[2][4] = {0};
This can be only done for 0, not for any other value.
Access and Update Elements
Elements of a 2D array must be accessed using row and column indices inside [] square
brackets. It is similar to matrix element position, but the only difference is that here indexing
starts from 0.
The value of any element can be updated by using = assignment operator.
arr[i][j];
array_name[i][j] = new_value
where, i is the index of row, j is the index of the column, and new_value to updated. The
range of indexes should be:
0 ≤ i ≤ (row_size - 1)
0 ≤ j ≤ (col_size - 1)
Any values other than that leads to the segmentation fault.
Example:
#include <iostream>
using namespace std;
int main() {
int arr[2][4] = {0, 1, 2, 3, 4, 5, 6, 7};
// Accessing 3rd element is 1st row
cout << arr[0][2] << endl;
// Accessing first element in 2nd row
cout << arr[1][0] << endl;
// Updating 3rd element is 1st row
 arr[0][2] = 22;
cout << arr[0][2] << endl;
// Updating first element in 2nd row
arr[1][0] = 99;
cout << arr[1][0];
return 0;
}
Output
2
4
22
99
Traverse 2D Array
Two loops nested inside each other are needed to traverse a 2D array. First loop is used to
move though the rows of 2D array, while other is used to move though columns in each row
to access all the elements of the row.
#include <iostream>
using namespace std;
int main() {
int arr[2][4] = {0, 1, 2, 3, 4, 5, 6, 7};
// Outer loop to move through rows
for (int i = 0; i < 2; i++) {
// Inner loop to move though elements in each row
for (int j = 0; j < 4; j++) {
cout << arr[i][j] << " ";
}
cout << endl; }
return 0;
}
Output
0123
4567

Index to Address Translation in an Array

Index to address translation is the process of converting an array index into the actual
memory address where the element is stored.
Because arrays are stored in contiguous memory locations, this translation is done using a
simple mathematical formula.
General Formula
For a 1-D array A:
Address of A[Index] = B + W * (Index - LB)
Where:
●​ Index = The index of the element whose address is to be found (not the value of
the element).
●​ B = Base address of the array.
●​ W = Storage size of one element in bytes.
●​ LB = Lower bound of the index (if not specified, assume zero).

Example 1: One-Dimensional Array

int A[5];
Assume:
●​ Base address of A[0] = 1000
●​ Size of int = 4 bytes
Find address of A[3]:

Example: Given the base address of an array A[1300 ............ 1900] as 1020 and the size
of each element is 2 bytes in the memory, find the address of A[1700].
Solution:
Given:
●​ Base address (B) = 1020
 ●​ Lower bound (LB) = 1300
●​ Size of each element (W) = 2 bytes
●​ Index of element (not value) = 1700

Formula used:​
Address of A[Index] = B + W * (Index - LB)​
Address of A[1700] = 1020 + 2 * (1700 - 1300)​
= 1020 + 2 * (400)​
= 1020 + 800​
Address of A[1700] = 1820
Why Index to Address Translation Is Fast
●​ No traversal required
●​ Direct mathematical calculation
●​ Gives O(1) access time
Calculate the address of any element in the 2-D array:

●​ The 2-dimensional array can be defined as an array of arrays. The 2-Dimensional

arrays are organized as matrices which can be represented as the collection of rows
and columns as array[M][N] where M is the number of rows and N is the number of
columns.
●​ Example:
To find the address of any element in a 2-Dimensional array there are the following two
ways-
1.​ Row Major Order
2.​ Column Major Order
1. Row Major Order:
Row major ordering assigns successive elements, moving across the rows and then down the
next row, to successive memory locations. In simple language, the elements of an array are
stored in a Row-Wise fashion.​
To find the address of the element using row-major order uses the following formula:
Address of A[I][J] = B + W * ((I - LR) * NC + (J - LC))
I = Row Subset of an element whose address to be found, ​
J = Column Subset of an element whose address to be found, ​
B = Base address, ​
W = Storage size of one element store in an array(in byte), ​
LR = Lower Limit of row/start row index of the matrix(If not given assume it as zero), ​
LC = Lower Limit of column/start column index of the matrix(If not given assume it as
zero), ​
N = Number of column given in the matrix.
Example: Given an array, arr[1.........10][1.........15] with base value 100 and the size of each
element is 1 Byte in memory. Find the address of arr[8][6] with the help of row-major order.
Solution:
Given:​
Base address B = 100​
Storage size of one element store in any array W = 1 Bytes​
Row Subset of an element whose address to be found I = 8​
Column Subset of an element whose address to be found J = 6​
Lower Limit of row/start row index of matrix LR = 1 ​
Lower Limit of column/start column index of matrix = 1​
Number of column given in the matrix N = Upper Bound - Lower Bound + 1​
= 15 - 1 + 1​
= 15
Formula:​
Address of A[I][J] = B + W * ((I - LR) * N + (J - LC))
Solution:​
Address of A[8][6] = 100 + 1 * ((8 - 1) * 15 + (6 - 1))​
= 100 + 1 * ((7) * 15 + (5))​
= 100 + 1 * (110)​
Address of A[I][J] = 210
2. Column Major Order:
If elements of an array are stored in a column-major fashion means moving across the
column and then to the next column then it's in column-major order. To find the address of
the element using column-major order use the following formula:
Address of A[I][J] = B + W * ((J - LC) * NR + (I - LR))
I = Row Subset of an element whose address to be found, ​
J = Column Subset of an element whose address to be found, ​
B = Base address, ​
W = Storage size of one element store in any array(in byte), ​
LR = Lower Limit of row/start row index of matrix(If not given assume it as zero), ​
LC = Lower Limit of column/start column index of matrix(If not given assume it as zero), ​
NR = Number of rows given in the matrix.
Example: Given an array arr[1.........10][1.........15] with a base value of 100 and the size of
each element is 1 Byte in memory find the address of arr[8][6] with the help of column-major
order.
Solution:
Given:​
Base address B = 100​
Storage size of one element store in any array W = 1 Bytes​
Row Subset of an element whose address to be found I = 8​
Column Subset of an element whose address to be found J = 6​
Lower Limit of row/start row index of matrix LR = 1​
Lower Limit of column/start column index of matrix = 1​
Number of Rows given in the matrix M = Upper Bound - Lower Bound + 1​
= 10 - 1 + 1​
= 10
Formula: used​
Address of A[I][J] = B + W * ((J - LC) * M + (I - LR))​
Address of A[8][6] = 100 + 1 * ((6 - 1) * 10 + (8 - 1))​
= 100 + 1 * ((5) * 10 + (7))​
= 100 + 1 * (57)​
Address of A[I][J] = 157
From the above examples, it can be observed that for the same position two different address
locations are obtained that is because in row-major order movement is done across the rows
and then down to the next row, and in column-major order, first move down to the first
column and then next column. So, both the answers are right.
So it's all based on the position of the element whose address is to be found for some cases
the same answers is also obtained with row-major order and column-major order and for
some cases, different answers are obtained.
Row Major Order vs Column Major Order

Aspect Row Major Order Column Major Order

Elements are stored row by Elements are stored column

row in contiguous by column in contiguous
Memory Organization locations. locations.

For a 2D array A[m][n]: For the same array:

[A[0][0], A[0][1], ..., [A[0][0], A[1][0], ...,
Memory Layout Example A[m-1][n-1]] A[m-1][n-1]]

Moves through the entire Moves through the entire

row before progressing to column before progressing
Traversal Direction the next row. to the next column.

Efficient for row-wise Efficient for column-wise

access, less efficient for access, less efficient for
Access Efficiency column-wise access. row-wise access.

Commonly used in Commonly used in

Common Use Cases languages like C and C++. languages like Fortran.

Suitable for row-wise Suitable for column-wise

operations, e.g., image operations, e.g., matrix
Applications processing. multiplication.