Data Structures and Algorithms

In this tutorial we will learn about Array data structure.

- What is an Array?
- Types of Array
- One Dimensional Array
- Two Dimensional Array
- Multi Dimensional Array
- Array Operations
- When to use an Array?

An array is a finite collection of elements of similar data type stored in adjacent memory location.

Important points

- An array contains
`n`

elements. - Each element of the array is referrenced by its index.
- Array index starts from
**0**. So, if an array has`n`

elements 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.

Arrays can be divided into three types.

- One dimensional (1D) or Linear array
- Two dimensional (2D) array
- Multi 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
`arr`

will 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 | |
+---------+--------+
```

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.

**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.

- 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