Arrays in Data Structures - Types, Representation & Algorithm (With Examples)

12 Jun 2024
Beginner
8.62K Views
Learn via Video Course & by Doing Hands-on Labs

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 an `Array` 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};
``````

Types of Arrays in Data Structures

There are two types of `array` in Data Structures, which are:

1. Single-dimensional array: It is a collection of elements of the same data type that are stored in a contiguous block of memory.
2. 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 the `index` 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
``````

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
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;
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;
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 in `O(n)` space complexity.

Applications of Arrays in Data Structures

1. 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.
2. 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.
3. Implementing dynamic data structures: It isused to implement dynamic data structures like `stacks`, `queues`, and heaps.
4. 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.
5. 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.
6. 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

1. 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.
2. 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.
3. Flexibility: Arrays are used to implement other data structures like stacks, queues, trees, graphs, etc.
4. 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

1. 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.
2. 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.
3. 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.
4. 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.
5. 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.
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

Q1. What are two types of array in Data Structures?

1. Single-dimensional array
2. Multi-dimensional array

Q2. Which sorting algorithms use arrays?

Different sorting algorithms such as bubble sort, insertion sort, merge sort, and quick sort use arrays.

Q3. How arrays store data?

Arrays store data in contiguous memory locations.
Share Article

Live Classes Schedule

Our learn-by-building-project method enables you to build practical/coding experience that sticks. 95% of our learners say they have confidence and remember more when they learn by building real world projects.
 Generative AI For Software Developers Jul 20 SAT, SUN Filling Fast 08:30PM to 10:30PM (IST) Angular Certification Course Jul 20 SAT, SUN Filling Fast 06:00PM to 08:00PM (IST) Azure Master Class Jul 20 SAT, SUN Filling Fast 03:00PM to 05:00PM (IST) ASP.NET Core Certification Training Jul 28 SAT, SUN Filling Fast 07:00AM to 09:00AM (IST) Software Architecture and Design Training Jul 28 SAT, SUN Filling Fast 05:30PM to 07:30PM (IST) .NET Solution Architect Certification Training Jul 28 SAT, SUN Filling Fast 05:30PM to 07:30PM (IST) Azure Developer Certification Training Jul 28 SAT, SUN Filling Fast 10:00AM to 12:00PM (IST) Advanced Full-Stack .NET Developer Certification Training Jul 28 SAT, SUN Filling Fast 07:00AM to 09:00AM (IST) Data Structures and Algorithms Training with C# Jul 28 SAT, SUN Filling Fast 08:30PM to 10:30PM (IST) Angular Certification Course Aug 11 SAT, SUN Filling Fast 09:30AM to 11:30AM (IST) ASP.NET Core Project Aug 24 SAT, SUN Filling Fast 07:00AM to 09:00AM (IST)

Can't find convenient schedule? Let us know

Similar Articles