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

An array is a fundamental data structure that stores a fixed‑size, ordered collection of elements of the same data type. Elements are stored in contiguous memory locations, allowing for efficient random access via an index. Arrays form the building block for many other data structures and are used in almost every area of computer science.

Key Characteristics

• Homogeneous: All elements share the same data type.
• Contiguous Memory: Elements are stored in adjacent memory locations.
• Random Access: Any element can be accessed in O(1) time using its index.
• Fixed Size: In static arrays, the size is determined at compile time; dynamic arrays can resize.

Types of Arrays

Arrays can be classified by their dimensions:

• One‑Dimensional (1D): A linear list of elements (e.g., [1, 2, 3]).
• Two‑Dimensional (2D): A table with rows and columns (e.g., a matrix).
• Multi‑Dimensional: More than two dimensions (e.g., 3D arrays for volumetric data).
• Jagged Arrays: An array of arrays where each inner array can have a different length.

Each type has its own use cases, which are covered in detail in the dedicated pages of this series.

Memory Representation

Because arrays are stored in contiguous memory, we need a mapping between the logical indices and physical memory addresses. Two common schemes are used:

Row‑Major Order

Elements are stored row by row. Used in C, C++, Python (lists), and Java (for rectangular arrays).

Address(arr[i][j]) = base_address + (i * cols + j) * element_size

Example: For a 2D array with 3 rows and 4 columns,
arr[1][2] is at offset (1 * 4 + 2) = 6 elements from the base.

Column‑Major Order

Elements are stored column by column. Used in Fortran, MATLAB, and some numerical libraries.

Address(arr[i][j]) = base_address + (j * rows + i) * element_size

Example: For a 2D array with 3 rows and 4 columns,
arr[1][2] is at offset (2 * 3 + 1) = 7 elements from the base.

Basic Operations on Arrays

1. Traversal

Visiting each element exactly once.

def traverse(arr):
    for i in range(len(arr)):
        print(arr[i], end=" ")

2. Access

Retrieving an element by index — O(1).

value = arr[index]

3. Insertion

Adding an element at a specific position (requires shifting).

def insert(arr, index, value):
    arr.insert(index, value)  # Python list method

4. Deletion

Removing an element (requires shifting).

def delete(arr, index):
    arr.pop(index)  # Python list method

5. Searching

Finding the index of a target value.

• Linear Search: O(n) – works on any array.
• Binary Search: O(log n) – requires a sorted array.

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Sorting Algorithms (Examples)

Several sorting algorithms operate on arrays. Here are two classic ones with code:

Bubble Sort

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

Selection Sort

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

Other sorting algorithms (insertion, merge, quick, etc.) are covered in their dedicated chapters.

Complexity Summary

Applications

• Data Storage: Storing lists of data (e.g., student IDs, product prices).
• Mathematical Operations: Matrices for linear algebra, image processing.
• Buffers and Caches: Temporarily storing data for I/O operations.
• Implementing Other Structures: Stacks, queues, heaps, and hash tables are often built on arrays.
• String Processing: Strings are arrays of characters.
• Dynamic Programming: Storing intermediate results in tables (e.g., knapsack, LCS).

Advantages & Disadvantages

Advantages

• Simple and easy to use.
• Constant‑time random access.
• Cache‑friendly due to contiguous memory.
• Efficient for static collections.

Disadvantages

• Fixed size in many languages (unless using dynamic arrays).
• Insertion and deletion are costly (O(n)).
• All elements must be of the same type.
• Memory may be wasted if the array is not fully utilized.

Examples in Different Languages

Python

# 1D array (list)
arr = [10, 20, 30, 40, 50]

# 2D array (list of lists)
matrix = [[1, 2], [3, 4]]

# Jagged array
jagged = [[1, 2], [3, 4, 5], [6]]

Java

// 1D array
int[] arr = {10, 20, 30, 40, 50};

// 2D array
int[][] matrix = { {1, 2}, {3, 4} };

// Jagged array
int[][] jagged = new int[3][];
jagged[0] = new int[2];
jagged[1] = new int[3];
jagged[2] = new int[1];

C++

// 1D array
int arr[] = {10, 20, 30, 40, 50};

// 2D array
int matrix[2][2] = { {1, 2}, {3, 4} };

// Dynamic 1D array
int* arr = new int[5];

Key Takeaway

Arrays are the most fundamental data structure, providing a simple and efficient way to store and manipulate collections of data. Understanding arrays is essential for mastering more complex data structures and algorithms.