Introduction to Arrays in Data Structure
An array is a type of data structure used to store homogeneous data in contiguous memory locations. This implements the idea to store the various items to be retrieved or accessed at one go.
Here index refers to the location of an element in the array. Let’s imagine if P[L] is the name of the array where ‘P’ is the variable name, and ‘L’ is the length of the array, i.e. the number of elements present in the array. Then P[i] represents the element at that ‘i+1’the position in the array.
For Example:
P[6]= 72 means element at 6+1th location of the array.
Need of Array: It helps to represent a large number of elements using a single variable. It also makes accessing of element faster easy to store in memory location using the array index that represents the location of the element in the array.
How do Arrays work in Data Structure?
An array stores the variables at contiguous locations and gives them a particular index. When someone wants to fetch the data, the person uses this index. In the above-given array ‘P’, say base address for array = 100 then elements are stored as below:
Memory allocated to an array can be calculated as:
- One Dimensional Array: Total memory allocated to an Array = Number of elements * size of one element.For example: In the above case, memory = 7 * (size of an int)
- Row Major Order: Total memory allocated to 2D Array = Number of elements * size of one element
= Number of Rows * Number of Columns * Size of one element - Column Major Order: Total memory allocated to 2D Array = Number of elements * size of one element
= Number of Rows * Number of Columns * Size of one element
How to Define Arrays?
Thus Array can be defined as a derived data structure to store homogeneous data of primitive datatype at contiguous memory locations. Below are the operations that can be performed on arrays:
1. Insertion: This refers to inserting an element in the array at a particular index. This can be performed with O(n) complexity.
2. Deletion: This refers to deleting an item at a particular index. This operation requires shifting of elements after deletion thus takes O(n) complexity.
3. Searching: This refers to accessing an item at a particular index of an array.
4. Traversing: It refers to printing all the elements of an array one after another.
Properties of Arrays in Data Structure
Below are the properties of arrays in Data Structure:
- It is a derived data type, compose of a collection of various primitive data types such as int, char, float, etc.
- Elements of an array are stored in contiguous blocks in primary memory.
- The name of the array stores the base address of the array. It acts as a pointer to the memory block where the first element has been stored.
- Array indices start from 0 to N-1 in case of single dimension array where n represents the number of elements in an array.
- Elements of the array can only be composed of constants and literal values.
How to Create Arrays?
We can create Arrays using the below syntax:
1. Dimensional Array: <datatype> var = {c1,c2,c3,…….cn}
Here var refers to the variable to array that stores the base location of the array. And c1,c2… are elements of the array.
Example: int a = {4,6,7,8,9}
Length of the array = n
2. Multi Dimensional array: <datatype> var = {{r01,…r0n},{r10,…..r1n}…..{rm0….rmn}}
Here var refers to the name of the array of m rows and n columns.
How to Access Arrays Element?
Indexes of an array start from 0 till -1.0, which indicates the first element of the array and -1 indicates the last element of the array. Similarly, -2 indicates the last but one element of the array. Let’s say, and there is an array ‘A’ having 10 elements. Then, a variable stores the reference of the first variable of the array, which is called ‘Base Address’ of an array. After this, if someone wants to access the array element, then the address of that element is calculated using the below formula.
Address of ith element = Base Address + i * size of each element
Here, each element’s size refers to the memory taken by various primitive data types that array is holding. E.g., int takes 2 bytes of space and float takes 4 bytes of space in C.
Accessing Multi-Dimensional Array
Let’s say A[rl,……..,ru][cu,……, cl] is a multidimensional array and rl, ru, cu, cl are lower and upper bounds rows and columns. The number of rows in A, say NR = ru – rl +1 and Number of columns in A, say NC = cl – cu +1.
Now to find the address of an element in the array, there are 2 methods:
1. Row Major: Where we traverse row by row.
Address of A[i][j] = Base Address +((i – rl )*NC + (j- cl) * size of each element.
2. Column Major: Where we traverse column by column.
Address of A[i][j] = Base Address +((i – rl) + (j- cl) *NR) * size of each element.
Complexity: Accessing any element in an array is much easier and can be done in O(1) complexity.
Conclusion
Arrays are a unique way to structure the stored data such that it can be easily accessed and can be queried to fetch the value at a particular number using the index value. Although inserting an element into an array takes much time, it needs complete rearrangement and shifting of existing elements. It is still used to implement various other complex data structures such as tree, queue or stack and used in various algorithms.
Recommended Articles
This is a guide to Arrays in Data Structure. Here we discuss the basic concept of creating and accessing Array elements in Data Structure and properties. You can also go through our other related articles to learn more –
