Data Structures and Algorithms
In this tutorial we will learn about Array data structure.
An array is a finite collection of elements of similar data type stored in adjacent memory location.
Important points
n
elements.n
elements then index will be from 0 to n-1.Arrays can be divided into three types.
1D array are also known as linear array.
We create a one dimensional or 1D array using the following syntax.
Code in C/C++
data_type variable_name[size];
In the following example we are creating an array of size 6 and data type int
.
int arr[3];
If data type int
is of size 2 bytes then the above code will occupy 2x3 = 6 bytes of contiguous memory location.
Let us assume that each block of memory is of size 1 byte and the array arr
is allocated contiguous memory blocks from address 1000. Then we will have the following points to note.
arr
will point at the memory location 1000 which is also the address of the first element of the array.1d array memory representation
Address Array
+---------+--------+
| 0998 | |
+---------+--------+
| 0999 | |
+---------+--------+
| 1000 | arr[0] | <---- arr
+---------+--------+
| 1001 | |
+---------+--------+
| 1002 | arr[1] |
+---------+--------+
| 1003 | |
+---------+--------+
| 1004 | arr[2] |
+---------+--------+
| 1005 | |
+---------+--------+
| 1006 | |
+---------+--------+
| 1007 | |
+---------+--------+
We create a two dimensional or 2D array using the following syntax.
data_type variable_name[row][col];
Example:
int arr[3][3];
The above code creates an integer array having 3 rows and 3 columns.
row --->
0 1 2
col 0 arr(0,0) arr(0,1) arr(0,2)
1 arr(1,0) arr(1,1) arr(1,2)
2 arr(2,0) arr(2,1) arr(2,2)
In order to retrieve a value stored at i
th row and j
th column we write the following code.
arr[i][j]
A 2D array is saved in memory in two ways - Row Major and Column Major.
In Row Major order the rows of the array are saved contiguously in memory like the following.
We are assuming each item of the array is taking 2 bytes.
ROW MAJOR
ArrayItem MemoryAddress
arr(0,0) 1000
arr(0,1) 1002
arr(0,2) 1004
arr(1,0) 1006
arr(1,1) 1008
arr(1,2) 1010
arr(2,0) 1012
arr(2,1) 1014
arr(2,2) 1016
We use the following formula to find the memory address of an item at position i
th row and j
th column in a 2D array of size RxC (row x column) that is saved in Row Major order.
MemoryAddress = baseAddress + (i * C + j) * itemSize
Example: If we want to find the memory address of item arr[1][2] then we will compute the following.
baseAddress = 1000
itemSize = 2
i = 1
j = 2
C = 3
MemoryAddress = baseAddress + (i * C + j) * itemSize
= 1000 + (1 * 3 + 2) * 2
= 1000 + (3 + 2) * 2
= 1000 + 5 * 2
= 1000 + 10
= 1010
In Column Major order the columns of the array are saved contiguously in memory like the following.
We are assuming each item of the array is taking 2 bytes.
COLUMN MAJOR
ArrayItem MemoryAddress
arr(0,0) 1000
arr(1,0) 1002
arr(2,0) 1004
arr(0,1) 1006
arr(1,1) 1008
arr(2,1) 1010
arr(0,2) 1012
arr(1,2) 1014
arr(2,2) 1016
We use the following formula to find the memory address of an item at position i
th row and j
th column in a 2D array of size RxC (row x column) that is saved in Column Major order.
MemoryAddress = baseAddress + (j * R + i) * itemSize
Example: If we want to find the memory address of item arr[1][2] then we will compute the following.
baseAddress = 1000
itemSize = 2
i = 1
j = 2
R = 3
MemoryAddress = baseAddress + (j * R + i) * itemSize
= 1000 + (2 * 3 + 1) * 2
= 1000 + (6 + 1) * 2
= 1000 + 7 * 2
= 1000 + 14
= 1014
Any array beyond 2D is termed as a multidimensional array.
In the following example we are creating a three dimensional array.
Code in C/C++
char str[2][3][4];
We can perform the following operations on an array.
Do not use array in following cases.
Alright, in the next tutorials we will be covering each of the array operations in detail. See you in the next tutorial. Thank you for reading. Have fun learning.
ADVERTISEMENT