DSA Arrays

What Is an Array?

An array stores its elements in one contiguous block of memory, with every element occupying the same fixed amount of space. This uniform, back-to-back layout is what lets an array compute the location of any element directly instead of having to search for it.

Because every slot has an identical size, the address of the element at position i can be computed with a single formula: base_address + i * element_size. Reading values[3] therefore costs exactly the same single step as reading values[3000000]. Contrast this with a linked list, where nodes can live anywhere in memory and finding the i-th node means following i pointers one at a time - an O(n) walk.

Arrays in Python and Their Operation Costs

• Access by index - O(1), computed directly from a memory address formula
• Search by value - O(n), elements are checked one by one until a match is found
• Append at the end - O(1) amortized, usually writes straight into spare capacity
• Insert or delete at the front or middle - O(n), later elements must shift to keep the array contiguous

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

print(values[0])   # 10 - first slot
print(values[3])   # 40 - jumps directly to the 4th slot
print(values[-1])  # 50 - Python resolves this to values[4] first

Reading values[3] never walks past indices 0, 1, and 2. Python computes the target memory address as base_address + 3 * element_size and reads that slot directly - one arithmetic step and one memory read, regardless of whether the list holds 5 elements or 5 million. That is the essence of O(1) access: the cost does not depend on the size of the input.

data = [2, 3, 4, 5]
data.insert(0, 1)
print(data)  # [1, 2, 3, 4, 5]

# Trace: to make room at index 0, Python moves
# 5 -> index 4, 4 -> index 3, 3 -> index 2, 2 -> index 1
# (4 element moves for a 4-element list), then writes 1 at index 0.

data = []
for value in [10, 20, 30, 40]:
    data.append(value)
print(data)  # [10, 20, 30, 40]

# Trace: Python lists over-allocate spare capacity, so most appends
# just write into the next free slot - O(1). Occasionally the spare
# capacity runs out and Python copies everything into a bigger block,
# an O(n) event that happens rarely enough that the average
# ('amortized') cost per append still works out to O(1).