AI Hints
Home›DSA in Python Tutorial›Arrays and Lists
DSA in Python · Lesson 14 of 132

List Operation Costs

What is fast, what is slow.

⏱ 2 min read▶ Video at 15:45🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

List Operation Costs
From the video: List Operation Costs
  • 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.

OperationExampleCost
index / assigna[i], a[i] = xO(1)
add / remove at enda.append(x), a.pop()O(1)
add / remove at fronta.insert(0, x), a.pop(0)O(n)
searchx in aO(n)
sorta.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.

front_back.pypython
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")
Output
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)
Next up: Two Pointers — one from each end