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 oen 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.

Implementation#

Attention

Array in Python is a list whose size is not fixed.

array: list[int] = [1, 2, 3, 4, 5]

# Access
array[0] # 1

# Search
array.index(3) # 2

# Insertion
array.insert(3, 2.5) # [1, 2, 2.5, 3, 4, 5]
# or, to append at the end of list:
array.append(6) #[1, 2, 2.5, 3, 4, 5, 6]

# Deletion
array.remove(3) # [1, 2, 3, 4, 5, 6]

#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 }
}