Data Structures and Algorithms | Learn Python by Running It

Choosing a data structure

A data structure is a way to arrange information so that a task is simple to perform. A list keeps an order. A dictionary connects a key to a value. A set remembers whether a value has appeared.

Do not start with the most advanced structure. Start by asking what the program needs to do often: keep order, look up a value, or avoid duplicates.

That question matters because the wrong structure can make a solution harder to read without making it any better. The right structure usually follows the task naturally.

EXAMPLE

names = ["Ari", "Bea"]
scores = {"Ari": 8, "Bea": 10}
seen = {"Ari"}

print(names[0])
print(scores["Bea"])
print("Ari" in seen)

Output will appear here.

Pause after running the example and explain each line in your own words. Notice what the program reads, what it stores, and what it prints, then make one small change and run it again to see exactly what changed.

Practice

Work through the same idea a few times so it starts to feel familiar. Begin by copying the example, then make the single change the instruction asks for, and finally explain to yourself why the result changed.

Create a list, dictionary, and set exactly like the lesson example.

EXERCISE

Output will appear here.

Add one item to the list.

EXERCISE

Output will appear here.

Predict which structure answers `"Ari" in seen`.

EXERCISE

Output will appear here.

Store two scores in a dictionary and print one score by name.

EXERCISE

Output will appear here.

Linear search

Linear search checks one item at a time from the beginning. It is a useful first solution because it is easy to trace and works on any list, sorted or unsorted.

The index changes on each pass through the loop. A common mistake is returning False after checking only the first item; the return belongs after the loop when no match was found.

This is the kind of solution you often write before you optimize. It gives you a correct baseline and helps you understand the problem before you try anything more advanced.

EXAMPLE

def find_index(items, target):
    for index, item in enumerate(items):
        if item == target:
            return index
    return -1

print(find_index([4, 9, 2], 9))

Output will appear here.

Pause after running the example and explain each line in your own words. Notice what the program reads, what it stores, and what it prints, then make one small change and run it again to see exactly what changed.

Practice

Work through the same idea a few times so it starts to feel familiar. Begin by copying the example, then make the single change the instruction asks for, and finally explain to yourself why the result changed.

Run `find_index([4, 9, 2], 9)`.

EXERCISE

Output will appear here.

Change the target from 9 to 2.

EXERCISE

Output will appear here.

Predict the result when the target is 8.

EXERCISE

Output will appear here.

Search your own three-item list for its first item.

EXERCISE

Output will appear here.

Counting with dictionaries

A dictionary can count repeated values. Each word becomes a key and its count becomes the value. This pattern appears in anagrams, frequency questions, duplicate checks, and many interview questions that ask for a summary of the input.

Use .get(word, 0) when a key might not exist yet. It gives a starting count of zero instead of raising a KeyError.

Once you see this pattern, you will notice it again and again. It is one of the clearest examples of how a dictionary can turn repeated items into useful information.

EXAMPLE

def count_words(words):
    counts = {}
    for word in words:
        counts[word] = counts.get(word, 0) + 1
    return counts

print(count_words(["red", "blue", "red"]))

Output will appear here.

Pause after running the example and explain each line in your own words. Notice what the program reads, what it stores, and what it prints, then make one small change and run it again to see exactly what changed.

Practice

Work through the same idea a few times so it starts to feel familiar. Begin by copying the example, then make the single change the instruction asks for, and finally explain to yourself why the result changed.

Run `count_words(["red", "blue", "red"])`.

EXERCISE

Output will appear here.

Add another `"blue"` to the list.

EXERCISE

Output will appear here.

Predict the count for a word that appears once.

EXERCISE

Output will appear here.

Count three fruit names, with one repeated.

EXERCISE

Output will appear here.

Stacks

A stack keeps the most recently added item at the top. In Python, a list can act as a stack with append and pop, which makes the structure easy to test quickly.

Before calling pop, check that the stack has an item. Trying to pop from an empty list is a common source of errors in bracket-matching problems.

Stacks show up in more places than bracket checking. They are also useful when you need to remember recent decisions or reverse a sequence of actions.

EXAMPLE

stack = []
stack.append("first")
stack.append("second")

print(stack.pop())
print(stack)

Output will appear here.

Pause after running the example and explain each line in your own words. Notice what the program reads, what it stores, and what it prints, then make one small change and run it again to see exactly what changed.

Practice

Work through the same idea a few times so it starts to feel familiar. Begin by copying the example, then make the single change the instruction asks for, and finally explain to yourself why the result changed.

Create an empty list, append `"first"` and `"second"`, then pop once.

EXERCISE

Output will appear here.

Append `"third"` before popping.

EXERCISE

Output will appear here.

Predict which item `pop()` returns.

EXERCISE

Output will appear here.

Use a list as a stack for three short tasks, then pop them.

EXERCISE

Output will appear here.

Two pointers

Two pointers are two positions that move through a sequence. They are helpful when the answer depends on items near both ends, such as a palindrome check, or when you want to compare two moving positions instead of every possible pair.

Give each pointer a clear job. Here, left moves right and right moves left after a successful comparison. Stop when they meet or cross.

The strength of this pattern is that it narrows the work quickly while still staying easy to trace by hand.

EXAMPLE

def is_palindrome(text):
    left, right = 0, len(text) - 1
    while left < right:
        if text[left] != text[right]:
            return False
        left += 1
        right -= 1
    return True

print(is_palindrome("radar"))

Output will appear here.

Pause after running the example and explain each line in your own words. Notice what the program reads, what it stores, and what it prints, then make one small change and run it again to see exactly what changed.

Practice

Work through the same idea a few times so it starts to feel familiar. Begin by copying the example, then make the single change the instruction asks for, and finally explain to yourself why the result changed.

Run `is_palindrome("radar")`.

EXERCISE

Output will appear here.

Replace `radar` with `robot`.

EXERCISE

Output will appear here.

Predict the result for `"level"`.

EXERCISE

Output will appear here.

Test two words of your choice and print both results.

EXERCISE

Output will appear here.

Tracing an algorithm

Before optimizing, trace the algorithm with a tiny input. Write the value of each variable after every loop step. This makes off-by-one mistakes easier to see and helps you notice where your expectation and the code diverge.

This small explorer is not Python execution. It is a way to practice reading the steps a program takes before you write one yourself.

If you can explain a solution with pencil-and-paper steps, you are in a much better position to improve it or debug it later.

Trace the programMove the value, then play through each branch or loop step.

Value: 3

value is below 5
take the else branch

Pause after running the example and explain each line in your own words. Notice what the program reads, what it stores, and what it prints, then make one small change and run it again to see exactly what changed.

Practice

Work through the same idea a few times so it starts to feel familiar. Begin by copying the example, then make the single change the instruction asks for, and finally explain to yourself why the result changed.

Set the explorer to `for loop` and value 3, then press play trace.

EXERCISE

Output will appear here.

Change the value to 5 and press play trace again.

EXERCISE

Output will appear here.

Before pressing play, predict how many loop steps appear.

EXERCISE

Output will appear here.

Use the explorer’s `while loop` view and describe its stopping step in a code comment.

EXERCISE

Output will appear here.