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

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

20 Feb 2024
Beginner
3.39K Views
46 min read
Learn via Video Course & by Doing Hands-on Labs

Data Structures & Algorithms For Beginners Free Course

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};
    

Representation of Arrays in Data Structures

Read more: Arrays in Java

Types of Arrays in Data Structures

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

Read More - Best Data Structure Interview Questions and Answers

Basic Operations on Arrays in Data Structures

  1. 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    

  1. 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 

  1. 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  

  1. 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 

  1. 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
    OperationBest CaseAverage CaseWorst 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.
Accept cookies & close this