Arrays in Data Structures

Analogy categoryAnalogies

Introduction

An array is a linear data structure that stores a fixed-size collection of elements of the same type in contiguous memory locations. Because the elements sit next to each other in memory, the array can compute the address of any element directly from its index, which makes reading any position extremely fast.

🏏

Cricket analogy: An array is like a row of numbered dressing-room lockers assigned to players 1 through 11; because each locker sits at a fixed, contiguous slot, the team manager can walk straight to locker 7 without checking the others first.

Explanation

Every array element is accessed using an index, and in most languages (including Python's list, which behaves like a dynamic array) indexing starts at 0. Because memory is contiguous, the address of element i is simply base_address + i * element_size, so reading or writing arr[i] takes constant time, O(1). Insertion and deletion are more expensive: inserting or removing at the beginning or middle requires shifting all subsequent elements, giving O(n) time in the worst case, while appending at the end is amortized O(1) for a dynamic array like Python's list. Searching for a value without knowing its index requires scanning the array, which is O(n) unless the array is sorted, in which case binary search brings it down to O(log n).

🏏

Cricket analogy: Reading a batting order array by index, like team_list[3] for the number-4 batsman, is O(1) since the position is computed directly; but inserting a new opener means shifting every batsman down a slot, which is O(n).

Example

python

# Python lists behave as dynamic arrays
scores = [88, 92, 75, 60, 99]

# O(1) indexed access
print(scores[2])          # 75

# O(1) amortized append
scores.append(81)
print(scores)              # [88, 92, 75, 60, 99, 81]

# O(n) insertion at a specific position (elements shift right)
scores.insert(0, 100)
print(scores)              # [100, 88, 92, 75, 60, 99, 81]

# O(n) deletion by value (search + shift)
scores.remove(60)
print(scores)              # [100, 88, 92, 75, 99, 81]

# O(n) linear search
def linear_search(arr, target):
    for i, value in enumerate(arr):
        if value == target:
            return i
    return -1

print(linear_search(scores, 99))  # 4

Complexity

Indexed access is O(1) because addresses are computed directly. Append at the end is amortized O(1); Python's list over-allocates capacity so it only needs to reallocate and copy occasionally. Insertion or deletion at an arbitrary position is O(n) because trailing elements must shift to keep the array contiguous. Unsorted search is O(n); sorted search with binary search is O(log n). Space complexity for storing n elements is O(n).

🏏

Cricket analogy: Indexed access on a scoreboard array, like current_over[3], is O(1) since the address is computed directly; appending the next ball's result is amortized O(1), but inserting a corrected run mid-over shifts every later ball, O(n).

Key Takeaways

Arrays store elements contiguously, enabling O(1) indexed access via direct address calculation.
Python lists are dynamic arrays: append is amortized O(1), but insert/delete at arbitrary positions is O(n) due to shifting.
Unsorted linear search is O(n); binary search on a sorted array is O(log n).
Arrays trade flexible size for cache-friendly, fast random access compared to linked structures.

Practice what you learned

1. What is the time complexity of accessing an element by index in an array?

2. What is the worst-case time complexity of inserting an element at the beginning of a Python list?

3. Why is appending to the end of a Python list considered amortized O(1)?

4. Which search strategy achieves O(log n) time on an array?

Was this page helpful?

Multidimensional Arrays

Topics covered

#Python#DataStructuresStudyNotes#DataStructures#ArraysInDataStructures#Arrays#Data#Structures#Explanation#StudyNotes#SkillVeris