Arrays Explained: The Building Block of Data Storage

Before we get started on what are arrays, let us first understand what data structures are.

Data Structure: It is a way of organizing, storing and managing data in a computer’s memory, so that it can easily be manipulated, maintained and accessed efficiently.

Here the question arises why do we need to manipulate them ? What are they needed for ? Can’t we just store data in computer’s memory simply.

With the advancement in technology, the amount of data that is being generated exponentially. With this comes the complexity of organizing and retrieving data when needed. Data structures help store large amounts of data efficiently, minimizing space and allowing for quick retrieval when needed.

Arrays: An array is a data structure that stores data in a linear, contiguous format. Their size is predefined and cannot be changed. They store same type of data. In this structure, each element can be accessed using an index.

Where can we use arrays ?

1. We can use arrays where we already know the size of data.

2. An Array is helpful when direct access to elements is needed. Accessing elements in array takes O(1) time.

Various operations on arrays :

• Initializing an array : There are various ways an array can be initialized.

  Some of the most common ways are :

    int arr[5] = {1, 2, 3, 4, 5}; // Initialize with specific values
  
    //using loop
    int arr[5];
    for (int i = 0; i < 5; i++) {
        arr[i] = i * 10; // Set each element based on a formula or other condition
    }
  

• Accessing elements in an array : Elements can be accessed very easily in arrays by using indexes whose complexity is O(1).

    int arr[] = {10, 20, 30, 40, 50};
  
    for (int i = 0; i < 5; i++) {
            cout << "Element at index " << i << ": " << arr[i] << endl;
        }
  

• Inserting elements in an array : Inserting elements in array takes O(N) time complexity.

• Searching elements in an array : Searching elements can take O(1) when element is present at the index that has been searched first, it is in the best case. In worst case it can take up to O(N).

  Searching can be done in two ways Linear and Binary Searching.

  • Linear Search : In this, the search space is from 0-th index to last index. Its time complexity is O(N).

      int arr[] = {10, 20, 30, 40, 50};
      int x = 40; //element to search
    
      for(int i = 0; i < 5; i++){
          if(arr[i] == x) return "element found";
      }
      return "not found";
    

  • Binary Search : In this, the search space in each iteration becomes half. Its space complexity is O(log N). For searching an element in an array with binary search array should be in sorted order.

      // Sorted array for binary search
      int arr[] = {10, 20, 30, 40, 50};
      int x = 40; // Element to search
      // Initialize left and right pointers
      int left = 0;
      int right = 4;
      int result = -1; // Variable to store the result
    
      while (left <= right) {
          int mid = left + (right - left) / 2; // Calculate the mid index
              // Check if the element is present at mid
              if (arr[mid] == x) {
                  result = mid; // Element found
                  break; // Exit loop if found
              }
              // If element is greater, ignore the left half
              else if (arr[mid] < x) {
                  left = mid + 1;
              }
              // If element is smaller, ignore the right half
              else {
                  right = mid - 1;
          }
        }
    
          // Output the result
          if (result != -1) {
              cout << "Element found at index: " << result << endl;
          } else {
              cout << "Element not found." << endl;
          }
    
          return 0;
    

    Binary search is faster then linear search.

• Deletion in an array: Deleting an element from an array involves two main steps: locating the element and shifting subsequent elements if necessary.

  • By Index: If the index is known, deletion requires shifting all elements after it one position to the left. This has a time complexity of O(N) for elements at the start or middle, but O(1) if the element is at the end.

  • By Value: If deleting by value, a linear search ( O(N) complexity) is needed to find the element, followed by shifting.

Arrays are one of the simplest yet most powerful data structures. They provide fast access and efficient storage for fixed-size collections of data. Arrays serve as building blocks for more complex structures and algorithms, offering a solid starting point for organizing data.

Though limited by their fixed size and the cost associated with insertions and deletions, arrays are ideal when the size and type of data are known in advance and direct access is required. Understanding arrays and their operations not only helps in effective data management but also forms a strong foundation for learning advanced data structures.