Array Data Structures: Linear, Multidimensional, and Sparse

Posted on Jun 11, 2026 in Computers

Introduction to Arrays

An Array is a fundamental, linear data structure that stores a collection of elements of the same data type in contiguous (adjacent) memory locations.

Instead of declaring separate variables for twenty different integers, you declare a single array variable and access each individual element using an index (a numerical position offset).

Linear Arrays

A Linear Array (or one-dimensional array) is a list of a finite number of homogeneous data elements such that:

• The elements of the array are referenced respectively by an index set consisting of consecutive integers.
• The elements are stored in successive memory locations.

The length or total number of elements in a linear array can be calculated using its index bounds:

Length = UB – LB + 1

Where UB is the Upper Bound (maximum index) and LB is the Lower Bound (starting index, usually 0 in modern languages like C++ and Python, or 1 in languages like Fortran).

Memory Representation of Linear Arrays

Because elements are stored contiguously, the computer’s compiler doesn’t track the address of every single item. Instead, it tracks only the address of the very first element, known as the Base Address (Base).

To find the address of any element at index k, the computer uses a simple address calculation formula:

Address(A[k]) = Base + w(k – LB)

Where w is the width (size in bytes) of each data type element (e.g., 4 bytes for a standard integer).

Two-Dimensional and Multidimensional Arrays

When data requires organization in rows and columns (like a table or grid), a Two-Dimensional Array (2D Array) is used. A 3D array adds a third dimension (like depth, useful for coordinates or RGB image layers), and any array beyond that is considered a Multidimensional Array.

2D Array Memory Mapping

Computer memory is inherently linear (one-dimensional). To store a 2D grid in linear memory, the computer must flatten it using one of two techniques:

Matrix Layout:
[A, B]
[C, D]

Row-Major (Flattened):    [ A, B, C, D ]
Column-Major (Flattened): [ A, C, B, D ]

1. Row-Major Order (RMO)

Elements are stored row by row. All elements of the first row are stored sequentially, followed by all elements of the second row, and so on.

Address(A[i][j]) = Base + w[N(i – LB1) + (j – LB2)]

(Where N is the total number of columns, LB1 is the lower bound of rows, and LB2 is the lower bound of columns)

2. Column-Major Order (CMO)

Elements are stored column by column. All elements of the first column come first, followed by the second column, etc.

Address(A[i][j]) = Base + w[(i – LB1) + M(j – LB2)]

(Where M is the total number of rows)

Sparse Matrix Representation

A matrix is considered a Sparse Matrix when a significant majority of its elements are zero. Storing a large sparse matrix in a standard 2D array wastes an immense amount of memory.

Standard 2D Sparse Matrix:
[ 0  0  7  0 ]
[ 0  0  0  0 ]
[ 3  0  0  0 ]

To optimize space, we compress the matrix by storing only the non-zero elements.

3-Tuple Representation

The matrix is converted into an N x 3 array where each row contains three attributes: [Row Index, Column Index, Value]. Row 0 is typically reserved for the metadata: [Total Rows, Total Columns, Total Non-Zero Elements].

Array Operations and Algorithms

Here are the algorithmic logic steps and clean, standard implementations for core array operations.

1. Traversal

Visiting every element of the array exactly once to process or display it.

Algorithm

1. Set Initial Index to LB.
2. Repeat Steps 3 and 4 while Index <= UB.
3. Apply processing/print to Array[Index].
4. Increase Index by 1.
5. Exit.

Code Implementation

void traverse(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

Time Complexity: O(n)
Space Complexity: O(1)

2. Selection and Searching

Finding the location of an element with a given value (Linear Search variant).

Algorithm

1. Set Index to LB, set Location to -1.
2. Repeat while Index <= UB:
   • if Array[Index] == Item:
     • Location = Index
     • Break
   • Index = Index + 1
3. If Location == -1: Print “Item not found”
4. Else: Return Location

Code Implementation

int select_item(int arr[], int size, int item) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == item) {
            return i; // Item found at index i
        }
    }
    return -1; // Item not found
}

Time Complexity: O(n) worst case, O(1) best case.
Space Complexity: O(1)

3. Insertion

Adding a new element into the array at a specific index. This requires shifting all subsequent elements down by one position to make room.

Algorithm

1. Initialize Counter = Size – 1.
2. Repeat while Counter >= Target_Index:
   • Array[Counter + 1] = Array[Counter] (Shift element right)
   • Counter = Counter – 1
3. Array[Target_Index] = New_Item
4. Increase Size by 1.

Code Implementation

bool insert_at(int arr[], int& size, int capacity, int item, int index) {
    if (size >= capacity || index < 0 || index > size) {
        return false; // Out of bounds or array full
    }
    for (int i = size - 1; i >= index; i--) {
        arr[i + 1] = arr[i];
    }
    arr[index] = item;
    size++; // Update active size
    return true;
}

Time Complexity: O(n) (Since shifting elements is required).
Space Complexity: O(1)

4. Deletion

Removing an element from a specific index. This requires shifting all subsequent elements up by one position to close the empty gap.

Algorithm

1. Set Deleted_Item = Array[Target_Index].
2. Initialize Counter = Target_Index.
3. Repeat while Counter < Size – 1:
   • Array[Counter] = Array[Counter + 1] (Shift element left)
   • Counter = Counter + 1
4. Decrease Size by 1.

Code Implementation

bool delete_at(int arr[], int& size, int index) {
    if (index < 0 || index >= size) {
        return false; // Invalid index
    }
    for (int i = index; i < size - 1; i++) {
        arr[i] = arr[i + 1];
    }
    size--; // Update active size
    return true;
}

Time Complexity: O(n) (Due to element shifting).
Space Complexity: O(1)