Previous Tutorial
21
NovArrays in Data Structures - Types, Representation & Algorithm (With Examples)
12 Jun 2024
Beginner
16.3K Views
48 min read
Arrays in Data Structures: An Overview
You might have already come across arrays while learning arrays in C and arrays in C++. We even saw in the first tutorial, Data Structures and its Types that anArray is a type of non-primitive, linear, and static data structure. It is a collection of elements of the same type.In this DSA tutorial, we will see the array data structure in detail i.e. its features, working, implementation, etc. To further enhance your understanding and application of array concepts, consider enrolling in the best Data Structures and Algorithms Course, where you can gain comprehensive insights into effective data structure utilization for improved problem-solving and time management.
What is an Array in Data Structures?
An array is a powerful data structure that allows users to store and manipulate a collection of elements, all of the same data type in a single variable. Simply, it is a collection of elements of the same data type stored at contagious memory locations that can be randomly accessed with their index number. It’s one of the most popular and simple data structures and is often used to implement other data structures like stacks and queues.Representation of Arrays in Data Structures
The representation of an array can be defined by its declaration. A declaration means allocating memory for an array of a given size.We can declare and initialize arrays in various ways in different programming languages.
import array
# Example:
arr = array.array('i', [1, 2, 5, 6])
// declare an array
dataType[] arrayName;
// or
dataType[] arrayName = {elements};
// example
int[] arr = {1, 2, 5, 6};
dataType arrayName[arraySize];
// example
int arr[4];
int arr[4] = {1, 2, 5, 6};
Read more: Arrays in Java
Types of Arrays in Data Structures
There are two types of array in Data Structures, which are:
- Single-dimensional array: It is a collection of elements of the same data type that are stored in a contiguous block of memory.
- Multi-dimensional array: It is an array that contains one or more arrays as its elements. We will see this in the next section Types of Arrays in Data Structures.
In this tutorial, we will cover all the aspects of a Single dimensional array
How to Access Elements of an Array in Data Structures?
To access the array elements, use theindex number of the required element. The array index starts with 0. The index of the last element is n-1.
class ArrayExample:
def __init__(self):
# declaring the array of type int and size 4
self.a = [1, 2, 5, 6]
# declaring the array of type char and size 3
self.b = ['a', 'b', 'c']
# declaring the array of type float and size 5
self.c = [0.2, 0.7, 0.8, 0.21, 0.9]
def display_elements(self):
# accessing the 2nd element of array a
print(self.a[1])
# accessing the elements of array b
for i in range(3):
print(self.b[i])
# accessing the 3rd element of array c
print(self.c[2])
# Create an instance of the ArrayExample class and display elements
array_example = ArrayExample()
array_example.display_elements()
public class ArrayExample {
public static void main(String[] args) {
// declaring the array of type int and size 4
int[] a = {1, 2, 5, 6};
// declaring the array of type char and size 3
char[] b = {'a', 'b', 'c'};
// declaring the array of type float and size 5
float[] c = {0.2f, 0.7f, 0.8f, 0.21f, 0.9f};
// accessing the 2nd element of array a
System.out.println(a[1]);
// accessing the elements of array b
for (int i = 0; i < 3; i++) {
System.out.println(b[i]);
}
// accessing the 3rd element of array c
System.out.println(c[2]);
}
}
#include <iostream>
int main() {
// declaring the array of type int and size 4
int a[4] = {1, 2, 5, 6};
// declaring the array of type char and size 3
char b[3] = {'a', 'b', 'c'};
// declaring the array of type float and size 5
float c[5] = {0.2, 0.7, 0.8, 0.21, 0.9};
// accessing the 2nd element of array a
std::cout << a[1] << std::endl;
// accessing the elements of array b
for (int i = 0; i < 3; i++) {
std::cout << b[i] << std::endl;
}
// accessing the 3rd element of array c
std::cout << c[2] << std::endl;
return 0;
}
Output
2
a
b
c
0.8
Read More - Best Data Structure Interview Questions and Answers
Basic Operations on Arrays in Data Structures
- Traversal
This operation is used to traverse or move through the elements of the array.
fruits = ["Apple", "Mango", "Banana", "Orange", "Grapes"]
for fruit in fruits:
print(fruit)
public class ArrayExample {
public static void main(String[] args) {
String[] fruits = {"Apple", "Mango", "Banana", "Orange", "Grapes"};
for (int i = 0; i < 5; i++) {
System.out.println(fruits[i]);
}
}
}
#include <iostream>
#include <string>
using namespace std;
int main() {
string fruits[5] = {"Apple", "Mango", "Banana", "Orange", "Grapes"};
for (int i = 0; i < 5; i++) {
cout << fruits[i] << '\n';
}
return 0;
}
Output
Apple Mango Banana Orange Grapes
- Insertion
We can insert one or multiple elements in an array as per the requirement at the required positions or indexes.
def main():
chairs = [1, 2, 3, 4, 5]
balls = [5, 2, 8, 5, 7, -1]
# array size
n = 5
# index of element to be added
pos = 2
# element to be added
item = 4
# incrementing the size of the array by 1
n = n + 1
# adjusting the value of loop counter to the last index
j = n - 2
# traversing balls[] from last
while j >= pos:
# copying the element to the incremented block
balls[j + 1] = balls[j]
j = j - 1
# copying the element to the vacated position
balls[pos] = item
print("The chairs and the corresponding number of balls after adding a ball:")
for i in range(n):
print(" ", i + 1, "\t", balls[i])
if __name__ == "__main__":
main()
public class BallInsertion {
public static void main(String[] args) {
int[] chairs = {1, 2, 3, 4, 5};
int[] balls = {5, 2, 8, 5, 7, -1};
// array size
int n = 5;
// index of element to be added
int pos = 2;
// element to be added
int item = 4;
// incrementing the size of the array by 1
n = n + 1;
// adjusting the value of loop counter to the last index
int j = n - 2;
// traversing balls[] from last
while (j >= pos) {
// copying the element to the incremented block
balls[j + 1] = balls[j];
j = j - 1;
}
// copying the element to the vacated position
balls[pos] = item;
System.out.println("The chairs and the corresponding number of balls after adding a ball:");
for (int i = 0; i < n; i++) {
System.out.println(" " + (i + 1) + "\t " + balls[i]);
}
}
}
#include <iostream>
int main() {
int chairs[] = {1, 2, 3, 4, 5};
int balls[] = {5, 2, 8, 5, 7, -1};
// array size
int n = 5;
// index of element to be added
int pos = 2;
// element to be added
int item = 4;
// incrementing the size of the array by 1
n = n + 1;
// adjusting the value of loop counter to the last index
int j = n - 2;
// traversing balls[] from last
while (j >= pos) {
// copying the element to the incremented block
balls[j + 1] = balls[j];
j = j - 1;
}
// copying the element to the vacated position
balls[pos] = item;
std::cout << "The chairs and the corresponding number of balls after adding a ball:\n";
for (int i = 0; i < n; i++) {
std::cout << " " << i + 1 << "\t " << balls[i] << "\n";
}
return 0;
}
Output
1 5
2 2
3 4
4 8
5 5
6 7 - Deletion
It is used to delete an element from a particular index in an array.
balls = [5, 2, 8, 5, 7]
# array size
n = 5
# index of element to be deleted
pos = 2
# adjusting the value of loop counter to pos
j = pos
while j < n:
balls[j - 1] = balls[j]
j = j + 1
# decrementing the size of the array by 1
n = n - 1
print("\nThe chairs and the corresponding number of balls after removing a ball")
for i in range(n):
print(" " + str(i + 1) + "\t " + str(balls[i]))
public class Main {
public static void main(String[] args) {
int[] balls = {5, 2, 8, 5, 7};
// array size
int n = 5;
// index of element to be deleted
int pos = 2;
// adjusting the value of loop counter to pos
int j = pos;
while (j < n) {
balls[j - 1] = balls[j];
j = j + 1;
}
// decrementing the size of the array by 1
n = n - 1;
System.out.println("\nThe chairs and the corresponding number of balls after removing a ball");
for (int i = 0; i < n; i++) {
System.out.println(" " + (i + 1) + "\t " + balls[i]);
}
}
}
#include <iostream>
int main() {
int balls[] = {5, 2, 8, 5, 7};
// array size
int n = 5;
// index of element to be deleted
int pos = 2;
// adjusting the value of loop counter to pos
int j = pos;
while (j < n) {
balls[j - 1] = balls[j];
j = j + 1;
}
// decrementing the size of the array by 1
n = n - 1;
std::cout << "\nThe chairs and the corresponding number of balls after removing a ball";
for (int i = 0; i < n; i++) {
std::cout << " " << i + 1 << "\t " << balls[i] << "\n";
}
return 0;
}
Output
The chairs and the corresponding number of balls after removing a ball
1 5
2 8
3 5
4 7 - Search
It is used to search an element using the given index or by the value. We can search any element in an array and display both, its index and value.
balls = [5, 4, 8, 5, 7]
# array size
n = 5
# element to be searched
order = 4
j = 0
while j < n:
if balls[j] == order:
break
j = j + 1
print("The corresponding chair number of order:", order, " is ->", j + 1)
public class Main {
public static void main(String[] args) {
int[] balls = {5, 4, 8, 5, 7};
// array size
int n = 5;
// element to be searched
int order = 4;
int j = 0;
while (j < n) {
if (balls[j] == order)
break;
j = j + 1;
}
System.out.println("The corresponding chair number of order:" + order + " is -> " + (j + 1));
}
}
#include <iostream>
int main() {
int balls[] = {5, 4, 8, 5, 7};
// array size
int n = 5;
// element to be searched
int order = 4;
int j = 0;
while (j < n) {
if (balls[j] == order)
break;
j = j + 1;
}
std::cout << "The corresponding chair number of order:" << order << " is -> " << j + 1 << std::endl;
return 0;
}
Output
The corresponding chair number of order:4 is -> 2 - Update
We can change the values of the elements inside an array at any position or index.
no_of_students = [5, 6, 7, 2, 4, 8, 3]
# array size
n = 7
# index of the element to be updated
pos = 3
# updated number
item = 0
print("The number of students sitting on the benches in order: ")
for i in range(n):
print(no_of_students[i])
print("Bench numbers and the corresponding number of students sitting on each bench")
for i in range(n):
print(f" {i + 1}\t {no_of_students[i]}")
no_of_students[pos] = item
print("\nStudent Numbers and the updated no of Students on each bench after the 1st update")
for i in range(n):
print(f" {i + 1}\t {no_of_students[i]}")
public class BenchUpdate {
public static void main(String[] args) {
int[] noOfStudents = {5, 6, 7, 2, 4, 8, 3};
// array size
int n = 7;
// index of the element to be updated
int pos = 3;
// updated number
int item = 0;
System.out.println("The number of students sitting on the benches in order: ");
for (int i = 0; i < n; i++) {
System.out.println(noOfStudents[i]);
}
System.out.println("Bench numbers and the corresponding number of students sitting on each bench");
for (int i = 0; i < n; i++) {
System.out.println(" " + (i + 1) + "\t " + noOfStudents[i]);
}
noOfStudents[pos] = item;
System.out.println("\nStudent Numbers and the updated no of Students on each bench after the 1st update");
for (int i = 0; i < n; i++) {
System.out.println(" " + (i + 1) + "\t " + noOfStudents[i]);
}
}
}
#include
int main() {
int noOfStudents[7]={5, 6, 7, 2, 4, 8, 3};
// array size
int n = 7;
// index of the element to be updated
int pos = 3;
// updated number
int item = 0;
std::cout << "The number of students sitting on the benches in order: \n";
for (int i = 0; i < n; i++) {
std::cout << noOfStudents[i] << "\n";
}
std::cout << "Bench numbers and the corresponding number of students sitting on each bench\n";
for (int i = 0; i < n; i++) {
std::cout << " " << i + 1 << "\t " << noOfStudents[i] << "\n";
}
noOfStudents[pos] = item;
std::cout << "\nStudent Numbers and updated no of Students on each bench after the 1st update\n";
for (int i = 0; i < n; i++) {
std::cout << " " << i + 1 << "\t " << noOfStudents[i] << "\n";
}
return 0;
}
Output
The number of students sitting on the benches in order:
5
6
7
2
4
8
3
Bench numbers and the corresponding number of students sitting on each bench
1 5
2 6
3 7
4 2
5 4
6 8
7 3
Student Numbers and the updated no of Students on each bench after the 1st update
1 5
2 6
3 7
4 0
5 4
6 8
7 3 Complexity Analysis of Operations on Arrays
- Time Complexity
Operation Best Case Average Case Worst Case Traversal O(1)O(n)O(n)Insertion O(1)O(n)O(n)Deletion O(1)O(n)O(n)Search O(1)O(n)O(n)Update O(1)O(1)O(1) - Space Complexity: Most of the operations on arrays have a space complexity of
O(1), except for resizing operations and certain insertions/deletions that may require shifting elements, resulting inO(n)space complexity.
Applications of Arrays in Data Structures
- Storing and accessing data: Arrays are often used to store data that can be accessed quickly and efficiently. For example, an array can be used to store the scores of students in a class or the prices of products in a store.
- Sorting and searching data: It is easier to sort and search data in an array using the index. It is used for different sorting algorithms such as bubble sort, insertion sort, merge sort, and quick sort.
- Implementing dynamic data structures: It isused to implement dynamic data structures like
stacks,queues, and heaps. - Image processing: Arrays can be used to represent and process images. Each element in the array represents a pixel in the image, and operations can be performed on the array to manipulate the image.
- Numerical computations: The application of an array is extensive in numerical computations, such as in linear algebra and signal processing. For example, a matrix can be represented as a two-dimensional array, and operations like matrix multiplication can be performed efficiently using arrays.
- Games and simulations: Arrays can be used to represent game boards, game pieces, and game states. They are also used in simulations to store and manipulate data over time.
Advantages of Arrays in Data Structures
- Efficient access: Arrays offer fast and efficient access to elements because each element can be accessed directly through its index. This makes array traversal quick and straightforward.
- Versatility: Arrays can be used to store any type of data like integers, characters, and strings. They can also be used to store user-defined data types, such as structures and classes.
- Flexibility: Arrays are used to implement other data structures like stacks, queues, trees, graphs, etc.
- Easy to remember: Arrays represent multiple data items of the same type using a single name. Therefore it’s easier to remember an array name than remembering the names of several variables.
Disadvantages of Arrays in Data Structures
- Fixed-size: The size of an array is fixed at the time of its creation, which means that once the array is created, its size cannot be changed. This can be a limitation in situations where the size of the data is not known in advance.
- Memory wastage: There will be a wastage of memory if we store less number of elements than the declared size because there is static memory allocation in arrays.
- Inefficient insertion and deletion: Arrays store data in contiguous memory locations, which makes deletion and insertion very difficult to implement. All the elements after insertion or deletion must be shifted to accommodate the new element or fill in the gap. This can be a time-consuming process, especially for large arrays.
- Homogeneous data: Arrays can only store elements of the same data type, which can be a limitation in situations where the user needs to store data of different types.
- No built-in support for dynamic resizing: While some programming languages provide built-in support for dynamic resizing of arrays, many do not. In those cases, the developer may have to implement their own resizing logic, which can be complex and error-prone.
| >>> Read More:- Differences Between Array and Linked List |
Summary
So, here we saw every aspect of arrays in data structures. As you are already familiar with arrays, it might not have become difficult to understand the above-discussed concepts. You might have got a broad idea regarding arrays and their applications. I know it's quite difficult to understand the implementation of array operations in a single go. Therefore, refer to it again and again till you get thorough with the arrays in data structures. To test your knowledge of arrays, enroll in our Best Dsa Course.FAQs
- Single-dimensional array
- Multi-dimensional array
Different sorting algorithms such as bubble sort, insertion sort, merge sort, and quick sort use arrays.
Arrays store data in contiguous memory locations.