Python iteration, helpers and choosing a container

Why it matters

Two things trip up almost every programmer who works with containers. The first is changing a list while you loop over it, which often skips items without any error. The second is choosing a container that matches the wrong pattern of use, which makes a program slow or hard to read. This lesson fixes both. It also covers the built-in functions and methods for sorting, searching and copying, which you will use every week.

By the end of the lesson you should be able to look at a problem and name the container you would reach for first, explain why in one sentence, and remove items from a list without breaking the loop.

The problem: a loop that changes what it loops over

Suppose you want to delete every word shorter than four letters from a list while you walk through it. The natural first attempt looks like this:

words = ["a", "to", "bird", "be", "tree"]
for w in words:
    if len(w) < 4:
        words.remove(w)
print(words)

This code runs without an error and prints ['to', 'bird', 'tree']. The word to should have been removed, and it is still there. Python does not stop the loop when the list changes. It keeps a position, and removing an item shifts the items after it to the left. The loop moves on past the gap and never looks at the shifted item. The rest of this lesson explains how a loop keeps its position and which versions are safe.

Iterators: a bookmark for a container

An iterator is an object that walks through a container one item at a time. Think of it as a bookmark that remembers your place. Python has two built-in functions for working with one directly. iter(x) makes an iterator from a container, and next(it) returns the next item and moves the bookmark forward. When no items are left, next raises StopIteration. A second argument to next gives a default value instead of the error.

The output is:

1 2 done
caught: StopIteration

The for loop is a short way to write this. Python creates the iterator for you, asks it for items until it is finished, and hands each item to your variable. You never see the bookmark, but it is there. Every built-in container works this way: lists, tuples, sets, strings, dicts and deques. That is why one loop style works across many different containers.

Python iterators have no remove method. A list does not know which item the loop is on, so the safe way to delete while walking is to keep your own position and delete only at that position. The next example does it with a while loop.

The output is:

['bird', 'tree']

The variable i is the bookmark. When the word at i is short, the program deletes it, and the next word slides into slot i. The program does not move i forward in that case, so the next word is checked. When the word is long enough, the program moves i forward by one. This keeps every word checked exactly once.

The list comprehension [w for w in words if len(w) >= 4] gives the same result in one line, and it is usually the clearest choice when the test is simple. The while version is the one to use when you need more than deletion, such as stopping early or changing items as you go.

Why the for loop skips items

A Python list does not keep a count of its changes, so a for loop over a list does not notice when the list changes. Adding or removing items during the loop never raises an error. The loop simply uses the same position number as before, and the list now holds different items at that position.

Here are three versions of the same mistake, with the output of each:

The output is:

remove 2: [1, 3, 4]
remove 3: [1, 2, 4]
remove 4: [1, 2, 3]

When the loop removes 2, the number 3 slides into slot 1. The loop moves on to slot 2, which now holds 4, so 3 is never visited. The printed list is still correct here, because nothing else needed a check. When the loop removes 3, the 4 slides into slot 2, and the loop ends after it moves past the end. The 4 is never visited, but nothing bad happens. The third case removes the last item. The loop ends normally and the output looks fine.

These outputs look reasonable, which is why the bug is hard to spot. A test with a longer list may show the problem only at some positions. The rule for Python is simple: do not add or remove items from a list while a for loop reads it. If you need to delete, use a comprehension, an index loop that does not advance after a delete, or del on a saved list of positions.

Dicts and sets are different. They do keep a count of their changes, and Python raises an error as soon as a loop sees the change:

The output is:

caught: dictionary changed size during iteration

Dict loops fail loudly, which is easier to debug. List loops can fail silently, so read the rule above for lists.

The built-in helpers

Python has no separate helper class like Java's Collections. The helpers are plain functions and list methods. The program below uses the most common ones. Each call is written next to its result in the output.

The output is:

[1, 3, 4] 1
[4, 3, 1]
4 1
3
[1, 3, 4]
['ab', 'ab', 'ab']
[3, 4, 1]

The method sort changes the list into ascending order in place, and it returns None. The method index returns the position of the first 3, which is 1. The method reverse flips the order in place. The functions max and min return the largest and smallest values. The method count counts how many times 1 appears, which is 3. The swap of two items is one line with tuple unpacking, a, b = b, a. Multiplying a list by 3 makes a new list with three references to the same string, which is handy for setting up test data.

The last part shuffles a list in random order. The class random.Random(42) makes a random number generator with the seed 42, so the shuffle gives the same order every time you run it. Without a seed, the order would change on each run. The order that a seed produces depends on the Python version, so the output above is the result on Python 3.14.

A few more helpers are worth knowing. The function sorted(x) returns a new sorted list and leaves x as it was, while x.sort() changes x. The function reversed(x) returns an iterator that walks backwards. The function sum adds the numbers in a container. The bisect module searches a sorted list.

The bisect function has the same warning as the binarySearch helper in other languages. It only works on a sorted list. On an unsorted list it returns a position without any error, and that position is wrong. Sort first, or use a loop.

Immutable containers and read-only views

Python has three ways to make a container that cannot change, and each one fails in a different way.

A tuple is an immutable sequence, written with round brackets. You cannot assign to its items or add to it. Trying to change one raises TypeError: 'tuple' object does not support item assignment.

A frozenset is an immutable set. You cannot add to it or remove from it, so it can also be a dict key.

A read-only view of a dict is made with MappingProxyType from the types module. The view does not copy the data. If you change the original dict, the view shows the change, but you cannot change the view itself.

The output is:

{'a': 1, 'b': 2}
caught: 'mappingproxy' object does not support item assignment
{'a': 1, 'b': 2}

The first line shows the view picked up the new key b, because it is a view, not a copy. A read-only view protects the view from changes, but it does not protect the original dict from changes made through another name. The dict(source) line makes a true copy, which is a snapshot. The later change to source does not reach it.

Lists have no read-only view in the standard library. For a list that callers must not change, return a tuple made with tuple(items), or return a copy.

Choosing a container

Most mistakes in choosing a container come from thinking about the type first. Think about the operation first. Ask what you do most often. Reads by position? Adds at one end? Checks for membership? Sorted queries? The answer names the container.

A short decision path covers most cases. If the data has keys, think of a dict. If you need uniqueness, think of a set. If the order of removal matters, think of a deque, a stack or a heap. Otherwise, use a list.

Declare variables with the name that describes the job, such as recent or queue, and create them with the type that matches. The next program keeps the three most recent searches, newest first, and drops the oldest when the limit is exceeded. Read the code and decide, before you run it, which container each variable needs.

Save the program as a file. When it asks for input, type this, one line at a time:

5
rust
java
rust
go
python

from collections import deque
 
n = int(input())
recent = deque()
for _ in range(n):
    term = input().strip()
    if term in recent:
        recent.remove(term)
    recent.appendleft(term)
    if len(recent) > 3:
        recent.pop()
    print(list(recent))

The output is:

['rust']
['java', 'rust']
['rust', 'java']
['go', 'rust', 'java']
['python', 'go', 'rust']

The choice is a deque. Each new search goes to the front, and the oldest search falls off the back. That is the shape of a sliding window of history, which a deque does in O(1) per step. A list would work, but inserting at the front of a list costs O(n), and the choice would be a poor match for the job.

The third search, rust, is already in the deque. The check if term in recent finds it, and recent.remove(term) removes its old position first. Then appendleft moves it to the front. Without the check, remove would raise ValueError for a new term. The list therefore shows each term once, with the newest first. That detail, moving a repeat to the front instead of storing it twice, is the kind of rule an interviewer will ask you to state.

Notice the pop call. It removes the oldest term, which sits at the back. The deque size stays at three. The program never needs an index, so the deque is the cleanest structure for this job.

Walking through the decision

Here is how to reason about the recent-searches program when you have to choose from scratch, without seeing the answer. The first question is what the program does most. It adds at the front, removes from the back and sometimes removes a value in the middle. A list would support all of that, but adding at the front costs O(n). A deque is built for both ends, and it also has remove(value), so it covers every operation the program needs. So the deque wins, and the reason is in the operations, not in the name.

The second question is whether order matters. The output must be newest first, so order matters. A set would lose the order, so it cannot be the main structure, although a set could check for repeats. The third question is cost. The main work is at the ends, so each step is O(1), plus the remove(value) search, which is O(n) for a short list. For a list of three items, that search costs nothing noticeable.

This three-question habit works for almost every problem: what operations dominate, does order matter, and what does each operation cost. Practise saying the answer in that order.

How the bookmark works, step by step

An iterator over a list keeps a number that is the index of the next item to return. For a list of four items, the number starts at 0. Each call to next returns the item at that index and moves the index forward by one. The loop stops when the index reaches the end of the list. The loop checks the current length of the list only at that moment, so a removal that makes the list shorter can end the loop early, as the earlier examples showed.

Once you hold this picture, the trap makes sense. The loop's index is a number that assumes the list stays the same. A removal before the index moves the next item into a slot the loop has already passed. A removal at the index moves the next item into the slot the loop is about to read, which is also a skip. The safe patterns either avoid changing the list while they read it, or they change it only at a position they control.

Making your own type work with a for loop

Any class can work with a for loop if it defines the method __iter__. That method returns an iterator. The simplest way to write one is a generator, a function that uses yield to hand out one item at a time and pauses between items:

The output is:

[3, 2, 1]

The yield keyword sends one value out and remembers where the function stopped. The next time the loop asks for an item, the function continues from that point. The class does not need to store a list of values. This is why one loop style works on lists, sets, dicts, files and your own classes alike.

Replacing items during a walk

To change items while you walk, use the position. The enumerate function gives you the position and the item together, so you can assign to the list at that position. The next example replaces every empty string with a placeholder:

The output is:

['cat', '(none)', 'dog', '(none)']

Assigning to words[i] replaces one item and does not change the length of the list, so the loop is safe.

Removing from a dict, and returning safe containers

Dicts have the same removal trap as lists, and Python reports it with the RuntimeError shown earlier. The fix is to loop over a copy of the keys. For example, to drop every word whose count is below 2, write:

The output is:

{'to': 2, 'be': 2}

The call list(counts) makes a list of the keys before the loop starts. The loop reads that list, and the del changes the dict, which is safe because the loop is not reading the dict.

Returning a container from a function needs care too. If a method returns its internal list, the caller can change your data without going through your code. The fix is to return a copy or an immutable container. The line return tuple(items) gives the caller a tuple, so an attempt to add to it raises an error instead of silently changing your object. Return a copy when the caller must not affect your state. Say which one you chose in the function's docstring.

Sorting with more than one rule

sorted and list.sort use the natural order of the items, which is alphabetical for strings. To sort by one rule and break ties with a second rule, pass a key function that returns a tuple. Python compares tuples one item at a time.

The output is:

['fig', 'kiwi', 'pear', 'apple']
[('Delhi', 36), ('Pune', 33), ('Pune', 31)]

The first call sorts by length first and alphabetically inside each length. Starting from pear, fig, apple, kiwi, the first rule groups the words as fig (3), then kiwi and pear (4), then apple (5). The second rule puts kiwi before pear.

The second call sorts the records by city name, and for the same name it puts the higher temperature first. The minus sign in -r[1] reverses the order of the number only. Checking a key function against a small hand example like this is the fastest way to catch a rule that is reversed.

Three design cases

Interviewers often describe a situation and ask which container you would use. Practise naming the property first and the container second.

A leaderboard must show the top ten players as scores change. A heap of size ten answers "top ten" in O(log n) per change, and heapq.nlargest answers it once. A sorted list of scores with bisect also works when you need the next lower score too.

Unique search terms in the order typed need two properties at once. A set checks for repeats quickly, but it has no order. A dict keeps insertion order and uses its keys as a set, so one dict covers both needs.

A cache of recent pages must drop the least recently used page when it is full. collections.OrderedDict can move a key to the end when it is used, and popitem(last=False) removes the oldest. Without that feature, you would pair a deque for the order with a dict for the lookups.

Fail-fast: why the check exists

Some containers in other languages check for changes while you loop, and they fail at once. Python dicts and sets do this, and the error you saw earlier is the result. The check costs one comparison on each step, so it is cheap. It turns a silent corruption into a loud error, and the traceback points at the loop that broke. The aim is to make the bug visible early, while the traceback still shows the cause.

Lists do not do this check. That is why a loop over a list can skip items with no error. Treat the lack of an error as no guarantee. Fix the structure of the loop rather than hoping for an exception.

Reading a container's contract

Every built-in type has a clear contract. Before you use a function, read three things: what it returns when the container is empty, what it does with None, and whether the result is a copy or a view. Those three facts answer most of the surprises in this module. popleft raises IndexError for an empty deque. sorted returns a new list, and list.sort returns None. MappingProxyType is a view, and dict(x) is a copy.

When you write your own function that returns a container, write the same three facts in its docstring. A caller who reads them does not have to guess, and an interviewer will notice the habit.

Sorting records for a report

A common job is to sort a list of records by two fields. The key function from the earlier example does it in one line. For a report, the same pattern works with names: sorted(rows, key=lambda row: (row.city, -row.temp)), where each row is an object with those attributes. The rule is the same as before. Put the fields in the order of importance, and negate a number to reverse its order.

Reading the error messages in this module

Most errors tell you the cause in their name or in their message. This table matches each error you have met in this module with its usual cause and fix.

When an error appears, read it in three parts: the kind of problem, the value involved, and the place it happened. The traceback shows the place as its last frame that names your file. Start there, then trace the values by hand, as the debugging walkthroughs in this module did.

Common mistakes

Modifying a list inside a for loop. Build a new list with a comprehension, or use a while loop with an index that you control. Never change the list while the for loop reads it, because Python will not warn you.

Calling next on an iterator that is finished. It raises StopIteration. Use a for loop, or give next a default.

Using bisect on an unsorted list. It returns a position without any error, and that position is wrong. Sort first, or use a loop.

Expecting a view to be a copy. MappingProxyType shows later changes to the original. Use dict(...) for a true snapshot.

Choosing a deque for every queue-like job by reflex. A deque is best for two-end work. For a list you read by position, a list is better.

Forgetting the imports. deque and Counter come from collections, MappingProxyType from types, bisect and heapq are separate modules, and random is its own module. Each one needs an import line.

A debugging walkthrough: a list that loses items

A program is meant to remove all the short words from a list, keeping words of four letters or more. It loops with an index and calls pop. Running it stops with an error, so the final print never runs. Here is the loop:

words = ["a", "to", "bird", "be", "tree"]
for i in range(len(words)):
    if len(words[i]) < 4:
        words.pop(i)
print(words)

Trace the loop by hand. The list is ['a', 'to', 'bird', 'be', 'tree']. At i equal to 0, the word a is short, so pop(0) deletes it, and the list becomes ['to', 'bird', 'be', 'tree']. The loop moves to i equal to 1, which is now bird. It is not short, so nothing happens. The word to has moved to index 0, which the loop has already passed, so it is never checked. At i equal to 2, the word be is short and is removed. The list is ['to', 'bird', 'tree']. The loop then reaches i equal to 3 and the list has only three items, so the code raises an error. The last line of the traceback is the one that matters:

IndexError: list index out of range

The first short word is removed, the second is missed, and the loop then reads past the end. The skip is the bug: removing an item shifts the items after it to the left, and the loop moves on past the gap. The fix is to advance the index only when nothing was removed, as the while example did, or to write words = [w for w in words if len(w) >= 4].

The same removal written as a for loop over the list itself does not raise an error, but it still skips to, as the earlier example showed. The general lesson is that removing an item from a list shifts the items after it. Any loop that keeps a position must account for that shift, and the simplest way is to build a new list.

Variations and edge cases

An empty container is a valid input to every function here. max([]) raises ValueError: max() iterable argument is empty, so check if items: before you ask for the maximum.

A single item list is also valid. bisect returns the right position for a single item, and reverse does nothing.

A list with duplicates affects count, index and comprehensions that filter. The index method returns the position of the first match only. A comprehension with if drops every copy that matches the test, not only the first.

When you need to change items while walking, use enumerate and assign to the position, as the placeholder example did. The assignment does not change the length of the list, so the walk stays correct.

Interview-style and real-world uses

Interviewers ask about containers in two ways. The first is a direct question: "Which structure would you use for this?" The answer should name the operations first and the type second, as the decision walkthrough showed. The second is a trap question: "What does this loop print?" Look for changes to the list inside a for loop, and check whether the loop skips items. Those two patterns account for many interview bugs.

In real software, iterators are everywhere, even when you do not see them. A database cursor, a file reader and a network stream all work like iterators: they hand out one item at a time and remember their place. Understanding the bookmark idea makes all of them easier to use. A generator is the same idea in a function.

The built-in sorting and helper functions appear in production code. Sorting a list of records, reversing a history, finding the largest value and shuffling a deck of cards all use them. Returning a tuple from a function prevents callers from changing your data by accident, which removes one common kind of bug.

Practice

1. Remove all words shorter than 4 letters from a list with a comprehension. Then do the same with a while loop and an index, and explain why both give the same result.
2. You need the 10 most recent searches, newest first, dropping the oldest. Which container fits, and what do you add to and remove from? Explain in one sentence.
3. For each need, pick a container and give one reason: counting votes per candidate; checking whether a username is taken; a to-do list that must stay in the order it was written.
4. A function returns MappingProxyType(items). The caller stores it, and later you add a key to items. Does the caller see the new key? Why? How would you return a true snapshot?
5. Write a loop that removes every None from a list without a comprehension, using an index that does not advance after a delete. Explain why a for loop that deletes as it goes would skip items on the same task.
6. Predict the output of this code, then run it: items = [5, 6, 7], items.remove(6), print(items).
7. Write a function that takes a list of numbers and returns True if it is sorted in ascending order. Use an index loop. Explain why using bisect to check this would be a mistake.
8. A program stores each student's name and grade in a dict. What order does iteration produce? Write the line that prints the students in alphabetical order.
9. Write a program that reads numbers until it sees 0, stores them in a list, and then removes every number that appears more than once, keeping only the values that appear exactly once. Keep the original order.
10. Explain the difference between a list and a tuple in terms of what you can change: items, length, and the ability to add or remove. Give one case where each is the right choice.

Exercise 1. Show the answer:

words = ["cat", "bird", "to", "tree"]
a = [w for w in words if len(w) >= 4]
 
b = ["cat", "bird", "to", "tree"]
i = 0
while i < len(b):
    if len(b[i]) < 4:
        del b[i]
    else:
        i += 1

Both leave ['bird', 'tree']. The while loop deletes the item at the index it is on, and it moves forward only when it keeps the item, so it never skips one.

Exercise 2. Show the answer: a deque, with appendleft to add the newest search, and pop to remove the oldest from the back when the length passes 10. The operations are at the ends, so each step is O(1).

Exercise 3. Show the answer: votes per candidate, a dict mapping name to count, because you look up by name. A username taken, a set, because you only ask whether it is present. The to-do list, a list, because you keep the written order and access by position.

Exercise 4. Show the answer: yes, the caller sees the new key, because the view does not copy the dict. Return dict(items) for a snapshot, which is a copy that does not change when items changes.

Exercise 5. Show the answer:

i = 0
while i < len(items):
    if items[i] is None:
        del items[i]
    else:
        i += 1

A for loop that calls del on the current item moves every later item one slot to the left, so the item after each deletion is skipped and may still be None.

Exercise 6. Show the answer: the output is [5, 7]. The remove method deletes the first item equal to 6.

Exercise 7. Show the answer:

def is_sorted(items):
    for i in range(1, len(items)):
        if items[i - 1] > items[i]:
            return False
    return True

bisect assumes the list is sorted, so it cannot be used to verify sorting. On an unsorted list it returns a position without warning, and that position says nothing about whether the list is sorted.

Exercise 8. Show the answer: a dict prints in the order its keys were added, which may not be alphabetical. Print in alphabetical order with for name in sorted(grades): print(name, grades[name]).

Exercise 9. Show the answer:

from collections import Counter
 
nums = []
v = int(input())
while v != 0:
    nums.append(v)
    v = int(input())
 
counts = Counter(nums)
print([x for x in nums if counts[x] == 1])

The comprehension keeps the original order, because it reads the list from start to end and never reorders the items.

Exercise 10. Show the answer: a list can change its items, its length, or both. A tuple cannot change at all. Use a list for a collection that grows or changes, such as the messages in a chat window. Use a tuple for a fixed record, such as a point (x, y), or for data a function returns that callers must not change.

What you now know

• An iterator is a bookmark. iter, next and for walk a container one item at a time.
• Changing a list while a for loop reads it can skip items with no error. Build a new list or use a while loop with an index instead.
• Dicts and sets raise RuntimeError when their size changes during a loop. Loop over list(d) to change a dict safely.
• sort and sorted order items. bisect needs sorted input, and it does not check.
• A tuple cannot change, MappingProxyType is a view rather than a copy, and dict(x) makes a true snapshot.
• Choose a container by the operations you do most, whether order matters and what each operation costs.