Data Structures

The four built-in collections - lists, tuples, dictionaries, and sets - and how their behaviour differs based on whether they are mutable.

Lists

A list is an ordered, mutable collection.

Creating and indexing

lst = ['a', 'b', 'c', 'd', 'e']
#       0    1    2    3    4
#      -5   -4   -3   -2   -1

lst[0]      # → 'a'
lst[-1]     # → 'e'
lst[1:3]    # → ['b', 'c']      (1 inclusive, 3 exclusive)
lst[:2]     # → ['a', 'b']      (start up to 2)
lst[3:]     # → ['d', 'e']      (3 to the end)
lst[-2:]    # → ['d', 'e']      (last 2)

Methods that change the list (return None)

lst.append(item)   adds to the end
lst.remove(item)   removes first occurrence
lst.sort()         sorts ascending
lst.reverse()      reverses the order
lst.pop()          removes + RETURNS the last item
lst.pop(0)         removes + returns the item at index 0

Methods that return a value (change nothing)

lst.count(item)    counts how often item occurs
lst.index(item)    returns index of the first occurrence

Functions (not methods - they stand alone)

len(lst)    number of elements
sum(lst)    sum (numbers only)
min(lst)    smallest
max(lst)    largest

Watch the syntax: it is len(lst), not lst.len(); and lst.append(5), not append(lst, 5).

Try it yourself

lst = [5, 2, 8, 1, 9, 3]
print(lst.pop())       # What comes out? What is lst afterwards?
print(lst)
lst.sort()
print(lst)             # Sorted?
print(lst.index(8))    # Where is 8 now?
print(lst.count(2))    # How often does 2 occur?

# The reference experiment again:
a = [1, 2, 3]
b = a
c = a.copy()
a.append(4)
print("b =", b)        # What do you expect?
print("c =", c)        # And here?

Under the hood: how sort() compares values

This is more than you strictly need, but it explains the surprising results you sometimes get from sort().

Numbers carry value on their own - like money. Two euros is worth less than five, which is worth less than ten, so a computer can line them up without any extra information: 2, 5, 10.

Letters do not carry value on their own. So the computer gives every character a fixed number - its code point (the ASCII / Unicode value). When you sort text, the computer is really sorting those numbers. We call it “alphabetical” for convenience, but underneath it is pure number comparison. Money is just a thing we invented to put a value on goods; code points do the same job for characters.

You can look up a character’s value with ord(), and go back with chr():

ord('A')   # → 65
ord('Z')   # → 90
ord('a')   # → 97
ord('z')   # → 122
ord('0')   # → 48
ord('9')   # → 57
chr(66)    # → 'B'

Notice the ranges. Because digits (48-57) come before uppercase (65-90), which come before lowercase (97-122), the ordering is:

digits  <  UPPERCASE  <  lowercase
'0'-'9'    'A'-'Z'        'a'-'z'

So uppercase and digit-strings always sort before ordinary lowercase letters:

words = ["banana", "Apple", "cherry", "Date"]
words.sort()
print(words)   # ['Apple', 'Date', 'banana', 'cherry']
#                 'A'=65, 'D'=68  come before  'b'=98, 'c'=99

Comparison operators (<, >) use the exact same values, character by character:

'a' < 'b'    # → True   (97 < 98)
'Z' < 'a'    # → True   (90 < 97, so any capital beats any lowercase)
'apple' < 'banana'  # → True  (compares 'a' vs 'b' first)

This also explains the classic numbers-as-strings trap:

nums = ["10", "2", "1", "21"]
nums.sort()
print(nums)    # ['1', '10', '2', '21']   ← not numeric order!

It compares the first character first: '1' (49) beats '2' (50), so every string starting with '1' comes before every string starting with '2'. To sort by real numeric value, convert to int first (e.g. sorted(nums, key=int)).

Tuples

Tuples are “frozen lists” - immutable.

t = (1, 2, 3)
t[0]          # → 1   (indexing works)
t[0] = 99     # → TypeError (cannot change)

They only have count() and index() - no append, remove, etc. Tuples are often used for coordinates, dates, or as dictionary keys.

Dictionaries

A dictionary stores key/value pairs and is mutable.

Creating and using

student = {'name': 'Jan', 'age': 22, 'course': 'ICT'}

student['name']             # → 'Jan'   (look up a value)
student['email'] = 'j@hu.nl'  # add a new pair
student['age'] = 23         # change an existing value

Methods

d.keys()       all keys (as a view)
d.values()     all values (as a view)
d.items()      all (key, value) pairs (as a view)
d.pop(key)     removes a pair, returns the value
d.update(d2)   merges another dict in / overwrites

Iterating

for key in student:
    print(key, "→", student[key])
# name → Jan
# age → 23
# course → ICT

for key, value in student.items():
    print(key, "→", value)
# same output, but cleaner

Dictionary as a counter

A very common pattern - counting occurrences:

text = "abracadabra"
counts = {}
for letter in text:
    if letter in counts:
        counts[letter] += 1
    else:
        counts[letter] = 1
print(counts)  # {'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1}

KeyError

student['phone']  # → KeyError (key does not exist)

Try it yourself

Build a word counter:

sentence = "the cat sat on the mat"
counter = {}
for word in sentence.split():
    if word in counter:
        counter[word] += 1
    else:
        counter[word] = 1
print(counter)
# How many times does "the" occur?

Sets

Unordered, no duplicates, only immutable elements.

s = {1, 2, 3, 2, 1}   # → {1, 2, 3}

# Strings are fine as elements:
names = {"Jan", "Piet", "Jan"}   # → {"Jan", "Piet"}

Operations

a = {1, 2, 3}
b = {3, 4, 5}

a.union(b)         # → {1, 2, 3, 4, 5}   (all elements)
a.intersection(b)  # → {3}               (in common)
a.difference(b)    # → {1, 2}            (in a but not b)
b.difference(a)    # → {4, 5}            (in b but not a)
a.issubset(b)      # → False

Remember: {} is an empty dict, not an empty set. An empty set is set().

Try it yourself

class_a = {"Jan", "Piet", "Kees", "Anna"}
class_b = {"Anna", "Bert", "Kees", "Dirk"}

print(class_a.intersection(class_b))  # Who is in both classes?
print(class_a.difference(class_b))    # Who is only in A?
print(class_a.union(class_b))         # All unique names?

Mutability overview

Type        Mutable?   Example       Methods change the object?
─────────────────────────────────────────────────────────────────
int         No         42             -
float       No         3.14           -
bool        No         True           -
str         No         "hello"        No (return a copy)
tuple       No         (1, 2, 3)      No
list        Yes        [1, 2, 3]      Yes (append, sort, etc.)
dict        Yes        {'a': 1}       Yes (update, pop, etc.)
set         Yes        {1, 2, 3}      Yes (add, remove, etc.)