Mastering Array Fundamentals: Implementing basic array operations in Java

Photo by Florian Olivo on Unsplash

Array is a data structure in which elements of the same data types are stored at contiguous memory locations. In this post I will show the implementation and time complexity of basic array operations: Search, Insert, and Delete. For a comprehensive comparison of time complexity data structures operations, please refer to my post Algorithm Analysis Cheat Sheet.

Table of contents:

· Search
∘ Unsorted Array
∘ Sorted Array
· Insert
∘ Fixed size array
· Delete

Search

Unsorted Array

Linear search is particularly useful to traverse unsorted arrays. It operates by sequentially examining each element of the array until the element with the desired value is found or the entire array has been traversed.

• Time complexity: O(n)

public int search(int[] arr, int arr_size, int val) {
  for (int i = 0; i < arr_size; i++) {
    if arr[i] == val
      return i; // index of the value in the array
  }  
  return -1; // value cannot be found
}

Sorted Array