Programming Concepts

Foundational Data Structures~20 min

Sets and Uniqueness

A set holds unique values with no meaningful order, and answers "have I seen this before?" fast no matter how large it grows.

By the end of this lesson, you can

  • Explain what makes a set different from a list — no duplicates, no order, fast membership testing
  • Use a set to remove duplicates from a collection and to test membership
  • Choose a set over a list when a problem is really about uniqueness or membership, not order

Why it matters

Some problems aren’t really about order or key-value lookup — they’re about whether something has already been seen. “Has this email address signed up before?” “What are the distinct tags across every post?” A list can answer these questions, but it does so slowly and awkwardly once it grows large. A set is built for exactly this shape of problem.

Mental model

A set is a collection with two guarantees a list doesn’t make: every value in it is unique — adding a duplicate has no effect — and checking “is this value in here?” stays fast no matter how large the set grows. In exchange, a set gives up the two things a list is good at: order, and access by position. (len() is a built-in function that returns how many items any collection holds — a list, a set, later a dictionary.)

PythonDuplicates collapse automatically
seen = set()
seen.add("ada")
seen.add("grace")
seen.add("ada")

print(seen)
print(len(seen))
Output
{'ada', 'grace'}
2

The second "ada" had no effect — a set can’t hold the same value twice. set(some_list) is also the quickest way to remove duplicates from an existing list.

Trace it

Building a set from a list with duplicate names
Operationseen
start: seen = set(){} (empty set)
seen.add("ada"){'ada'}
seen.add("grace"){'ada', 'grace'}
seen.add("ada"){'ada', 'grace'} — unchanged

Compare that to checking membership in a list versus a set:

PythonSame question, two structures
names_list = ["ada", "grace", "linus"]
names_set = {"ada", "grace", "linus"}

print("grace" in names_list)
print("grace" in names_set)
Output
True
True

Both give the same answer here — but in on a list has to check items one by one until it finds a match or reaches the end, so it gets slower as the list grows. in on a set stays fast regardless of size, which is the entire reason to reach for one when membership testing is the actual problem.

Check your understanding

What does this print? tags = set() tags.add("python") tags.add("beginner") tags.add("python") print(len(tags))
Or reveal the answer without checking

Answer:2
The second tags.add("python") has no effect, since "python" is already in the set — sets never hold duplicates. Two unique values remain.

You need to track which usernames have already registered, and only ever check whether a given name is taken. Which structure fits best?
Or reveal the answer without checking

Answer:A set, since the only operation that matters is membership testing, not order
Since order was never part of the requirement — only 'has this name been used?' — a set models the problem directly and keeps membership checks fast as the number of usernames grows.

Practice: warm-up

Trace this program by hand — write down the contents of unique_words after each line — before revealing the answer.

unique_words = set()
unique_words.add("cat")
unique_words.add("dog")
unique_words.add("cat")
unique_words.add("bird")

Stuck? Reveal one hint at a time.

  1. Hint 1

    Each .add() either introduces a new value or has no effect at all, depending on whether that value is already present.

  2. Hint 2

    The second "cat" is the one to watch closely.

Reveal the trace

Try the problem yourself before reading this. There is often more than one reasonable approach — treat this as one worked example, not the only correct answer.

start:                unique_words = {}          (empty set)
add("cat")            unique_words = {'cat'}
add("dog")            unique_words = {'cat', 'dog'}
add("cat")            unique_words = {'cat', 'dog'}   (unchanged — already present)
add("bird")           unique_words = {'cat', 'dog', 'bird'}

Practice: apply it

This code checks whether each new order ID has already been processed, using a list that grows over time:

processed = []

def process_order(order_id):
    if order_id in processed:
        return False
    processed.append(order_id)
    return True
As processed grows to contain thousands of order IDs, what happens to each call to process_order?
Or reveal the answer without checking

Answer:Each call gets slower, since order_id in processed has to check items one by one against a growing list
Membership testing on a list is proportional to its size — as processed grows, each in check has more items to compare against, one at a time.

Modification challenge: rewrite process_order using a set instead of a list for processed, so membership testing stays fast regardless of how many orders have been processed.

Summary

  • A set holds unique values with no meaningful order — adding a duplicate has no effect.
  • Membership testing (in) on a set stays fast as it grows; on a list, it gets slower because each item is checked one by one.
  • set(some_list) is a quick way to remove duplicates from an existing list.
  • Choose a set when a problem is really about uniqueness or membership — never when order or position matters.

Key terms