Arrays in Data Structure: A Complete Guide with Examples

Property

Value / Description

Data type constraint

Homogeneous – all elements must be the same type

Memory layout

Contiguous – elements occupy adjacent memory addresses

Index base

0-indexed in most languages (element 0 is the first)

Access time

O(1) – constant time direct access via index

Size

Fixed at declaration time in statically typed languages

Dimensions

1D (linear), 2D (matrix), multi-dimensional, jagged

Key Concept: The contiguous memory layout is what makes arrays fast. When you access array[5], the CPU calculates the exact memory address as: base_address + (5 × element_size). No traversal needed – this is true O(1) random access.

Property

Description

Time Complexity

Order

Linear data structure – elements stored in a specific, fixed sequence

–

Direct Access

Any element accessible via its index number – no traversal required

O(1)

Searching

Linear search for unsorted arrays; binary search for sorted arrays

O(n) / O(log n)

Insertion

Requires shifting elements to create space at the target index

O(n)

Deletion

Requires shifting elements to close the gap after removal

O(n)

Fixed Size

Size predetermined at declaration – cannot grow or shrink dynamically

–

Homogeneous

All elements must be the same data type

–

Cache-Friendly

Contiguous memory layout maximises CPU cache hit rates

–

# linear array in data structure - memory representation

# Formula: Address(A[i]) = B + i × w

# Example: int A[5] = {10, 20, 30, 40, 50}

# Base address B = 2000, element size w = 4 bytes

#

# A[0] = 2000 A[1] = 2004 A[2] = 2008

# A[3] = 2012 A[4] = 2016

# Python equivalent

A = [10, 20, 30, 40, 50]

print(f'Element at index 3: {A[3]}') # Output: 40

# 2d array in data structure - row-major memory representation

# For a 3×3 matrix A[3][3], base address B, element size w:

#

# Row-Major: Address(A[i][j]) = B + (i × cols + j) × w

# Column-Major: Address(A[i][j]) = B + (j × rows + i) × w

# Python 2D array (list of lists)

matrix = [

[1, 2, 3],

[4, 5, 6],

[7, 8, 9]

]

# Access element at row 1, column 2

print(matrix[1][2]) # Output: 6

# Row-major memory layout (conceptual):

# [1][2][3][4][5][6][7][8][9]

# A[0][0..2] then A[1][0..2] then A[2][0..2]

Ordering

Formula

Language Default

Memory Sequence for A[2][3]

Row-Major

B + (i×cols + j)×w

C, C++, Java, Python

A[0][0], A[0][1], A[0][2], A[1][0], A[1][1], A[1][2]

Column-Major

B + (j×rows + i)×w

Fortran, MATLAB, R

A[0][0], A[1][0], A[0][1], A[1][1], A[0][2], A[1][2]

# algorithm of array in data structure - Binary Search O(log n)

def binary_search(arr, target):

left, right = 0, len(arr) - 1

while left <= right:

mid = (left + right) // 2

if arr[mid] == target:

return mid # Found - return index

elif arr[mid] < target:

left = mid + 1 # Search right half

else:

right = mid - 1 # Search left half

return -1 # Not found

sorted_arr = [10, 20, 30, 40, 50, 60, 70]

print(binary_search(sorted_arr, 40)) # Output: 3

print(binary_search(sorted_arr, 25)) # Output: -1

# Insertion at a specific index - O(n) due to shifting

def insert_at(arr, index, value):

arr.append(None) # Extend array by 1

for i in range(len(arr)-1, index, -1):

arr[i] = arr[i-1] # Shift elements right

arr[index] = value # Place new element

return arr

arr = [10, 20, 30, 40, 50]

print(insert_at(arr, 2, 99)) # Output: [10, 20, 99, 30, 40, 50]

# Deletion at a specific index - O(n) due to shifting

def delete_at(arr, index):

for i in range(index, len(arr)-1):

arr[i] = arr[i+1] # Shift elements left

arr.pop() # Remove last (now duplicate) element

return arr

arr = [10, 20, 30, 40, 50]

print(delete_at(arr, 2)) # Output: [10, 20, 40, 50]

Operation

Algorithm Type

Time Complexity

Space Complexity

Access by index

Direct calculation

O(1)

O(1)

Linear Search

Sequential scan

O(n)

O(1)

Binary Search (sorted)

Divide and conquer

O(log n)

O(1)

Insertion at end

Append

O(1) amortised

O(1)

Insertion at index

Shift right then insert

O(n)

O(1)

Deletion at index

Shift left

O(n)

O(1)

Bubble Sort

Compare-and-swap

O(n²)

O(1)

Quick Sort

Divide and conquer

O(n log n) avg

O(log n)

Traversal

Single pass

O(n)

O(1)

# Traversal - array operations in data structure

arr = [5, 10, 15, 20, 25]

total = 0

for element in arr:

total += element

print(f'Sum: {total}') # Output: Sum: 75

# Time: O(n) | Space: O(1)

# Insertion - operation of array in data structure

arr = [1, 2, 3, 5, 6]

arr.insert(3, 4) # Insert 4 at index 3

print(arr) # Output: [1, 2, 3, 4, 5, 6]

# Time: O(n) worst case (shift n-index elements)

# Deletion - operation of array in data structure

arr = [1, 2, 3, 4, 5]

arr.pop(2) # Remove element at index 2 (value: 3)

print(arr) # Output: [1, 2, 4, 5]

# Time: O(n) worst case

# Linear Search - O(n)

def linear_search(arr, target):

for i, val in enumerate(arr):

if val == target: return i

return -1

arr = [64, 25, 12, 22, 11]

print(linear_search(arr, 22)) # Output: 3

print(linear_search(arr, 99)) # Output: -1

# Bubble Sort - array operations in data structure

def bubble_sort(arr):

n = len(arr)

for i in range(n):

for j in range(0, n-i-1):

if arr[j] > arr[j+1]:

arr[j], arr[j+1] = arr[j+1], arr[j] # Swap

return arr

arr = [64, 25, 12, 22, 11]

print(bubble_sort(arr)) # Output: [11, 12, 22, 25, 64]

# Time: O(n²) | Space: O(1)

# implementing stack using array - Python

class ArrayStack:

def __init__(self, capacity):

self.capacity = capacity

self.stack = [None] * capacity # Fixed-size array

self.top = -1 # -1 means empty stack

def push(self, value):

if self.top == self.capacity - 1:

print('Stack Overflow - array is full')

return

self.top += 1

self.stack[self.top] = value

print(f'Pushed: {value}')

def pop(self):

if self.top == -1:

print('Stack Underflow - array is empty')

return None

value = self.stack[self.top]

self.stack[self.top] = None

self.top -= 1

return value

def peek(self):

if self.top == -1: return None

return self.stack[self.top]

def is_empty(self):

return self.top == -1

# Test the array-based stack

s = ArrayStack(5)

s.push(10) # Pushed: 10

s.push(20) # Pushed: 20

s.push(30) # Pushed: 30

print(s.peek()) # Output: 30 (top element)

print(s.pop()) # Output: 30 (removed)

print(s.peek()) # Output: 20 (new top)

// implementing stack using array - Java

public class ArrayStack {

private int[] stack;

private int top;

private int capacity;

public ArrayStack(int capacity) {

this.capacity = capacity;

this.stack = new int[capacity];

this.top = -1;

}

public void push(int value) {

if (top == capacity - 1) { System.out.println("Overflow"); return; }

stack[++top] = value;

}

public int pop() {

if (top == -1) { System.out.println("Underflow"); return -1; }

return stack[top--];

}

public int peek() { return top == -1 ? -1 : stack[top]; }

public boolean isEmpty() { return top == -1; }

}

// Stack operations complexity:

// Push: O(1) | Pop: O(1) | Peek: O(1) | Search: O(n)

Stack Operation

Array Implementation

Time Complexity

Notes

Push (add element)

stack[++top] = value

O(1)

Constant time - just increment index and assign

Pop (remove top)

return stack[top--]

O(1)

Constant time - just return and decrement index

Peek (view top)

return stack[top]

O(1)

No modification - just read top index value

isEmpty

return top == -1

O(1)

Single comparison

Search

Linear scan

O(n)

Must scan from bottom to top in worst case

Application

How Arrays Are Used

Example

Stack Implementation

Fixed-size array with top pointer - LIFO operations

Browser history, undo/redo systems, function call stack

Queue Implementation

Array with front and rear pointers - FIFO operations

Print queues, task schedulers, BFS traversal

Sorting Algorithms

In-place sort algorithms operate directly on array elements

Bubble sort, quick sort, merge sort, heap sort

Searching Algorithms

Linear and binary search operate on indexed array elements

Database lookups, spell checkers, contact search

Matrix Operations

2D arrays represent matrices for linear algebra operations

Image processing, machine learning, graphics rendering

Hash Tables

Arrays serve as the underlying structure for hash buckets

Dictionary implementations, database indexing

Dynamic Programming

DP tables stored as 1D or 2D arrays to cache sub-results

Fibonacci, knapsack, longest common subsequence

Graph Adjacency Matrix

2D array representing connections between graph nodes

Network routing, social graph analysis, path finding

String Storage

Strings are character arrays in low-level languages

Text processing, pattern matching, compiler tokenisation

Advantage

Detail

O(1) Access Time

Direct index-based access makes arrays the fastest structure for random element retrieval

Cache Efficiency

Contiguous memory layout maximises CPU cache hits - arrays outperform linked lists in read-heavy workloads

Space Efficiency

No pointer overhead - arrays use the minimum possible memory for their data

Simple Implementation

Straightforward syntax in all programming languages - easy to declare, initialise, and use

Foundation for Other Structures

Stacks, queues, heaps, and hash tables are all implementable as arrays

Supports All Sort Algorithms

In-place sort algorithms (bubble, quick, selection) work natively on arrays

Disadvantage

Detail

Alternative

Fixed Size

Size set at declaration - cannot grow dynamically in static languages

Use ArrayList (Java) or list (Python) for dynamic sizing

Homogeneous Only

All elements must be the same data type - no mixed-type storage

Use structs, objects, or tuples for mixed types

Costly Insertion/Deletion

O(n) shifting required for mid-array insert/delete operations

Use linked lists when insert/delete frequency is high

Memory Waste

Oversized pre-allocation wastes memory; undersizing causes overflow

Use dynamic arrays or linked structures

No Built-in Bounds Safety

C/C++ arrays do not check for out-of-bounds access at runtime

Use Java/Python arrays with built-in bounds checking