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. Because elements are stored in a continuous block, each item can be directly identified and accessed using a numerical index, typically starting at 0.

Key Characteristics

Homogeneous Elements

Every item in the array must be of the identical data type, meaning each element occupies the exact same number of bytes in memory.

Contiguous Allocation

Elements are physically arranged right next to each other in the system memory (RAM).

Fixed Size

Standard (static) arrays require their total size to be defined at the time of creation, and this total capacity cannot be dynamically changed later.

Advantages and Limitations

Advantages

Fast Access

Instant \(O(1)\) random access to any element via its index.

Cache Friendly

Contiguous memory layout maximizes the system’s spatial locality of reference.

Low Overhead

Requires no extra memory tracking pointers like linked lists do.

Limitations

Fixed Size

Can result in wasted space if over-allocated, or running out of room if under-allocated.

Costly Modifications

Inserting or deleting elements from the middle is slow due to heavy element shifting.

Memory Fragmentation

Requires one large, unbroken chunk of memory, which might be blocked even if total free RAM exists.

Time Complexities

The structure of an array makes looking up specific locations incredibly fast, while modifying the structure itself remains highly inefficient.

Access (by index): \(O(1)\)

Constant time.

Search (by value): \(O(n)\)

Linear time for unsorted arrays, or \(O(log n)\) for sorted arrays using binary search.

Insertion: \(O(n)\)

Linear time; inserting an item in the middle requires shifting all subsequent elements down.

Deletion: \(O(n)\)

Linear time; moving an item requires shifting all remaining elements up to fill the gap.

Visualization

Source: Study Algorithms

Implementation

C++Python

#include <iostream>
#include <vector>

void insert(int array[], int *size, int index, int value) {
  // Shift elements to the right
  for (int i = *size; index < i; i--) {
    array[i] = array[i - 1];
  }

  // Insert new element
  array[index] = value;

  // Increase active element count;
  (*size)++;
}

void remove(int array[], int *size, int index) {
  if (index < 0 || *size <= index) return;

  // Shift elements to the left
  for (int i = index; i < (*size - 1); ++i) {
    array[i] = array[i + 1];
  }

  // Reduce the active element count;
  (*size)--;
}

template <int size>
int search(int (&array)[size], int target) {
  for (int i = 0; i < size; i++) {
    if (array[i] == target) return i; // target found
  }
  return -1; // target not found
}

int main() {
  // Declare and initialize
  int array[] = { 1, 2, 3 };
  int array_size { sizeof(array) / sizeof(array[0]) }; // 3

  // Access
  array[1]; // 2

  // Search
  search(array, 2); // 1

  // Insertion
  insert(array, &array_size, 3, 4); // { 1, 2, 3, 4 }

  // Deletion
  remove(array, &array_size, 3); // { 1, 2, 3 }
}