Arrays (Python Lists) Explained

An array is a block of memory that stores a sequence of elements so that any one of them can be reached instantly by its position, or index. In Python, the built-in list is the everyday stand-in for an array — but it is technically a dynamic array: it can grow and shrink at runtime while still giving you that instant, constant-time access by index. Understanding how lists really work under the hood, not just which methods to call, is the foundation for almost everything else in this course: stacks, queues, hash tables, sorting, and searching all build on the array’s core idea of contiguous, indexed storage.

Overview / How it works

In a classic array (like a C array), the computer reserves one contiguous block of memory large enough to hold a fixed number of same-sized elements. To find element i, the computer does simple arithmetic: address = base_address + i * element_size. No searching is involved — it’s a direct calculation, which is exactly why indexing is O(1).

A Python list works the same way, with two twists. First, a Python list doesn’t store the actual objects side by side in that block; it stores references (pointers) to objects, which is why a single list can hold mixed types like [1, "two", 3.0] — every slot is the same fixed size (a pointer), even though the objects they point to vary in size. Second, unlike a fixed-size C array, a Python list can grow. When you call .append() and the underlying array is full, CPython doesn’t just add one more slot — it allocates a new, larger block (roughly a constant factor bigger than before) and copies all the existing references over. Because this over-allocation happens in bigger and bigger jumps rather than one slot at a time, the *average* cost of an append, spread out over many appends, works out to O(1). This is called amortized constant time: any individual append might trigger an O(n) resize, but resizes happen rarely enough that the cost per operation averages out to constant.

Picture building a shopping list by adding items one at a time with append: each addition just drops the new item into already-reserved space, occasionally triggering a quick behind-the-scenes reallocation. Now picture instead always adding new items to the front of the list with insert(0, item): every existing item has to physically shift one slot to the right to make room, which is O(n) work every single time. Same data structure, wildly different cost, depending on where you operate.

Time and Space Complexity

The table below summarizes the core operations. “Amortized” means the cost averaged over a long sequence of operations, not the cost of any single call.

Operation	Example	Time Complexity	Why
Index access	arr[i]	O(1)	Direct address calculation — no scanning
Append at end	arr.append(x)	O(1) amortized, O(n) worst case	Spare capacity absorbs most appends; occasional resizes copy everything
Insert at front/middle	arr.insert(0, x)	O(n)	Every following element must shift right
Delete at end	arr.pop()	O(1)	No shifting — just shrink the length
Delete at front/middle	arr.pop(0)	O(n)	Every following element must shift left
Search (unsorted)	x in arr	O(n)	Elements are checked one by one
Search (sorted, binary search)	bisect.bisect_left(arr, x)	O(log n)	Each comparison halves the remaining search space
Slicing	arr[a:b]	O(k)	Copies k = b – a elements into a new list
Space	—	O(n)	One reference per element, plus a small reserved buffer

Examples

Example 1: Core list operations

This example shows the everyday toolkit: appending, inserting, popping, indexing, and slicing.

def demo_operations() -> None:
    numbers: list[int] = [10, 20, 30]
    numbers.append(40)
    numbers.insert(1, 15)
    removed = numbers.pop()
    print("List after append and insert:", numbers)
    print("Removed with pop():", removed)
    print("Element at index 2:", numbers[2])
    print("Slice [1:3]:", numbers[1:3])

demo_operations()

Output:

List after append and insert: [10, 15, 20, 30]
Removed with pop(): 40
Element at index 2: 20
Slice [1:3]: [15, 20]

Trace it by hand: starting from [10, 20, 30], append(40) gives [10, 20, 30, 40]. insert(1, 15) pushes 15 into index 1, shifting everything after it right, giving [10, 15, 20, 30, 40]. pop() with no argument removes and returns the last element, 40, leaving [10, 15, 20, 30]. From there, index 2 holds 20, and the slice [1:3] grabs indices 1 and 2, giving [15, 20].

Example 2: Two-pointer in-place reversal

A classic array technique is the two-pointer pattern: one pointer starts at the front, one at the back, and they walk toward each other.

def reverse_in_place(arr: list[int]) -> list[int]:
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    return arr

values = [1, 2, 3, 4, 5]
print("Original:", [1, 2, 3, 4, 5])
reverse_in_place(values)
print("Reversed:", values)

Output:

Original: [1, 2, 3, 4, 5]
Reversed: [5, 4, 3, 2, 1]

With arr = [1, 2, 3, 4, 5], left starts at 0 and right at 4. The first swap exchanges indices 0 and 4, giving [5, 2, 3, 4, 1]. Now left = 1, right = 3, so the second swap exchanges indices 1 and 3, giving [5, 4, 3, 2, 1]. Now left = 2, right = 2, so left < right is false and the loop stops. This runs in O(n) time and, because it swaps in place, uses only O(1) extra space — no second array is allocated.

Example 3: Maximum subarray sum (Kadane’s algorithm)

A more realistic, interview-style array problem: given an array of integers, find the largest possible sum of a contiguous subarray.

def max_subarray_sum(nums: list[int]) -> int:
    best_sum = nums[0]
    current_sum = nums[0]
    for i in range(1, len(nums)):
        current_sum = max(nums[i], current_sum + nums[i])
        best_sum = max(best_sum, current_sum)
    return best_sum

scores = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
result = max_subarray_sum(scores)
print("Array:", scores)
print("Maximum subarray sum:", result)

Output:

Array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Maximum subarray sum: 6

At each position, current_sum answers “what’s the best subarray ending exactly here?” — either extend the previous subarray, or start fresh at the current element, whichever is larger. best_sum tracks the best answer seen anywhere so far. The winning subarray here is [4, -1, 2, 1], which sums to 6. This single pass is O(n) time and O(1) extra space, compared to the naive O(n²) approach of checking every possible subarray.

How it works step by step

Tracing Kadane’s algorithm on [-2, 1, -3, 4, -1, 2, 1, -5, 4] element by element:

i	nums[i]	current_sum	best_sum
0 (start)	-2	-2	-2
1	1	max(1, -2+1) = 1	1
2	-3	max(-3, 1-3) = -2	1
3	4	max(4, -2+4) = 4	4
4	-1	max(-1, 4-1) = 3	4
5	2	max(2, 3+2) = 5	5
6	1	max(1, 5+1) = 6	6
7	-5	max(-5, 6-5) = 1	6
8	4	max(4, 1+4) = 5	6

By the time the loop finishes, best_sum has settled on 6 and never changes again in the last two steps, because neither remaining current_sum beats it. Each step only looks at the immediately preceding current_sum, which is what keeps this O(n) instead of re-scanning subarrays.

Common Mistakes

Mistake 1: Off-by-one loop bounds

A very common bug is looping one step too far when peeking ahead at the next element:

def print_pairs(arr):
    for i in range(len(arr)):
        print(arr[i], arr[i + 1])  # IndexError on the last iteration

print_pairs([1, 2, 3, 4])

With arr = [1, 2, 3, 4], range(len(arr)) lets i reach 3, and on that final iteration the code tries to read arr[4], which doesn’t exist — raising IndexError: list index out of range. The fix is to stop one index earlier, since the last valid pair uses the second-to-last element:

def print_pairs(arr: list[int]) -> None:
    for i in range(len(arr) - 1):
        print(arr[i], arr[i + 1])

print_pairs([1, 2, 3, 4])

Output:

1 2
2 3
3 4

Mistake 2: Mutating a list while iterating over it

Removing elements from a list while looping over that same list is a classic source of silently skipped elements, because a for loop tracks a numeric index internally, and removing an item shifts every later item one slot left — right under the loop’s feet:

def remove_evens(nums):
    for n in nums:
        if n % 2 == 0:
            nums.remove(n)
    return nums

print(remove_evens([2, 4, 6, 8, 10]))

Every element in [2, 4, 6, 8, 10] is even, so you might expect an empty list back. Instead, the loop’s internal index advances past elements that just shifted into the spot the index is about to check next, and the buggy function returns [4, 8] — two even numbers survive untouched. The reliable fix is to never mutate a list you’re iterating over; build a new list instead, most simply with a comprehension:

def remove_evens(nums: list[int]) -> list[int]:
    return [n for n in nums if n % 2 != 0]

print(remove_evens([2, 4, 6, 8, 10]))
print(remove_evens([1, 2, 3, 4, 5, 6]))

Output:

[]
[1, 3, 5]

Best Practices

• Reach for list when you need ordered, mutable, index-accessible storage; use a tuple when the sequence shouldn’t change after creation.
• Prefer appending to the end (list.append) over inserting at the front; if you genuinely need fast operations at both ends (a queue), use collections.deque, which gives O(1) appends and pops on either side instead of list’s O(n) front operations.
• If you’ll be checking membership (x in collection) repeatedly, convert to a set first — O(1) average lookup beats O(n) linear scanning once you do it more than a couple of times.
• Avoid list.insert(0, x) or list.pop(0) inside a loop over many elements; each call is O(n), so a loop of n such calls silently becomes O(n²).
• Never mutate a list while iterating over it directly; iterate over a copy (for x in list(original):) or build a new list with a comprehension.
• Use enumerate(arr) when you need both index and value, instead of manually indexing with range(len(arr)) — it’s clearer and sidesteps off-by-one bugs.
• When you must search repeatedly and the data can be kept sorted, use the bisect module for O(log n) binary search instead of linear in checks.

Practice Exercises

1. Rotate an array. Write rotate_right(arr, k) that rotates a list to the right by k positions and returns the new list. For example, rotate_right([1, 2, 3, 4, 5], 2) should return [4, 5, 1, 2, 3]. Hint: slicing the list into two pieces and swapping their order is more efficient than rotating one element at a time.

2. Second-largest value. Write find_second_largest(arr) that returns the second-largest distinct value using a single pass, without sorting. For example, find_second_largest([5, 1, 9, 9, 3]) should return 5 (9 is largest, and it repeats, so 5 is the next distinct value down). Hint: track two running variables as you scan once.

3. Merge two sorted arrays. Write merge_sorted(a, b) that merges two already-sorted lists into one sorted list in O(n + m) time, without calling sort(). Hint: use two index pointers, one per list, always taking the smaller of the two current elements.

Summary

• A Python list is a dynamic array: contiguous storage of object references, giving O(1) index access via direct address arithmetic.
• Appending at the end is O(1) amortized, because CPython over-allocates spare capacity and only occasionally pays an O(n) resize cost.
• Inserting or deleting at the front or middle is O(n), since every following element has to shift; deleting from the end is O(1).
• Searching an unsorted list is O(n); a sorted list can be searched in O(log n) with binary search.
• Overall space usage is O(n), plus a small reserved buffer for future growth.
• Never mutate a list while iterating over it — build a new list or iterate over a copy instead.
• Watch loop bounds carefully whenever you look ahead to arr[i + 1]; range(len(arr)) and range(len(arr) - 1) are not interchangeable.