What are the time complexities of common list operations (indexing, append, insert, pop, search)?
Python list is a dynamic array: O(1) index and amortized append, O(n) middle operations
A CPython list is a dynamic array of pointers. Indexing and assignment by index are O(1). append is amortized O(1) because the list occasionally reallocates and copies to grow. pop from the end is O(1). insert or pop at the front or middle is O(n) because elements must shift. Search by value is O(n) because it scans. Slicing is O(k) where k is the slice length.
- 1
lst[i], lst[i] = x: O(1)
- 2
append(x), pop(): amortized O(1)
- 3
insert(i, x), pop(i), remove(x): O(n)
- 4
x in lst, index(x): O(n)
- 5
Trade-off: use deque for O(1) appends/pops at both ends, and array for compact numeric storage.
- 6
Common mistake: saying append is always O(1). It is amortized O(1); a single append can be O(n) during resize.
- 7
Version note: overallocation growth factors are CPython implementation details and can change.
Scenario Questions
0-2 years experience
- 1You frequently pop from the front of a list. What is the complexity and what should you use?
- 2You append a million items. Is each append O(1)? Explain amortized.
2-5 years experience
- 1You need random access and occasional inserts in the middle. List or deque?
- 2You profile a list insert at index 0. Why is it slow?
5-8 years experience
- 1You are designing a sliding window over a large sequence. Which list operations matter?
- 2You need a fixed-size ring buffer. How do list vs deque compare?
8+ years experience
- 1Design a data structure that supports O(1) index, O(1) append/pop both ends, and O(log n) insert. Discuss Python built-ins and custom structures.
- 2You need to optimize a hot loop with many list pops. How do you choose between list, deque, and array?
Follow-up Questions
- Why is list.pop(0) O(n) while deque.popleft() is O(1)?
- How does list overallocation affect memory usage?