What is an Array in Data Structures? Key Concepts, Types, and Operations

Arrays are a fundamental data structure, storing a collection of elements in contiguous memory, which allows for fast random access to elements. However, their fixed size can limit flexibility, requiring careful memory allocation during design. 

Arrays form the foundation for many data structures (e.g., stacks, queues) and algorithms, serving as a baseline for tasks like sorting and searching. 

In this blog, we’ll dive into the key concepts of array in data structure, their types, and the common operations performed on them. 

What is Array in Data Structure? Basics, Types, and Applications?

An array is a data structure that stores a collection of data items (called elements) of the same type, such as contact numbers of customers visiting a store. This structured layout ensures that each element can be stored, accessed, and updated using a unique index starting from 0. 

Accessing elements by their index is particularly efficient, with a time complexity of O(1), making arrays ideal for scenarios requiring quick lookups or updates. The number of elements in an array is denoted by its array length.

For example, if VMart decides to offer a 10% discount to customers who visited the store last month, they can access relevant data. Similarly, in weather monitoring systems, arrays are used to store hourly temperature readings for quick analysis.

Basic Concept of Arrays:

• Arrays store multiple elements in a single variable.
• Elements are stored in a continuous block of memory.
• The size of an array is determined at the time of its declaration.
• Each element is accessed using an index (position), which makes it easier to retrieve values directly.
• Arrays can store data types like integers, strings, floats, or objects, depending on the array's specification, However, All elements must belong to the same data type, such as integers, characters, or floats.

Explanation of Contiguous Memory Allocation

In contiguous memory allocation, when a process requests memory, the operating system assigns it a single block of memory that is adjacent in physical memory. This approach can be implemented using either fixed-size or variable-size partitions:

• Fixed-size Partitioning: The memory is divided into fixed-sized blocks, with each block assigned to a single process. This method simplifies management but can lead to internal fragmentation if the allocated block is larger than the process needs.
• Variable-size Partitioning: Memory is allocated based on the specific requirements of the process, allowing for more efficient use of space but complicating management due to the need for tracking free and occupied blocks.

Common Use Cases of Arrays

Arrays are widely used in various domains because of their versatility and efficiency. Here are some common use cases of array in data structure:

• Storing Grades: In institutions, arrays are often used to store student grades. For example, a teacher might use an array to keep track of scores for a class: grades = [85, 90, 78, 92, 88]. 
• Managing Weekly Schedules: Arrays can represent fixed sets of items like days of the week. 

For example, a weekly planner might use an array to store tasks for each day: weekdays = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday"]. This makes it easy to iterate through the days and assign tasks accordingly.

• Image Processing: In graphics applications, images are often represented as two-dimensional arrays of pixels. Each pixel's color can be stored in an array, allowing for operations like filtering or resizing images. 

For example, a simple image might be represented as image[][] = [[255, 0, 0], [0, 255, 0], [0, 0, 255]], where each sub-array corresponds to a row of pixels.

• Caching Data: Web applications frequently utilize arrays to cache data for quick retrieval. For instance, an e-commerce site might store recently viewed products in an array to display them on the homepage: recentlyViewed = ["Product1", "Product2", "Product3"]. This enhances user experience by reducing load times.
• Statistical Analysis: Arrays facilitate statistical computations by storing datasets. For instance, if you have an array of temperatures recorded over a week: temperatures = [30.5, 31.2, 29.8, 32.1], you can easily calculate the mean or standard deviation using built-in functions.

Fixed Size, Homogeneous Elements, and Contiguous Memory Allocation

Arrays have a fixed size, meaning the number of elements is defined at creation and cannot be changed during runtime. They store homogeneous elements in contiguous memory locations, allowing random access through indexing.

• Fixed Size: When you declare an array, its size is typically set during initialization and cannot change during runtime (in most languages like C or Java). This means you have to specify how many elements the array will hold upfront. For example, int Students [25];
• Homogeneous Elements: All elements in an array must be of the same type. For example, you can have an array of integers or an array of strings, but you can't mix data types within the same array. This uniformity helps ensure consistency and makes accessing the data more efficient.
• Contiguous Memory Allocation: Arrays are stored in a single, continuous block of memory. This means that the data in an array is laid out sequentially in memory, which provides a significant performance advantage when accessing elements. The address of each element can be calculated quickly by knowing the starting memory address and the size of each element.

Comparison with Linked Lists

Arrays and linked lists are both used to store collections of data but how they differ to each other are as follows: 

Also Read: Array in Data Structure - Explanation, Function & Examples

Basics of Array in Data Structures

Arrays enable efficient random access to elements via their index, making them ideal for tasks requiring quick lookups or updates. 

Static Arrays

A static array is an array where the size is defined at the time of creation and cannot be changed during runtime. The memory for static arrays is allocated once, and its size is fixed for the entire duration of the program.

• Fixed Size: The size of the array is determined at compile time or when the array is created, and cannot be modified.
• Contiguous Memory Allocation: All elements are stored next to each other in a continuous block of memory, which leads to efficient access.
• Efficient Access: Since elements are stored contiguously, accessing an element by its index is O(1) (constant time).
• Low Overhead: No extra memory overhead for managing the array’s size or structure.

Potential Limitations:

• Wasted Space: If the declared size is larger than needed, memory may be wasted.
• Inflexibility: If more space is required than initially allocated, resizing is not possible, which can lead to inefficiency in dynamic scenarios.

Examples of When and Where Static Arrays are Used:

• Embedded Systems: Where memory resources are limited, static arrays are often used to store data that will not change in size.
• Low-Level Programming (e.g., C/C++): Static arrays are used in situations where you know the exact number of elements at compile time (e.g., storing a fixed-size matrix or a collection of items).
• Mathematical and Scientific Computations: Fixed-size arrays are used to represent vectors or matrices, where the size is predetermined.

Also Read: Creating a Dynamic Array in Java

Dynamic Arrays

Dynamic arrays are arrays that allow for resizing during runtime. Unlike static arrays, dynamic arrays can grow or shrink based on the needs of the program, which makes them more flexible and useful in scenarios where the number of elements is not known in advance.

• Resizable: Dynamic arrays can adjust their size dynamically as elements are added or removed, overcoming the fixed-size limitation of static arrays.
• Efficient Memory Use: As elements are added, the array may need to reallocate memory, typically doubling its size when it runs out of space. However, this resizing comes with an overhead, as reallocation involves copying all existing elements to a new memory location, making it an O(n) operation when resizing occurs.
• Amortized Constant Time for Insertions: While resizing can take O(n) time, the cost is distributed across multiple insertions, resulting in an amortized O(1) time complexity for most insertions.
• Memory Overhead: Dynamic arrays require additional memory to accommodate potential resizing, making them slightly less memory-efficient compared to static arrays.

Dynamic Array Libraries or Structures:

• ArrayList in Java: The ArrayList class in Java is a dynamic array implementation. It allows elements to be added or removed, and the underlying array automatically resizes when more space is needed.
• Vector in C++: Similar to ArrayList, Vector in C++ is a dynamic array that can grow and shrink as required. It manages memory automatically and provides random access to elements, just like static arrays.
• Python Lists: In Python, the list data structure is implemented as a dynamic array. As elements are added, the list resizes itself to accommodate new elements.

Dynamic arrays are widely used in modern programming languages due to their flexibility and ease of use, particularly when the exact size of data is unknown at the time of writing the program. Despite the slight memory overhead and occasional resizing cost, they provide the best of both worlds: the speed of array indexing and the flexibility of resizing.

Also Read: Dynamic Array Creation in C Language

Now that we’ve grasped the fundamentals, let’s dive deeper into the different types of arrays and how they vary in functionality.

What are the Different Types of Array in Data Structures?

Arrays efficiently store data in memory. One-dimensional arrays manage simple lists, multi-dimensional arrays handle grids (e.g., matrices, images), and jagged arrays excel in managing irregular datasets or hierarchical structures.

Let’s start by exploring one of the simplest and most commonly used types of array in data structures, One-Dimensional Arrays.

One-Dimensional Arrays

One-dimensional arrays are the simplest type of array where elements are arranged in a single line. This means that all the elements are indexed sequentially, starting from index 0.

• Example:

  Array of student marks.

int marks []= {85, 90, 76, 88, 92}

        List of numbers.

int num [] ={5, 12, 7, 20}

Here, each element in the array is accessed using a single index (e.g., array[0] for the first element).

• Uses:
  • Storing linear data such as student marks, inventory items, or a sequence of numbers.
  • Storing simple data where no relational structure is needed between elements.

Visual Example of One-Dimensional Array:

Two-Dimensional Arrays

A two-dimensional array is an array of arrays, where each element is itself an array. It can be thought of as a grid or table with rows and columns.

• Example:

Matrix:
  [1, 2, 3] 
  [4, 5, 6]
  [7, 8, 9]

• Uses:
  • Matrices for mathematical computations.
  • Image representation (where each pixel is stored in a grid format).
  • Tables for storing data in rows and columns (e.g., spreadsheet-like data).

Visual Example of Two-Dimensional Array:

Multi-Dimensional Arrays

A multi-dimensional array is an extension of two-dimensional arrays, where you can have three or more dimensions. These arrays are useful when working with complex data that has multiple layers or axes.

Example: A 3D array could be a cube of values:

int arr[2][2][2] = { { { 5, 2 }, { 7, 1 } },
                         { { 3, 6 }, { 11, 21 } } };

Explanation:

• This 3D array represents a 2x2x2 cube structure.
• The first dimension (arr[0] or arr[1]) represents two layers.
• Each layer contains 2 rows and 2 columns.

Use Cases:

• Scientific computations involving large data sets like 3D simulations.
• Multi-layered data such as geographic data (latitude, longitude, altitude) or RGB color data for images.

Multi-dimensional arrays allow you to organize and access large, complex data in a structured manner.

Visual Example of Multi-Dimensional Array:

Also Read: Multidimensional Array in PHP [With Examples]

Jagged Arrays

A jagged array is an array of arrays where each "inner array" can have a different length. Unlike a two-dimensional array, which has a consistent number of columns in every row, jagged arrays can have rows with varying numbers of elements.

• Example:

[
  [1, 2, 3],
  [4, 5],
  [6, 7, 8, 9]
]

• Uses:
  • Storing data with rows of different lengths, such as when data from different categories is stored.
  • Flexible storage for irregular or sparse data, such as ragged data from different regions or groups.

Visual Example of Jagged Array:

If you are interested in learning more about arrays and data structures, then check out this free upGrad course on Data Structures and Algorithms!

Having covered the various array types, it’s crucial to understand how memory is allocated for arrays to optimize their performance.

Memory Allocation of an Array in Data Structure

Arrays are a fundamental data structure in computer science, and their memory allocation plays a crucial role in their efficiency and performance. The memory allocation of arrays can differ significantly between static arrays and dynamic arrays.

Memory Allocation Differences Between Static and Dynamic Arrays:

• Static Arrays:
  • Fixed Size: Memory is allocated for a static array at compile time based on the defined size.
  • Contiguous Memory: All elements of the array are stored in contiguous memory locations, meaning each element is placed next to the other in memory.
  • No Resizing: The size of the array cannot change during runtime. If the size is exceeded, the program may run into errors or need to handle resizing manually (though static arrays cannot be resized).
  • Efficient Memory Use: Since the size is predefined, the memory is reserved ahead of time, ensuring no runtime overhead.
• Dynamic Arrays:
  • Resizable: Memory is allocated at runtime, allowing for resizing of the array. As elements are added, the array grows dynamically, typically by doubling in size.
  • Contiguous Memory (Initially): Similar to static arrays, elements are initially stored in contiguous memory locations, but as resizing occurs, a new, larger block of memory may be allocated, and elements from the old block are copied to the new block.
  • Overhead for Resizing: Dynamic arrays typically incur overhead when resizing. This can affect performance, especially if resizing happens frequently.

How to Declare an Array in Data Structure?

Arrays in different programming languages have specific syntaxes for declaration. Here's how you can declare arrays in various languages:

1. C/C++:

Arrays in C or C++, are declared by specifying the type, followed by the array name and the number of elements.

int array[5];  // Declares an array of 5 integers

Also Read: Top 7 Most Powerful Features of C++ You Should Know About

2. Java:

Arrays in Java are declared using the type, followed by square brackets.

int[] array = new int[5];  // Declares an array of 5 integers

3. Python:

In Python, arrays are usually represented by lists. Python doesn't require you to specify the number of elements at the time of declaration.

array = [1, 2, 3, 4, 5]  # A list with 5 elements

4. JavaScript:

JavaScript arrays are dynamic and can hold elements of any type. You declare them using square brackets.

let array = [1, 2, 3, 4, 5];  // Declares an array of 5 elements

How to Access an Element from an Array?

Array elements are accessed by their index, which starts from 0 for the first element. The formula to calculate the address of an array element is:

address_of_element = base_address + (index * size_of_element)

Where:

• base_address is the memory address of the first element.
• index is the position of the element in the array (starting from 0).
• size_of_element is the size of one element in the array.

Example in C:

#include <iostream>
using namespace std;

int main() {
    int array[5] = {1, 2, 3, 4, 5};
    cout << "Element at index 2: " << array[2] << endl;  // Accessing the 3rd element (index 2)
    return 0;
}

Output:

Element at index 2: 3

In this example, array[2] accesses the third element of the array (value 3), as array indexing starts from 0.

How to Initialize an Array in Data Structure?

Arrays can be initialized either at the time of declaration or later during program execution. In most cases, values are assigned to an array using index-based access.

Example of Initializing an Array During Declaration (C/C++):

int array[5] = {1, 2, 3, 4, 5};  // Initialize array with values at declaration

Example of Index-Based Initialization (JavaScript):

let array = [];
array[0] = 1;
array[1] = 2;
array[2] = 3;
array[3] = 4;
array[4] = 5;  // Initialize array with values using index-based access

Example in Python (List Initialization):

array = [1, 2, 3, 4, 5]  # Initialize list with values at the time of declaration

Also Read: The Ultimate C++ Guide: C++ Tutorials for Beginners

With memory allocation clarified, let's move on to understanding the essential operations performed on arrays and their time complexities.

upGrad’s Exclusive Data Science Webinar for you –

Watch our Webinar on How to Build Digital & Data Mindset?

Array in Data Structure: Essential Operations and Their Complexities

Arrays are fundamental data structures that provide efficient ways to store and manipulate collections of data. There are several key operations performed on arrays to manage and access the data. These operations are essential for tasks like adding new elements, deleting existing ones, searching for specific values, and updating data.

The common operations on arrays include:

• Traversal: Visiting each element in the array.
• Insertion: Adding an element to the array.
• Deletion: Removing an element from the array.
• Search: Finding an element in the array.
• Update: Modifying the value of an element.

Traversal

Traversal refers to visiting every element in the array. It’s often the first step when performing operations like searching or updating an array, as it allows us to access each element in sequence.

Code Example:

#include <iostream>
using namespace std;

int main() {
    int array[5] = {1, 2, 3, 4, 5};
    
    // Traversing the array
    for(int i = 0; i < 5; i++) {
        cout << "Element at index " << i << ": " << array[i] << endl;
    }
    
    return 0;
}

Output:

Element at index 0: 1
Element at index 1: 2
Element at index 2: 3
Element at index 3: 4
Element at index 4: 5

In the above code, we use a loop to visit and print each element in the array, starting from index 0 to 4.

Insertion

Insertion involves adding a new element to the array. It can be done at:

• The end of the array (commonly done in dynamic arrays).
• A specific index in the array, which may require shifting elements to maintain contiguous memory.

Code Example (Inserting at the End):

#include <iostream>
using namespace std;

int main() {
    int array[6] = {1, 2, 3, 4, 5};
    int size = 5;
    int new_element = 6;
    
    // Insertion at the end
    array[size] = new_element;
    size++;
    
    // Traversing after insertion
    for(int i = 0; i < size; i++) {
        cout << array[i] << " ";
    }
    
    return 0;
}

Output:

1 2 3 4 5 6

Here, we insert the new element 6 at the end of the array and then print the array.

Deletion

Deletion removes an element from the array. In dynamic arrays or static arrays, deletion requires shifting the subsequent elements to fill the gap left by the deleted element.

Code Example (Deleting an Element):

#include <iostream>
using namespace std;

int main() {
    int array[5] = {1, 2, 3, 4, 5};
    int size = 5;
    int index_to_delete = 2;  // Deleting element at index 2 (value 3)
    
    // Deletion: Shift elements left
    for(int i = index_to_delete; i < size - 1; i++) {
        array[i] = array[i + 1];
    }
    size--;  // Decrease the size of the array
    
    // Traversing after deletion
    for(int i = 0; i < size; i++) {
        cout << array[i] << " ";
    }
    
    return 0;
}

Output:

1 2 4 5

In this example, after deleting the element at index 2, the elements to the right of it are shifted left.

Search

Search is used to find the index of an element in the array. If the element is found, the index is returned; otherwise, a signal (like -1 or null) is returned to indicate the element is not present.

Code Example (Linear Search):

#include <iostream>
using namespace std;

int main() {
    int array[5] = {1, 2, 3, 4, 5};
    int size = 5;
    int target = 3;
    int index = -1;  // Initializing index to -1, assuming element not found
    
    // Linear search
    for(int i = 0; i < size; i++) {
        if(array[i] == target) {
            index = i;
            break;
        }
    }
    
    cout << "Element " << target << " found at index: " << index << endl;
    
    return 0;
}

Output:

Element 3 found at index: 2

Here, we perform a linear search to find the element 3 and return its index (2).

Update

Explanation: Update modifies the value of an existing element in the array. You access the element using its index and assign a new value to it.

Code Example (Updating an Element):

#include <iostream>
using namespace std;

int main() {
    int array[5] = {1, 2, 3, 4, 5};
    int index_to_update = 2;
    int new_value = 10;
    
    // Update the element at index 2
    array[index_to_update] = new_value;
    
    // Traversing after update
    for(int i = 0; i < 5; i++) {
        cout << array[i] << " ";
    }
    
    return 0;
}

Output:

1 2 10 4 5

In this example, the element at index 2 is updated to 10, and the updated array is printed.To casual please frame a better CTA

Also Read: Array in Java: What You Need To Know?

Complexity of Array Operations

Each operation on an array comes with its own time and space complexity. Below is an analysis of the time complexities for common array operations:

• Traversal:
  • Time Complexity: O(n)
  • Explanation: We visit each element in the array once, making the time proportional to the size of the array.
• Insertion:
  • At the end (in dynamic arrays):
    • Time Complexity: O(1) (amortized)
    • Explanation: Inserting at the end of the array is constant time unless the array needs resizing.
  • At a specific index:
    • Time Complexity: O(n)
    • Explanation: Insertion at a specific index requires shifting elements to the right, so the time grows linearly with the number of elements.
• Deletion:
  • Time Complexity: O(n)
  • Explanation: Deletion requires shifting all elements after the deleted element to the left to maintain the contiguous memory layout, so the operation is linear in time.
• Search (Linear Search):
  • Time Complexity: O(n)
  • Explanation: In the worst case, we may have to check each element once, making the search time proportional to the size of the array.
• Update:
  • Time Complexity: O(1)
  • Explanation: Accessing an element by its index is constant time, so updating an element is also constant time.

Also Read: How to Convert Object to Array in PHP

Now that we’ve analyzed the operations, it’s important to evaluate the advantages and disadvantages of using arrays in data structures.

Advantages and Disadvantages of Array in Data Structure

Array in data structure that offers efficient storage and quick access to elements through indexing. However, their fixed size and the need for shifting elements during insertions or deletions can limit flexibility and performance.

Here are some of the advantages:

Here are some of the disadvantages of arrays:

Also Read: Python Array vs. List: Difference Between Array and List in Python: Key Insights

After understanding the advantages and disadvantages of arrays, let’s see how platforms like upGrad can help you leverage these concepts to advance your career.

How upGrad Can Help You Advance Your Career in Data Structures?

Understanding array in data structures and learning programming language is a crucial step in becoming a proficient full stack developer, and upGrad offers a range of programs to help you achieve this.

The courses combine hands-on training, real-world projects, and personalized mentorship to help you advance your career and gain in-demand skills.

Here are some relevant courses you can check out:

• Data Structure and Algorithms Certificate Free Course
• Best Full Stack Developer Bootcamp
• Java Object-oriented Programming
• JavaScript Basics from Scratch

Enroll now and start mastering array in data structure and other web development skills with upGrad. Get personalized counseling from upGrad’s experts or visit the nearest upGrad Career Centre to chart your path to success!

Unlock the power of data with our popular Data Science courses, designed to make you proficient in analytics, machine learning, and big data!

Explore our Popular Data Science Courses

Elevate your career by learning essential Data Science skills such as statistical modeling, big data processing, predictive analytics, and SQL!

Top Data Science Skills to Learn

Stay informed and inspired  with our popular Data Science articles, offering expert insights, trends, and practical tips for aspiring data professionals!

Read our popular Data Science Articles