Applications of Array in Data Structure, With Examples

Short answer

An array stores items in contiguous memory so any item can be read by its index in O(1) time. Arrays are used to store lists and records, build matrices and grids, implement stacks, queues, heaps and hash tables, hold lookup tables and frequency counts, run binary search and sorting, and power patterns such as prefix sums, two pointers and sliding windows.

Arrays are the base of most other data structures, so understanding where they shine, and where they hurt, is the first step in DSA.

What an array gives you

Because elements sit next to each other in memory, the computer finds element i with one calculation. That fast index access, plus good use of the CPU cache, is why arrays are everywhere.

Operation	Time
Read or write by index	O(1)
Search an unsorted array	O(n)
Search a sorted array (binary search)	O(log n)
Append to a dynamic array	O(1) amortised
Insert or delete in the middle	O(n), because elements shift

Main applications of arrays

Application	Example
Storing collections of similar data	Marks of a class, daily temperatures, product prices
Lookup tables	Days in each month, a tax-slab table
Matrices and grids (2D arrays)	Chess and game boards, images as pixel grids, spreadsheets
Implementing other data structures	Stacks, queues, heaps and the buckets of a hash table
Dynamic programming tables	dp[i] and dp[i][j] arrays
Frequency and counting arrays	Counting letters, counting sort, histograms
Binary search and sorting	Searching sorted data, merge sort, quicksort
Buffers	A circular buffer for audio or network packets
Prefix sums and sliding windows	Fast range queries and running averages

A 2D array in practice

grid = [[1, 2, 3],
        [4, 5, 6],
        [7, 8, 9]]            # a 2D array: rows of columns

print(grid[1][2])             # row 1, column 2
print([sum(row) for row in grid])
print([sum(col) for col in zip(*grid)])

Output: 6, [6, 15, 24], [12, 15, 18]

Array patterns that solve many problems

Prefix sum: answer range sums in O(1)

def build_prefix(nums):
    prefix = [0]
    for n in nums:
        prefix.append(prefix[-1] + n)
    return prefix

nums = [3, 1, 4, 1, 5, 9, 2, 6]
prefix = build_prefix(nums)
left, right = 2, 5                      # sum of nums[2] to nums[5]
print(prefix[right + 1] - prefix[left])   # O(1) per query

Output: 19, which is 4 + 1 + 5 + 9.

Two pointers on a sorted array

def pair_with_sum(sorted_nums, target):
    left, right = 0, len(sorted_nums) - 1
    while left < right:
        total = sorted_nums[left] + sorted_nums[right]
        if total == target:
            return [left, right]
        if total < target:
            left += 1
        else:
            right -= 1
    return []

print(pair_with_sum([1, 2, 4, 6, 8, 11], 14))

Output: [3, 4], because 6 + 8 = 14.

Binary search on a sorted array

function binarySearch(sorted, target) {
  let low = 0, high = sorted.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

console.log(binarySearch([2, 5, 8, 12, 16, 23, 38], 23), binarySearch([2, 5, 8], 7));

Output: 5 -1

Kadane's algorithm: best subarray sum

def max_subarray(nums):
    best = current = nums[0]
    for n in nums[1:]:
        current = max(n, current + n)       # extend the run or start again here
        best = max(best, current)
    return best

print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))

Output: 6, from the run 4, -1, 2, 1.

Array vs linked list

	Array	Linked list
Access by index	O(1)	O(n)
Insert or delete in the middle	O(n)	O(1) once you hold the node
Memory	Contiguous, cache friendly, a fixed or resized block	Extra pointer per node, scattered
Best when	You read by position often	You insert and remove often at known nodes

Common mistakes

Off-by-one errors: indexes run from 0 to length - 1.
Reading outside the array, which throws an error in Python and Java and gives undefined in JavaScript.
Changing the array while looping over it.
Using a fixed-size array when the size is not known in advance.
Inserting in the middle inside a loop, which turns O(n) into O(n^2).

Practice problems, in order

The Masai guide to the applications of array has more examples. Next, see the applications of queue and hash maps.

Frequently asked questions

What are the applications of arrays?

Storing collections, lookup tables, matrices and grids, implementing stacks, queues, heaps and hash tables, frequency counts, dynamic programming tables, and binary search and sorting.

Why is array access O(1)?

Elements are stored contiguously, so the address of element i is the start address plus i times the element size. One calculation, whatever the length.

What is a real-life example of an array?

A row of numbered lockers, the seats in a cinema row, or a list of marks for a class are all arrays.

What is the difference between an array and a list in Python?

A Python list is a dynamic array that can grow and hold mixed types. A fixed array, such as the array module or NumPy arrays, stores one type in a compact block.

What is the disadvantage of an array?

Inserting or deleting in the middle is slow, and a fixed-size array cannot grow, so a dynamic array must occasionally copy itself to a bigger block.