Data Structures - Arrays
Data Structures and Algorithms
In this tutorial we will learn about Array data structure.
Table of Content
- What is an Array?
- Types of Array
- One Dimensional Array
- Two Dimensional Array
- Multi Dimensional Array
- Array Operations
- When to use an Array?
What is an Array?
An array is a finite collection of elements of similar data type stored in adjacent memory location.
Important points
- An array contains
nelements. - Each element of the array is referrenced by its index.
- Array index starts from 0. So, if an array has
nelements then index will be from 0 to n-1. - First element of the array is at index 0.
- Last element of the array of size n is at index n-1.
- The first index 0 is also called the lower bound of the array.
- The last index n-1 is also called the upper bound of the array.
Types of Array
Arrays can be divided into three types.
- One dimensional (1D) or Linear array
- Two dimensional (2D) array
- Multi dimensional array
One Dimensional Array
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.
- The variable
arrwill point at the memory location 1000 which is also the address of the first element of the array. - Since each element of the array is taking 2 bytes so the first element will occupy address 1000 and 1001.
- Second element will occupy address 1002 and 1003.
- Third element will occupy address 1004 and 1005.
1d array memory representation
Address Array
+---------+--------+
| 0998 | |
+---------+--------+
| 0999 | |
+---------+--------+
| 1000 | arr[0] | <---- arr
+---------+--------+
| 1001 | |
+---------+--------+
| 1002 | arr[1] |
+---------+--------+
| 1003 | |
+---------+--------+
| 1004 | arr[2] |
+---------+--------+
| 1005 | |
+---------+--------+
| 1006 | |
+---------+--------+
| 1007 | |
+---------+--------+
Two Dimensional Array
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 ith row and jth column we write the following code.
arr[i][j]Storing 2D array in memory
A 2D array is saved in memory in two ways - Row Major and Column Major.
Row 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
Memory address of an item for Row Major
We use the following formula to find the memory address of an item at position ith row and jth 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
= 1010Column Major
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
Memory address of an item for Column Major
We use the following formula to find the memory address of an item at position ith row and jth 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
= 1014Multi Dimensional Array
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];
Array Operations
We can perform the following operations on an array.
- Traversal - travelling the array from left to right and in reverse.
- Insertion - insert a new element at the end, beginning and in between.
- Deletion - remove an element at a given index.
- Reversing - reverse the element of the array.
- Merging - merge two or more arrays into one.
- Sorting - sort the elements of an array using any of the sorting algorithm.
- Searching - search for a particular element in an array.
When to use an Array?
- Arrays can be used to store values of same data type.
- They are efficient is accessing values and manipulating values in O(1) time complexity using the array index.
Do not use array in following cases.
- Storing sparse data as it will be an inefficient use of memory.
- For storing dynamic size data. As array size is fixed, hence we have to create a new array and copy the older array into the newer array of relatively bigger or smaller size.
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