Web
Analytics Made Easy - StatCounter

Arrays

What is an array?

An array is a contiguous area of memory. It consists of equal-sized items (or elements) indexed by a contiguous integer starting from 0 (or 1). Figure 1 shows the visual representation of an array consisting of 7 items.

Fig 1: Visual representation of an array

Once we know the address of the starting position of the array, we can calculate the position of $i^{th}$ (index) item in constant time as
$$A_i = A_0 + i * s$$
Where $A_0$ is the address of the starting position of the array (also called address of an array or array address) and $s$ is the size of each item. Suppose an array starts at memory $4000$ and has 30 items with size $4$, the location (or address or position) of 22nd item can be calculated as $4000 + 22*4 = 4088$. If we want to get the item in $i^{th}$ position, we simply calculate its address and read the content of that address. Even if the array has millions of items, the read (and write) operation takes a constant time. All we need to do is calculate the position in memory and we are done.

Operations on array

We can perform read, write, insert and delete operations on an array. If we give a position $i$ in the array, read operation gives the item located at position $i$, write overwrites the content in the memory located at position $i$, insert inserts the new item at position $i$ and delete removes the item located at position $i$. The complexities of all operations are described below.

Read

As described above we can perform the read operation on an array to get the content of any position from first to the last position. This operation takes constant time $O(1)$.

Write

The write operation also takes constant time $O(1)$. Once we know what to write and on what position to write, we can calculate the memory address of that position and write the content.

Insert

Inserting an item to the end of the array takes only a constant time. We calculate the position of the last block of the array and write the item. But if we want to insert the item in the first position, we need to shift all the items one step to the right and then write the item in the first position. If there are $n$ items in the array, inserting an item in the first position requires to move all the items in the one step to the right. If moving one item takes $O(1)$ time then moving $n$ items take $O(n)$ time. In a similar way, if we want to insert an item to the middle of the array, we need $O(n/2) = O(n)$ time. Therefore the worst case complexity of insertion is $O(n)$.

Delete

The delete operation is similar to insert operation in terms of complexity. To remove the item in the last position requires constant time. To remove the item in the first position requires $O(n)$ time. This is because after we remove the item in the first position, we need to move all the items one step to the left to fill the gap. The worst case complexity is, therefore, $O(n)$.

Multi-dimensional array

An array can be more than one dimensional. Even though we can have more than 2 dimensions, we only talk about 2-dimensional array here. The 2-dimensional array has row and column as shown in Figure 2.

Fig 2: Visual representation of 2 dimensional array

Array given in figure 2 has 5 rows and 6 columns. The position of the item in the 2d array can be specified using 2 integers $i$ and $j$ and is denoted by $(i, j)$. $i$ gives the row number and $j$ gives the column number. Once we know the row number, column number and the address of the first block ($(0, 0)$) of the array $A_{00}$, we can find the address of the item located at $(i, j)$ as follows.
$$A_{ij} = A_{00} + i * r + j$$ Where $r$ is the number of rows. As in one-dimensional array, the insertion and deletion operation in the 2D array takes $O(rc)$ ($c$ is a number of columns) time and read and write operation takes $O(1)$ time.

Implementation of array

Almost all programming languages have array implementation and we do not need to worry about implementing it. Please refer to the programs below that show how to declare an array and how to perform array operations in C, C++, and Java.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
      // array declaration and operations
#include <stdio.h>

// prints the array
void print(int a[], int n) {
int i;
for (i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("\n");
}

int main() {
int i;
// declares initializes 1d array of 12 integers
int a[12];

// keeps track of current number of items in the array
int n = 0;

// initialize first 10 items (takes O(n) time)
for (i = 0; i < 10; i++) {
a[i] = i + 1;
n = n + 1;
}

// print and see if it has all 10 items
print(a, n); // prints 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

// read the item in 5th position (position starts from 0)
printf("%d\n", a[5]); // prints 6

// write 12 in first position
a[0] = 12;

// print to see the change
print(a, n); // prints 12, 2, 3, 4, 5, 6, 7, 8, 9, 10

// insert 100 to first position
for (i = n; i >= 0; i--) {
a[i + 1] = a[i]; // move one step to right
}

a[0] = 100; // write 100 in first position
n = n + 1;

// print to verify
print(a, n); // prints 100 12 2 3 4 5 6 7 8 9 10

// remove the item in the first position
for(i = 0; i < n; i++) {
a[i] = a[i + 1];
}

n = n - 1;

// print to verify
print(a, n); // prints 12 2 3 4 5 6 7 8 9 10

return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// array declaration and operations
#include <iostream>

using namespace std;

// prints the array
void print(int a[], int n) {
int i;
for (i = 0; i < n; i++) {
cout<<a[i]<<" ";
}
cout<<endl;
}

int main() {
int i;
// declares initializes 1d array of 12 integers
int a[12];

// keeps track of current number of items in the array
int n = 0;

// initialize first 10 items (takes O(n) time)
for (i = 0; i < 10; i++) {
a[i] = i + 1;
n = n + 1;
}

// print and see if it has all 10 items
print(a, n); // prints 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

// read the item in 5th position (position starts from 0)
cout<<a[5]<<endl; // prints 6

// write 12 in first position
a[0] = 12;

// print to see the change
print(a, n); // prints 12, 2, 3, 4, 5, 6, 7, 8, 9, 10

// insert 100 to first position
for (i = n; i >= 0; i--) {
a[i + 1] = a[i]; // move one step to right
}

a[0] = 100; // write 100 in first position
n = n + 1;

// print to verify
print(a, n); // prints 100 12 2 3 4 5 6 7 8 9 10

// remove the item in the first position
for(i = 0; i < n; i++) {
a[i] = a[i + 1];
}

n = n - 1;

// print to verify
print(a, n); // prints 12 2 3 4 5 6 7 8 9 10

return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
  // array declaration and operations

public class MyArray {
private int [] a;
private int n;

public MyArray() {
a = new int[12];
n = 0;
}

public void initialize() {
for (int i = 0; i < 10; i++) {
a[i] = i+1;
}
n = 10;
}

// print the array
public void print() {
for (int i = 0; i < n; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}

public int get(int i) {
return a[i];
}

public void set(int position, int value) {
a[position] = value;
}

public void insert(int position, int value) {
for (int i = n; i >= position; i--) {
a[i + 1] = a[i];
}
a[position] = value;
n = n + 1;
}

public void delete(int position) {
for(int i = 0; i < n; i++) {
a[i] = a[i + 1];
}
n = n - 1;
}

public static void main(String [] args) {
MyArray arr = new MyArray();

// initialize the array (takes O(n) time)
arr.initialize();

// print to verify
arr.print(); // prints 1 2 3 4 5 6 7 8 9 10

// read the item in 5th position (position starts from 0)
System.out.println(arr.get(5)); // prints 6

// write 12 in first position
arr.set(0, 12); // prints 12 2 3 4 5 6 7 8 9 10

// print to verify
arr.print(); // 12 2 3 4 5 6 7 8 9 10

// insert 100 in first position
arr.insert(0, 100); // 100 12 2 3 4 5 6 7 8 9 10

// print to verify
arr.print();

// remove item in first position
arr.delete(0); // 12 2 3 4 5 6 7 8 9 10

// print to verify
arr.print();
}
}