Arrays in Data Structure (Examples, Uses, Types, More)

Introduction

Arrays are like shelves in a library where each book is placed side by side in a specific order. Just as
you can quickly find a book on a shelf by knowing its position, in programming, arrays let you
efficiently access and manage data by its index.

This simple yet powerful data structure is fundamental in DSA and programming, helping organize
data much like books in a library.

From keeping track of high scores in a video game to managing information in a user database, data
structure arrays help in performing several tasks.

Hence, let’s learn everything about arrays in data structures.

What is Array in Data Structure?

An array is a basic data structure used to store a fixed-size collection of elements of the same type.
These elements are arranged in contiguous memory locations, allowing each element to be indexed
or accessed directly using an integer index.

Array in data structure

Data structure arrays are essential because they form the basis for many other data structures, such
as stacks, queues, and array-based lists.

They also serve as the underlying mechanism for implementing algorithms that solve a variety of
problems, from sorting and searching data to handling matrices in computational applications

Examples of Arrays

Let’s understand the meaning of data structure array with a real-life example:

Consider an everyday task like organizing your music playlist. Each song in the playlist can be thought
of as an element in an array, where the position of the song (its index) helps you quickly locate and
play it without the need to search through the entire list.

Now, let’s understand arrays with examples in different programming languages, considering an
array of integers representing the ages of students in a classroom:

Characteristics of Arrays in Data Structures

Fixed Size: Once an array is declared, its size cannot be changed. You need to know the number of
elements you will store in the array beforehand.

Homogeneous Elements: All elements in an array must be of the same data type, such as all integers,
all floats, or all characters.

Indexed by Integers: Each element in an array is assigned a unique integer called an index, which
identifies its position within the array. Indexing usually starts at 0.
Efficient Access: Because of the way arrays are stored in memory (contiguously), accessing any
element by its index is very efficient. This direct access using the index is often referred to as
"random access."

Basics of Array in Data Structures

1. Static Arrays

A static array has a fixed size, which means the number of elements it can hold is defined when the
array is declared and cannot be changed during runtime.

The memory for a static array is allocated at compile time, and the allocated memory is a contiguous
block that remains allocated for the entire lifetime of the array.

Example:

int numbers[5]; // Declares a static array of integers with 5 elements

In this example, an integer array called numbers is created with space for 5 elements. You must
know in advance how many elements the array will hold, and this number cannot change later.

2. Dynamic Arrays

Dynamic arrays can change size during runtime, allowing more flexibility than static arrays.

They are particularly useful when the number of elements is not known in advance. Dynamic arrays
are implemented using pointers, and memory for them is allocated at runtime from the heap, which
allows them to expand or contract as needed.

Example:

int* numbers = malloc(5 * sizeof(int)); // Allocates memory for 5 integers dynamically

Here, numbers is a pointer to an integer array. Initially, it points to a memory block sufficient for 5
integers. If more space is needed, the array can be resized using realloc(), and if less space is needed,
it can be reduced in size or deallocated using free().

3. Memory Allocation of Arrays

Memory allocation for arrays depends on whether they are static or dynamic:

Static Arrays: Memory is allocated on the stack. The allocation is done at compile time, and the size
is fixed.

Dynamic Arrays: Memory is allocated on the heap. The allocation is done at runtime, and the size
can be adjusted using memory management functions like malloc, realloc, and free in languages like
C and C++.

Example of Dynamic Array Usage:

Consider a social media app that needs to store a user’s posts. Since the number of posts a user can
make isn’t fixed, a dynamic array allows the app to allocate more space as users add more posts,
ensuring that the data structure adapts to the user's behavior dynamically.

Uses of Array in Data Structure

Arrays in data structures are used across various domains for efficient data management and
manipulation:

Data Storage: Arrays provide a compact way of storing elements of the same type. They are
commonly used for storing data like user records, inventory details, and other sequential data.

Implementation of Matrices: In mathematical and scientific computations, two-dimensional arrays

are used to represent matrices which are crucial in operations such as transformations in graphics,
solving systems of linear equations, and statistical analyses.

Handling Buffer Data: Arrays are used in programming to manage buffer storages, which are
essential for the temporary storage of data during the transfer between two places in a system, such
as reading files or handling I/O streams.

Lookup Tables and Reverse Lookups: Arrays can be used to create fast access lookup tables, allowing
for efficient data retrieval. They are especially useful in applications where frequent retrieval of
information based on a key is required.

Implementation of Other Data Structures: Arrays serve as the underlying data structure for more
complex structures like heaps, stacks, queues, and graphs, used in more complicated algorithms.

Sorting and Searching Algorithms: Arrays in DSA are used to implement various sorting algorithms,
such as quicksort, mergesort, and heapsort, due to their ease of element manipulation and access.

Memory Management: In lower-level programming, arrays play a crucial role in memory

management schemes, helping manage resources effectively in a compact format.

Image Representation: In computer graphics, images are stored as arrays of pixels where each pixel
represents a color. Manipulations and effects applied to images are often performed via operations
on these arrays.

Handling Static Datasets: Arrays are ideal for applications where the data size is known and does not
change over time, allowing for efficient access and manipulation.

Game Development: Arrays are used extensively in game development for storing game states, grid
layouts for board games, sprite information in animations, and much more.

Types of Arrays in Data Structure

Below are the different types of arrays in data structures:

1. One-Dimensional Arrays (1D Arrays)

These are the simplest form of arrays, consisting of a single line of elements. Each element in a 1D
array is accessed by a single index representing its position within the array.

One-dimensional arrays

Use: One-dimensional arrays are commonly used to store lists of items, such as scores or sensor
readings, where each item can be accessed by a single index.

Real-Life Example:

A small shop could use a 1D array to keep track of the quantity of each product in stock. Each index
in the array represents a different product, and the value at that index represents the current stock
level.

Example:

Let’s imagine an array that stores the temperature readings for a week.

temperatures = [68, 70, 72, 66, 64, 68, 71] # temperatures for seven days

print(temperatures[2]) # Access the temperature of the third day

This prints 72, which is the temperature on the third day.

2. Two-Dimensional Arrays (2D Arrays)

A two-dimensional array in data structure, often thought of as a matrix, consists of rows and
columns. It is used to represent data in a grid format and is accessed by two indices: one for the row
and another for the column.

Two-dimensional array in data structure

Use: They are extensively used in applications that simulate a real-world environment onto a grid or
need a matrix setup, such as digital spreadsheets, board games, and scientific data that are laid out
in rows and columns.

Example:

Representing a chess board where each cell can hold information about whether it is occupied.

chess_board = [[0, 1, 0, 1, 0, 1, 0, 1], # 0 for empty, 1 for occupied

[1, 0, 1, 0, 1, 0, 1, 0],

[0, 1, 0, 1, 0, 1, 0, 1],
 ... # and so on for each row

print(chess_board[0][1]) # Accesses the second cell in the first row

This returns 1, indicating the cell is occupied.

Real-Life Example:

A theater's seating arrangement can be managed using a 2D array. Each row of the array could
represent a different row of seats, and each column a seat in that row, with the values indicating
whether a seat is empty or booked.

3. Multi-Dimensional Arrays

These are the arrays with more than two dimensions. The multi-dimensional arrays in data
structures can be used in scenarios requiring complex data representation.

Multi-dimensional arrays in data structures

For example, in three-dimensional graphics, where coordinates are stored in 3D space, or in

applications managing multi-dimensional data sets.

Example:

Storing data for a 3D tic-tac-toe game.

# A 3x3x3 3D tic-tac-toe board, where 0 means no move, 1 is player 1, and 2 is player 2

tic_tac_toe_3d = [[[0 for _ in range(3)] for _ in range(3)] for _ in range(3)]

tic_tac_toe_3d[0][0][0] = 1 # Player 1 places on the first cell in the top layer

Real-Life Example:

Climate scientists can use a three-dimensional array to simulate temperature, humidity, and wind
speed across different points in a geographic area at various altitudes.

weather_data = [[[20, 75, 10], [22, 80, 12]], # layer 1

 [[18, 65, 8], [16, 60, 7]], # layer 2

...]

Three-dimensional graphics

Different Array Operations

Arrays support a variety of operations that allow for the manipulation and interaction with the data
they hold:

1. Access Elements in Array

Accessing an element in an array includes retrieving the value stored at a specific index. This is one
of the most basic operations and is generally performed in constant time, O(1).

Example:

Access the third element in an array of integers.

elements = [10, 20, 30, 40, 50]

third_element = elements[2] # Arrays are zero-indexed

print(third_element) # Outputs 30

2. Insert Element in Array

Inserting an element involves adding the element at a given position in the array.

This can require shifting elements to the right to make room for the new element, especially in static
arrays, which makes it a potentially costly operation, O(n) in the worst case.

Example:

Insert the value 25 at the third position in an array.

elements = [10, 20, 30, 40, 50]

elements.insert(2, 25) # Insert 25 at index 2

print(elements) # Outputs [10, 20, 25, 30, 40, 50]

3. Delete an Element From Array

Deleting an element from an array includes removing the element at a given index. Like insertion,
this operation may require shifting elements to fill the space left by the removed element, which can
also be O(n) in the worst case.

Example:

Remove the third element from the array.

elements = [10, 20, 30, 40, 50]

del elements[2] # Delete the element at index 2

print(elements) # Outputs [10, 20, 40, 50]

4. Search for an Element in Array

Searching for an element in an array can be done either sequentially or via a more efficient method
like binary search if the array is sorted. The time complexity is O(n) for sequential search and O(log
n) for binary search.

Example:

Find an element in an unsorted array using sequential search.

elements = [10, 20, 30, 40, 50]

target = 30

for index, element in enumerate(elements):

if element == target:

print(f"Element found at index {index}") # Outputs index 2

break

5. Update Value of Existing Element in Array

Updating refers to changing the value of an existing element in the array at a specific index. This is a
simple and quick operation, usually done in O(1) time.

Example:

Update the third element in the array to 35.

elements = [10, 20, 30, 40, 50]

elements[2] = 35 # Update the element at index 2

print(elements) # Outputs [10, 20, 35, 40, 50]

6. Sort Array Elements

Sorting rearranges the elements in an array according to a particular order (ascending or

descending). The time complexity can vary based on the sorting algorithm used, typically ranging
from O(n log n) to O(n^2).

Example:

Sort an array of integers in ascending order.

elements = [50, 20, 40, 10, 30]

elements.sort()

print(elements) # Outputs [10, 20, 30, 40, 50]

Complexity of Array Operations

Operation

Time Complexity

Access

O(1)

Search

O(n)

Insertion

O(n)

Deletion
O(n)

Updating

O(1)

Sorting

O(n log n)

Advantages of Arrays in DSA

Following are the benefits of using arrays in data structures and algorithms:

Random Access: Arrays provide constant time access to any element, as each element can be
accessed directly using its index.

Efficiency: Storing elements contiguously in memory makes arrays very memory-efficient and
optimizes performance.

Simplicity: Arrays have a simple and straightforward structure, making them easy to understand and
implement.

Basis for Other Structures: Arrays serve as the foundational building block for constructing other
complex data structures like heaps, hash tables, stacks, and queues.

Good for Fixed-Size Collections: When the size of the dataset is known and not expected to change,
arrays are an excellent choice due to their static nature.

Performance in Iterative Processes: Due to their contiguous memory allocation, arrays allow fast
iteration over elements, making them ideal for loops and algorithmic processing.

Cache-Friendliness: The contiguous allocation of memory makes arrays cache-friendly, enhancing

performance by reducing cache misses during operations that access array elements sequentially.

Ease of Manipulation: Basic operations like sorting and searching are well-understood and easily
implemented on arrays, benefiting from direct element access.

Predictable Memory Allocation: Memory for arrays is allocated at the time of array creation, which
simplifies memory management in environments with limited resources or where performance
predictability is critical.

Disadvantages (Limitations) of Arrays in DSA

While arrays are widely used and offer many benefits, they also have some inherent disadvantages
or limitations that can impact their suitability for certain applications:
Fixed Size: Once an array is declared, its size cannot be changed. This static nature can lead to
inefficiencies, such as wasted memory if the array is not fully utilized or insufficient capacity if more
space is needed.

Costly Insertions and Deletions: Adding or removing elements from an array, especially in the
middle, is costly because it requires shifting elements to maintain the order. This operation has a
time complexity of O(n), making it inefficient for large datasets.

Single Data Type: Standard arrays are homogeneous, meaning all elements must be of the same data
type. This can limit their use in applications requiring a heterogeneous collection of data.

Overhead with Low-Level Management in Some Languages: In languages like C and C++, managing
arrays involves more low-level operations, which can increase the complexity of the code and the
potential for bugs, such as buffer overflows.