DSA Arrays

An array is one of the most fundamental data structures in computer science. It stores a fixed number of elements of the same type in contiguous (side-by-side) memory locations. Arrays are the building blocks upon which many other data structures are built.

In Python, the built-in list serves as a dynamic array — it works like a traditional array but can also grow and shrink in size automatically.

How Arrays Work Internally

When an array is created, a block of memory is reserved. Each element is stored at a specific memory address, and elements can be accessed directly using their index — a number that represents the element's position in the array.

Indexing always starts at 0 in most programming languages, including Python.


# Creating an array (list) in Python
scores = [85, 90, 78, 92, 88]

# Index:    0   1   2   3   4

print(scores[0])   # Output: 85 — first element
print(scores[3])   # Output: 92 — fourth element
print(scores[-1])  # Output: 88 — last element (negative indexing)

Types of Arrays

1. One-Dimensional Array

A single row of elements, like a numbered list. This is the most basic form.


# One-dimensional array
temperatures = [22, 25, 19, 30, 27]
print(temperatures[2])   # Output: 19

2. Two-Dimensional Array (Matrix)

An array of arrays — like a table with rows and columns. Useful for representing grids, matrices, or tables of data.


# Two-dimensional array (3 rows, 3 columns)
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

print(matrix[1][2])   # Output: 6 — row 1, column 2

Core Array Operations

Accessing an Element — O(1)

Because elements are stored at known memory addresses (calculated from the index), accessing any element takes constant time.


colors = ["red", "green", "blue", "yellow"]
print(colors[2])   # Output: blue

Inserting an Element

Inserting at the end of a dynamic array is O(1) on average. Inserting at a specific position is O(n) because all elements after that position must shift to the right.


fruits = ["apple", "banana", "cherry"]

# Insert at the end — O(1)
fruits.append("date")
print(fruits)   # ['apple', 'banana', 'cherry', 'date']

# Insert at position 1 — O(n), shifts elements right
fruits.insert(1, "avocado")
print(fruits)   # ['apple', 'avocado', 'banana', 'cherry', 'date']

Deleting an Element

Deleting from the end is O(1). Deleting from a specific position is O(n) because elements must shift left to fill the gap.


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

# Remove last element — O(1)
numbers.pop()
print(numbers)   # [10, 20, 30, 40]

# Remove element at index 1 — O(n)
numbers.pop(1)
print(numbers)   # [10, 30, 40]

Searching for an Element — O(n)

In an unsorted array, the only way to find a specific element is to check each one. This is called linear search.


def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i   # Return the index where target is found
    return -1          # Return -1 if not found

result = linear_search([5, 3, 8, 1, 9], 8)
print(result)   # Output: 2

Traversing (Iterating) an Array — O(n)

Going through each element one by one is called traversal. It is the most common array operation.


grades = [88, 72, 95, 60, 84]

for grade in grades:
    print(grade)

# Output:
# 88
# 72
# 95
# 60
# 84

Array Slicing in Python

Python allows extracting a portion of a list using slice notation: list[start:end]. The start index is included; the end index is excluded.


letters = ["a", "b", "c", "d", "e", "f"]

print(letters[1:4])    # Output: ['b', 'c', 'd']
print(letters[:3])     # Output: ['a', 'b', 'c']
print(letters[3:])     # Output: ['d', 'e', 'f']
print(letters[::2])    # Output: ['a', 'c', 'e'] — every second item

Common Array Algorithms

Finding the Maximum and Minimum


def find_max_min(arr):
    max_val = arr[0]
    min_val = arr[0]
    for num in arr:
        if num > max_val:
            max_val = num
        if num < min_val:
            min_val = num
    return max_val, min_val

maximum, minimum = find_max_min([4, 2, 9, 1, 7])
print("Max:", maximum, "| Min:", minimum)
# Output: Max: 9 | Min: 1

Reversing an Array


def reverse_array(arr):
    left = 0
    right = len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    return arr

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

Rotating an Array


# Rotate array left by k positions
def rotate_left(arr, k):
    k = k % len(arr)   # Handle k larger than array length
    return arr[k:] + arr[:k]

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

Limitations of Arrays

  • Fixed size (in traditional languages): Traditional arrays cannot grow after creation. Python lists overcome this limitation.
  • Slow insertion/deletion in the middle: Shifting elements makes these operations O(n).
  • No built-in search optimization: Searching requires O(n) unless the array is sorted.

Big O Summary for Arrays

  • Access by index — O(1)
  • Search (unsorted) — O(n)
  • Insert at end — O(1) amortized
  • Insert at position — O(n)
  • Delete at end — O(1)
  • Delete at position — O(n)

Key Points

  • An array stores elements in contiguous memory, allowing fast index-based access.
  • Python's list is a dynamic array that can grow or shrink automatically.
  • Accessing by index is O(1); searching in an unsorted array is O(n).
  • Inserting or deleting in the middle is O(n) because elements must shift.
  • Two-dimensional arrays represent tabular data and are widely used in algorithms.
  • Understanding arrays thoroughly is essential before moving to more complex structures.
Previous lessons
Back to courses
Next lessons

Leave a Comment