DEV Community

Cover image for Arrays and Array Operations: The Foundation of Every Data Structure
Gouranga Das Samrat
Gouranga Das Samrat

Posted on

Arrays and Array Operations: The Foundation of Every Data Structure

The simplest structure in computing — and still one of the most important.


What Is an Array?

An array is a collection of elements stored in contiguous (adjacent) memory locations, all of the same data type, accessible via an integer index.

Index:   [0]  [1]  [2]  [3]  [4]
Values:  [10] [20] [30] [40] [50]
Address: 100  104  108  112  116   (assuming 4 bytes per int)
Enter fullscreen mode Exit fullscreen mode

Three key properties define an array:

  1. Fixed size — Declared at creation; cannot change (in most languages).
  2. Homogeneous — All elements are the same type.
  3. Random access — Any element can be accessed in O(1) by its index.

How Arrays Work in Memory

When you declare int arr[5], the system allocates 5 × 4 = 20 consecutive bytes in memory.

To access arr[i], the CPU computes:

address_of(arr[i]) = base_address + (i × size_of_element)
Enter fullscreen mode Exit fullscreen mode

For example, if the base address is 100 and each int is 4 bytes:

  • arr[0] → 100
  • arr[1] → 104
  • arr[3] → 112

This formula explains why array indexing is O(1) — it's simple arithmetic, no searching required.


Types of Arrays

1. One-Dimensional Array

The classic linear array: a single row of elements.

arr = [5, 10, 15, 20, 25]
Enter fullscreen mode Exit fullscreen mode

2. Two-Dimensional Array (Matrix)

An array of arrays — rows and columns.

matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
# Access: matrix[row][col] → matrix[1][2] = 6
Enter fullscreen mode Exit fullscreen mode

3. Multi-Dimensional Array

Arrays with 3 or more dimensions. Common in scientific computing, image processing (height × width × channels), and game development.

4. Dynamic Array

Languages like Python (list), Java (ArrayList), and C++ (vector) provide arrays that resize automatically. Under the hood, they allocate a larger chunk of memory when full and copy elements over. Amortized O(1) append.


Core Array Operations

1. Traversal — O(n)

Visit every element exactly once.

def traverse(arr):
    for element in arr:
        print(element)
Enter fullscreen mode Exit fullscreen mode

Used for: printing, summing, searching, transforming.


2. Insertion

At the end (if space available): O(1)

arr[last_index + 1] = new_value
Enter fullscreen mode Exit fullscreen mode

At a specific index: O(n) — all elements after the index must shift right.

def insert_at(arr, index, value):
    # Shift elements right from the end
    for i in range(len(arr) - 1, index, -1):
        arr[i] = arr[i - 1]
    arr[index] = value
Enter fullscreen mode Exit fullscreen mode
Before: [10, 20, 30, 40, _]   Insert 25 at index 2
Shift:  [10, 20, 30, 30, 40]
After:  [10, 20, 25, 30, 40]
Enter fullscreen mode Exit fullscreen mode

Time complexity: O(n) worst case (inserting at index 0 shifts everything).


3. Deletion

From the end: O(1) — just decrement the size counter.

From a specific index: O(n) — elements after the deleted position must shift left.

def delete_at(arr, index, size):
    for i in range(index, size - 1):
        arr[i] = arr[i + 1]
    arr[size - 1] = None   # Clear the last slot
    return size - 1
Enter fullscreen mode Exit fullscreen mode
Before: [10, 20, 30, 40, 50]   Delete at index 1 (value 20)
Shift:  [10, 30, 40, 50, _]
Enter fullscreen mode Exit fullscreen mode

Time complexity: O(n) worst case.


4. Search

Linear Search (unsorted array) — O(n)

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1
Enter fullscreen mode Exit fullscreen mode

Binary Search (sorted array) — O(log n)

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1
Enter fullscreen mode Exit fullscreen mode

5. Update / Access — O(1)

arr[index] = new_value      # Update
value = arr[index]          # Access
Enter fullscreen mode Exit fullscreen mode

Direct index access is the killer feature of arrays — no traversal needed.


6. Sorting

Arrays can be sorted in-place. Complexity depends on the algorithm:

Algorithm Best Average Worst Space
Bubble Sort O(n) O(n²) O(n²) O(1)
Selection Sort O(n²) O(n²) O(n²) O(1)
Insertion Sort O(n) O(n²) O(n²) O(1)
Merge Sort O(n log n) O(n log n) O(n log n) O(n)
Quick Sort O(n log n) O(n log n) O(n²) O(log n)

Complexity Summary for Arrays

Operation Time Complexity
Access by index O(1)
Update by index O(1)
Search (unsorted) O(n)
Search (sorted) O(log n)
Insert at end O(1) amortized
Insert at index O(n)
Delete from end O(1)
Delete from index O(n)
Traverse O(n)

Arrays vs. Linked Lists: A Quick Comparison

Property Array Linked List
Memory layout Contiguous Non-contiguous
Access by index O(1) O(n)
Insertion (middle) O(n) — shifting O(1) — pointer swap
Deletion (middle) O(n) — shifting O(1) — pointer swap
Memory overhead Low (just data) Higher (data + pointer per node)
Cache performance Excellent Poor (pointer chasing)
Size flexibility Fixed (or amortized) Truly dynamic

Use arrays when: You need fast random access, know the size in advance, and rarely insert/delete in the middle.
Use linked lists when: You insert/delete frequently at arbitrary positions and don't need random access.


Common Array Patterns in Problem Solving

Two Pointers

# Reverse an array in-place
def reverse(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
Enter fullscreen mode Exit fullscreen mode

Sliding Window

# Maximum sum subarray of size k
def max_sum(arr, k):
    window = sum(arr[:k])
    max_sum = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]
        max_sum = max(max_sum, window)
    return max_sum
Enter fullscreen mode Exit fullscreen mode

Prefix Sum

# Precompute prefix sums for O(1) range queries
def build_prefix(arr):
    prefix = [0] * (len(arr) + 1)
    for i, val in enumerate(arr):
        prefix[i + 1] = prefix[i] + val
    return prefix

def range_sum(prefix, l, r):
    return prefix[r + 1] - prefix[l]  # O(1) query
Enter fullscreen mode Exit fullscreen mode

Summary

  • Arrays store elements contiguously in memory, enabling O(1) random access.
  • Access and update are O(1); traversal is O(n); insertion and deletion in the middle are O(n) due to shifting.
  • Types include 1D, 2D, multi-dimensional, and dynamic arrays.
  • Binary search (O(log n)) only works on sorted arrays.
  • Arrays excel at random access; linked lists excel at frequent middle insertions/deletions.
  • Powerful algorithmic patterns built on arrays: two pointers, sliding window, prefix sums.

Next up: Linear Search vs. Binary Search — a detailed comparison of the two fundamental searching strategies.


Top comments (0)