List Operation Costs
What is fast, what is slow.
Adding to the end of a list is fast. But adding to the front means every other item has to shuffle along one box. That small difference can make a program crawl.

- End: fast
- Front: everything shuffles
- Small difference, big effect
Cheat sheet: list costs
Here are the costs to remember. Indexing and changing an item are O of one. Appending and popping from the end are O of one. But inserting or popping at the front, or the middle, is O of N, because items shift. Checking if a value is in the list is O of N. And sorting is O of N log N.
| Operation | Example | Cost |
|---|---|---|
| index / assign | a[i], a[i] = x | O(1) |
| add / remove at end | a.append(x), a.pop() | O(1) |
| add / remove at front | a.insert(0, x), a.pop(0) | O(n) |
| search | x in a | O(n) |
| sort | a.sort() | O(n log n) |
Front versus back
Let's prove it. We add one hundred thousand items to the end with append, and then to the front with insert at zero. Run it. Appending finishes almost instantly. Inserting at the front is dramatically slower, because every insert shifts all the items already there.
import time
start = time.perf_counter()
back = []
for i in range(100_000):
back.append(i)
print(f"append: {time.perf_counter() - start:.3f} s")
start = time.perf_counter()
front = []
for i in range(100_000):
front.insert(0, i)
print(f"insert(0): {time.perf_counter() - start:.3f} s")append: 0.003 s insert(0): 1.812 s
Summary
Work at the end of a list is O of one, but work at the front is O of N. If you need a fast front too, use a deque, which we'll meet soon. Next, a powerful pattern for arrays. Two pointers.
Key takeaways- End: O(1)
- Front: O(n)
- x in list: O(n)