Arrays & Lists
14 min
A Python list is a dynamic array: contiguous memory that grows as needed.
That's different from a fixed-size array in C or Java — you never have to
declare a capacity up front.
nums = [3, 1, 4, 1, 5]
nums.append(9) # [3, 1, 4, 1, 5, 9]
nums[0] # 3 — indexing is O(1)
nums[-1] # 9 — negative indices count from the end
nums[1:3] # [1, 4] — slicing copies a sub-range
insert() and pop(0) both shift every following element — O(n). pop() with no argument (removing from the end) is O(1).
The operations you reach for most differ wildly in cost:
| Operation | Cost | Why |
|---|---|---|
| nums[i] (read) | O(1) | direct memory offset |
| nums.append(x) | O(1) amortized | occasional reallocation, averaged out |
| nums.pop() | O(1) | removes from the end, no shift |
| nums.insert(0, x) / nums.pop(0) | O(n) | every element after index 0 shifts |
| x in nums | O(n) | linear scan |
If you find yourself repeatedly inserting/removing from the front of a
list, that's usually a sign you want a collections.deque instead — more on
that in the next module.
Write a function `rotate_left(lst, k)` that returns a new list with `lst` rotated left by `k` positions. `k` may be larger than `len(lst)` — handle that with the modulo operator.
Write a function `second_largest(nums)` that returns the second-largest *distinct* value in a list of integers.
What is the amortized time complexity of appending to the end of a Python list?
You know how Python lists are stored, which operations are O(1) vs O(n), and can manipulate lists with slicing and indexing.