Data Structures & Algorithms - Array Data Structure

Share with a Friend

📌 Array Data Structure

1️⃣ What is an Array?

An array is a fixed-size data structure that stores elements of the same data type in contiguous memory locations. Each element in the array is accessed using an index, starting from 0.

✅ Key Features of Arrays:

• Fixed size (static allocation in some languages like C/C++).
• Fast access (O(1)) using an index.
• Elements stored sequentially in memory.
• Efficient for read operations, but insertion and deletion can be costly.

2️⃣ Types of Arrays

1. One-Dimensional Array (1D Array)
• Stores data in a single row or column.
• Example: int arr[5] = {10, 20, 30, 40, 50};
2. Two-Dimensional Array (2D Array)
• A matrix-like structure with rows and columns.
• Example: int matrix[2][3] = {{1, 2, 3}, {4, 5, 6}};
3. Multi-Dimensional Array
• Arrays with more than two dimensions.
• Example: int cube[2][2][2] = {{{1,2},{3,4}},{{5,6},{7,8}}};

3️⃣ Basic Operations on Arrays

1️⃣ Declaration & Initialization

int arr[5] = {10, 20, 30, 40, 50};

int arr[] = {10, 20, 30, 40, 50};

int arr[] = {10, 20, 30, 40, 50};

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

2️⃣ Accessing Elements

Elements in an array are accessed using indexing.

Example:

printf("%d", arr[2]);  // Output: 30

cout << arr[2];  // Output: 30

System.out.println(arr[2]);  // Output: 30

print(arr[2])  # Output: 30

3️⃣ Traversing an Array

We use loops to traverse an array and print its elements.

Example:

#include <stdio.h>

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int n = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

10 20 30 40 50

#include <iostream>
using namespace std;

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    for (int i = 0; i < 5; i++)
        cout << arr[i] << " ";
    return 0;
}

10 20 30 40 50

class Test {
    public static void main(String[] args) {
        int arr[] = {10, 20, 30, 40, 50};
        for (int num : arr)
            System.out.print(num + " ");
    }
}

10 20 30 40 50

arr = [10, 20, 30, 40, 50]
for num in arr:
    print(num, end=" ")

10 20 30 40 50

4️⃣ Insertion in an Array

Inserting an element at a specific position requires shifting elements.

C Language:

#include <stdio.h>

void insertElement(int arr[], int *n, int element, int pos) {
    for (int i = *n; i > pos; i--)
        arr[i] = arr[i - 1];
    arr[pos] = element;
    (*n)++;
}

int main() {
    int arr[10] = {10, 20, 30, 40, 50}, n = 5;
    insertElement(arr, &n, 25, 2);
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    return 0;
}

✅ Output:

10 20 25 30 40 50

5️⃣ Deletion in an Array

Deleting an element requires shifting elements.

C Language:

#include <stdio.h>

void deleteElement(int arr[], int *n, int pos) {
    for (int i = pos; i < (*n) - 1; i++)
        arr[i] = arr[i + 1];
    (*n)--;
}

int main() {
    int arr[5] = {10, 20, 30, 40, 50}, n = 5;
    deleteElement(arr, &n, 2);
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    return 0;
}

✅ Output:

10 20 40 50

6️⃣ Searching in an Array

Linear Search (O(n))

def linear_search(arr, key):
    for i in range(len(arr)):
        if arr[i] == key:
            return i
    return -1
arr = [10, 20, 30, 40, 50]
print(linear_search(arr, 30))  # Output: 2

✅ Output:

2

Binary Search (O(log n))

Python

def binary_search(arr, key):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == key:
            return mid
        elif arr[mid] < key:
            left = mid + 1
        else:
            right = mid - 1
    return -1
arr = [10, 20, 30, 40, 50]
print(binary_search(arr, 30))  # Output: 2

✅ Output:

2

 

4️⃣ Time Complexity of Array Operations

5️⃣ Advantages & Disadvantages of Arrays

✅ Advantages:

• Fast access (O(1)) if index is known.
• Efficient for fixed-size data storage.
• Simple implementation.

❌ Disadvantages:

• Fixed size (cannot grow dynamically in C/C++).
• Insertion & deletion are costly (O(n) in worst case).
• Memory wastage (if allocated size is larger than needed).

6️⃣ Real-Life Applications of Arrays

✅ Used in:
✔ Image processing (2D arrays for pixels).
✔ Database indexing.
✔ Scheduling algorithms (CPU scheduling).
✔ Pathfinding algorithms (A* algorithm).
✔ Implementing other data structures (stack, queue, heap).

Conclusion

• Arrays are simple and efficient for data storage and retrieval.
• However, they are static and have costly insertion/deletion operations.
• Linked Lists are often used when dynamic memory is required.