Basic Operations of array data structure

• Traversal: Access elements in the array one by one.
• Insertion: Add an element at the given index.
• Deletion: Delete an element at the given index.
• Search: Search for an element in the array using the given index or value.
• Update: Updates an element on a given position (index).
• Sorting: Arrange elements in increasing or decreasing order.
• Merging: Merge sorted arrays into a larger sorted array.

Traversal

Traversal in an array means visiting each element of the array one by one. This means you are traversing through the elements of the array one after the other.

Complexity:

• Time Complexity: O(n) - Traversing an array takes linear time, where ‘n’ is the number of elements in the array. This is because you only need to visit each element once.
• Space Complexity: O(1) - Traversal does not require any additional data structures or memory beyond a few variables for looping.

#include <iostream>
using namespace std;

void arrayTraversal(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << endl;
    }
}

int main() {
    int myArray[] = {1, 2, 3, 4, 5};
    int size = sizeof(myArray) / sizeof(myArray[0]);
    arrayTraversal(myArray, size);
    return 0;
}

Insertion

At the Beginning (Shift Elements):

Inserting an element at the beginning of static array requires shifting all existing elements to the right. This operation has a time complexity of O(n) because, in the worst case, you have to shift all ‘n’ existing elements.

#include <iostream>
using namespace std;

// Inserting at the beginning of the array.
void insertAtBeginning(int arr[], int n, int element) {
  if (n == sizeof(arr) / sizeof(arr[0])) {
    return; // Array is full.
  }
  for (int i = n; i > 0; i--) {
    arr[i] = arr[i - 1];
  }
  arr[0] = element;
  n++;
}

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    int n = 5;
    
    insertAtBeginning(arr, n, 0); // Adds 0 to the beginning of the array.

	for(int i = 0; i < n; i++){
		cout << arr[i]<< endl;
	}
    
    return 0;
}

// Output
0
1
2
3
4

Insertion at the End

This is the simplest scenario, as we do not need to shift any elements. This time complexity is O(1).

#include <iostream>
using namespace std;

// Inserting at the end of the array.
void insertAtEnd(int arr[], int n, int element) {
  if (n == sizeof(arr) / sizeof(arr[0])) {
    return; // Array is full.
  }
  arr[n] = element;
  n++;
}

int main() {
  int arr[5] = {1, 2, 3, 4, 5};
  int n = 5;

  insertAtEnd(arr, n, 6); // Adds 6 to the end of the array.


  for (int i = 0; i < n; i++) {
    cout << arr[i] << endl;
  }


  return 0;
}

// Output
1
2
3
4
5

Insertion at an arbitrary index

This scenario takes O(n) time, as we need to shift all the elements from the insertion index to the end of the array.

#include <iostream>
using namespace std;

// Inserting at an arbitrary index in the array.
void insertAtIndex(int arr[], int n, int element, int index) {
  if (index < 0 || index > n || n == sizeof(arr) / sizeof(arr[0])) {
    return; // Index is out of bounds or array is full.
  }
  for (int i = n; i > index; i--) {
    arr[i] = arr[i - 1];
  }
  arr[index] = element;
  n++;
}

int main() {
  int arr[5] = {1, 2, 3, 4, 5};
  int n = 5;

  insertAtIndex(arr, n, 7, 2); // Inserts 7 at index 2.

  for (int i = 0; i < n; i++) {
    cout << arr[i] << endl;
  }


  return 0;
}

//Output
1
2
7
3
4

Deletion

Deleting an element in a static array by removing the element and then moving all the subsequent elements one position to the left to fill the gap.

Time Complexity: The time complexity of deleting an element in a static array by shifting elements is O(n), where n is the number of elements in the array. This is because, in the worst case, you may need to shift all elements after the deletion point.

Space Complexity: The space complexity of deleting an element in a static array by shifting elements is O(1), which means it requires the constant amount of additional memory space.

#include <iostream>

const int MAX_SIZE = 100; // Maximum size of the static array

void deleteElement(int arr[], int& size, int indexToDelete) {
    if (indexToDelete >= 0 && indexToDelete < size) {
        // Shift elements to the left to fill the gap
        for (int i = indexToDelete; i < size - 1; i++) {
            arr[i] = arr[i + 1];
        }
        // Decrement the size of the array
        size--;
    }
}

int main() {
    int arr[MAX_SIZE];
    int size = 5; // Initial size of the array

    // Initializing the array with some values
    for (int i = 0; i < size; i++) {
        arr[i] = i * 10;
    }

    // Displaying the original array
    std::cout << "Original Array:" << std::endl;
    for (int i = 0; i < size; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    // Deleting an element at index 2 by shifting elements
    int indexToDelete = 2;
    deleteElement(arr, size, indexToDelete);

    // Displaying the array after deletion
    std::cout << "Array after deletion:" << std::endl;
    for (int i = 0; i < size; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

Output

Original Array:
0 10 20 30 40 
Array after deletion:
0 10 30 40 

Searching

Searching in data structure refers to the process of finding the required information from a collection of items stored as elements in the computer memory. Searching for an element in a static array can be done using various algorithms.

1. Linear Search

Linear search is a simple search algorithm that checks every element in the array one by one until it finds the target element or reaches the end of the array. It is suitable for unsorted arrays.

Time Complexity of Linear Search: O(n) - In the worst case, where the target element is at the end of the array or not present at all, you might have to iterate through all n elements.

#include <iostream>

const int MAX_SIZE = 100; // Maximum size of the static array

int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i; // Return the index where the target element is found
        }
    }
    return -1; // Return -1 if the target element is not found in the array
}

int main() {
    int arr[MAX_SIZE];
    int size = 5; // Initial size of the array

    // Initializing the array with some values
    for (int i = 0; i < size; i++) {
        arr[i] = i * 10;
    }

    // Displaying the original array
    std::cout << "Original Array:" << std::endl;
    for (int i = 0; i < size; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    int target = 30; // Element to search for
    int index = linearSearch(arr, size, target);

    if (index != -1) {
        std::cout << "Element " << target << " found at index " << index << std::endl;
    } else {
        std::cout << "Element " << target << " not found in the array." << std::endl;
    }

    return 0;
}

// Output
Original Array:
0 10 20 30 40 
Element 30 found at index 3

2. Binary Search

Binary search is an efficient search algorithm for sorted arrays. It repeatedly divides the search interval in half, reducing the search space by half each time. It compares the middle element with the target and eliminates half of the remaining elements based on the comparison result.

Time Complexity of Binary Search: O(log(n)) - Binary search repeatedly halves the search interval, making it much more efficient than linear search, especially for large arrays.

Note: Binary search only works on sorted arrays, so the array must be sorted before applying binary search.

#include <iostream>

const int MAX_SIZE = 100; // Maximum size of the static array

int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid; // Return the index where the target element is found
        }

        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1; // Return -1 if the target element is not found in the array
}

int main() {
    int arr[MAX_SIZE];
    int size = 10; // Initial size of the array (must be sorted)

    // Initializing the sorted array with some values
    for (int i = 0; i < size; i++) {
        arr[i] = i * 5;
    }

    // Displaying the original sorted array
    std::cout << "Original Sorted Array:" << std::endl;
    for (int i = 0; i < size; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    int target = 20; // Element to search for
    int index = binarySearch(arr, 0, size - 1, target);

    if (index != -1) {
        std::cout << "Element " << target << " found at index " << index << std::endl;
    } else {
        std::cout << "Element " << target << " not found in the array." << std::endl;
    }

    return 0;
}

// Output
Original Sorted Array:
0 5 10 15 20 25 30 35 40 45 
Element 20 found at index 4