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.
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.
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 | // array declaration and operations |
1 | // array declaration and operations |
1 | // array declaration and operations |