Unit 2: Python data structures

I. Orientation — Organizing and manipulating data

Python data structures store collections of values and provide operations for accessing, updating, searching, and combining them. The appropriate structure depends on whether data must preserve order, allow mutation, eliminate duplicates, or associate keys with values.

A. Defining properties and conventions

Python’s built-in structures share a common object model but differ in organization and permitted operations.

• Sequence: A sequence stores elements in a defined order. Strings, lists, and tuples support zero-based indexing, negative indexing, slicing, iteration, and len().
  • sequence[0] accesses the first element.
  • sequence[-1] accesses the last element.
  • sequence[start:stop:step] returns elements from start up to, but not including, stop.
• Mutability: A mutable object can change after creation; an immutable object cannot.
  • Lists, sets, and dictionaries are mutable.
  • Strings and tuples are immutable.
• Membership: The operators in and not in test whether an element, character, or key is present.

3 in [1, 2, 3]           # True
"py" in "python"         # True
"name" in {"name": "Ada"}  # True

• Iteration: A for loop processes collection elements one at a time. Dictionary iteration processes keys unless another view is specified.
• Heterogeneous values: Lists, tuples, sets, and dictionaries may contain values of different types, although consistent types often make programs clearer.
• Hashability: Set elements and dictionary keys must be hashable, meaning they have a stable hash value during their lifetime. Numbers, strings, and suitable tuples are hashable; lists, sets, and dictionaries are not.
• Copying and aliasing: Assignment normally creates another reference to the same mutable object rather than an independent copy.

a = [1, 2]
b = a
b.append(3)       # Both a and b now refer to [1, 2, 3]
c = a.copy()      # c is a shallow independent copy

II. Strings — Immutable sequences of text

A string is an immutable sequence of Unicode characters, created with single, double, or triple quotation marks.

A. Strings

Strings support indexed access, slicing, searching, transformation, formatting, and many sequence operations.

• Creation: Single and double quotes create equivalent one-line strings; triple quotes can contain multiple lines.

language = "Python"
message = 'Data structures'
multiline = """first line
second line"""

• Indexing and slicing: For text = "Python", text[0] is "P", text[-1] is "n", and text[1:4] is "yth". A slice outside the available range is safely truncated, but an invalid single index raises IndexError.
• Immutability: Character assignment is prohibited because a string cannot be modified in place. A transformed string must be assigned as a new object.

word = "cat"
word = "b" + word[1:]    # "bat"

• Concatenation and repetition: + joins strings, while * repeats them. Both operations create new strings: "Py" + "thon" produces "Python", and "ha" * 3 produces "hahaha".
• Common methods: String methods return results without changing the original.
  • lower() and upper() change letter case in the returned value.
  • strip() removes characters, whitespace by default, from both ends.
  • replace(old, new) substitutes occurrences.
  • find(substring) returns the first index or -1; count(substring) counts non-overlapping occurrences.
  • split(separator) produces a list, while separator.join(iterable) combines strings.
• Formatting: An f-string embeds expressions inside braces and supports format specifications.

name = "Mina"
score = 92.5
report = f"{name} scored {score:.1f}%"

• Escapes and raw strings: \n represents a newline and \t a tab. A raw string such as r"C:\new" treats most backslashes literally.

B. Applications and limitations

Strings are appropriate for textual data, but repeated reconstruction may be inefficient.

• Text processing: Input validation, file content, labels, and messages rely on operations such as split(), strip(), and membership testing.
• Efficient assembly: Joining a collection is generally preferable to repeated + operations in a large loop because strings are immutable.

parts = ["Python", "data", "structures"]
title = " ".join(parts)   # "Python data structures"

• Type distinction: "12" is text, not the integer 12; explicit conversion such as int("12") is required for arithmetic.

III. Lists — Mutable ordered collections

A list is a mutable sequence that preserves insertion order, permits duplicate values, and can grow or shrink dynamically.

A. Lists

Lists are designed for collections whose elements or ordering may need to change.

• Creation and access: Square brackets create a list. Indexing and slicing follow sequence rules.

scores = [78, 91, 84, 91]
first = scores[0]       # 78
middle = scores[1:3]    # [91, 84]

• Mutation: An indexed element or slice can be replaced. scores[0] = 80 changes the existing list.
• Adding elements:
  • append(value) adds one value at the end.
  • extend(iterable) adds every element from an iterable.
  • insert(index, value) places a value before a specified position.
• Removing elements:
  • remove(value) removes the first matching value and raises ValueError if absent.
  • pop(index) removes and returns an element; without an index, it uses the last element.
  • clear() removes all elements, while del items[index] deletes by position.
• Ordering: sort() changes a list in place; sorted(iterable) creates a new sorted list. Both accept reverse=True and a key function.

names = ["Lin", "Alexandra", "Bo"]
names.sort(key=len)      # ["Bo", "Lin", "Alexandra"]

• List comprehensions: A comprehension builds a list from an iterable, optionally filtering values.

squares = [n * n for n in range(6) if n % 2 == 0]
# [0, 4, 16]

• Nested lists: A list may contain other lists; matrix[1][0] accesses row 1, column 0.

B. Applications and limitations

Lists suit ordered, changeable data but are not optimized for every form of lookup.

• Typical uses: Lists represent queues of tasks, sequences of measurements, table rows, or collections assembled incrementally.
• Membership cost: Testing value in items may inspect elements from left to right, giving linear-time behavior in the worst case.
• Shallow copying: copy(), list(source), and source[:] copy the outer list, but nested mutable objects remain shared.
• Safe construction: [[] for _ in range(3)] creates three separate inner lists; [[]] * 3 repeats references to the same inner list.

IV. Sets — Unordered collections of unique values

A set is a mutable collection of distinct hashable elements, primarily used for membership testing and mathematical set operations.

A. Sets

Sets automatically eliminate duplicates and do not provide positional indexing or slicing.

• Creation: {1, 2, 3} creates a nonempty set, but an empty set requires set() because {} creates an empty dictionary.
• Uniqueness: set([2, 1, 2, 3]) produces a set containing 1, 2, and 3; display order should not be treated as meaningful.
• Modification: add(value) inserts one element, while update(iterable) inserts multiple elements. remove(value) raises KeyError if absent, whereas discard(value) does not.
• Set algebra: For sets A and B, Python provides:
  • A | B: union, containing elements in either set.
  • A & B: intersection, containing elements in both.
  • A - B: difference, containing elements in A but not B.
  • A ^ B: symmetric difference, containing elements in exactly one set.
• Relationships: A <= B tests whether A is a subset of B; A >= B tests whether it is a superset. isdisjoint() checks whether two sets share no elements.
• Set comprehensions: A set can be generated with an expression and optional condition.

remainders = {n % 3 for n in range(10)}
# {0, 1, 2}

B. Applications and limitations

Sets are effective when uniqueness and fast average-case membership testing matter more than position.

• Deduplication: unique = set(values) removes repeated values, although original order is not guaranteed by the set abstraction.
• Comparison: If registered and attended are sets, registered - attended identifies registered people who did not attend.
• Restrictions: A set cannot directly contain a list because lists are unhashable. A tuple may be an element only when all its components are hashable.
• Immutable variant: frozenset() creates an immutable, hashable set suitable for use as a dictionary key or as an element of another set.

V. Tuples — Immutable ordered records

A tuple is an immutable sequence commonly used to group a fixed number of related values.

A. Tuples

Tuples support sequence operations while preventing structural changes after creation.

• Creation: Parentheses are conventional, but commas create the tuple. A one-element tuple requires a trailing comma: (5,).
• Access: Indexing, slicing, iteration, membership, len(), count(), and index() work as they do for other sequences.
• Packing and unpacking: Values can be grouped and assigned to multiple variables.

point = (4, 7)
x, y = point

• Extended unpacking: A starred target receives remaining elements: first, *middle, last = (1, 2, 3, 4) assigns [2, 3] to middle.
• Immutability boundary: Tuple positions cannot be reassigned, but a mutable object stored inside a tuple can still change.

record = ("A", [10, 20])
record[1].append(30)     # Allowed: inner list becomes [10, 20, 30]

• Returning values: A function can return comma-separated values as a tuple, allowing direct unpacking by the caller.

B. Applications and limitations

Tuples communicate fixed structure and can provide hashable compound values.

• Records: Coordinates such as (latitude, longitude) and RGB colors such as (255, 128, 0) have stable positions and fixed lengths.
• Dictionary keys: (row, column) can be a key because a tuple of integers is hashable.
• Limited updating: Changing one field requires creating a new tuple, so classes, named tuples, or dictionaries may be clearer for records with many fields.

VI. Dictionaries — Mutable key-value mappings

A dictionary maps unique hashable keys to values and preserves insertion order in modern Python.

A. Dictionaries

Dictionaries retrieve values by meaningful keys rather than numeric positions.

• Creation and access: Key-value pairs use key: value syntax.

student = {"name": "Asha", "score": 88}
name = student["name"]

• Missing keys: Bracket access raises KeyError for an absent key. student.get("grade", "N/A") safely returns the default "N/A".
• Mutation: Assignment adds or updates a pair: student["score"] = 91. update() merges supplied pairs, replacing values for existing keys.
• Removal: pop(key) removes and returns a value; popitem() removes and returns the most recently inserted pair; del mapping[key] removes a specified entry.
• Views and iteration:
  • keys() provides a dynamic view of keys.
  • values() provides a dynamic view of values.
  • items() provides (key, value) tuples.

for key, value in student.items():
    print(key, value)

• Dictionary comprehensions: Expressions can generate mappings concisely.

squares = {n: n * n for n in range(4)}
# {0: 0, 1: 1, 2: 4, 3: 9}

• Key rules: Keys must be unique and hashable. Assigning an existing key replaces its value rather than creating a duplicate entry.

B. Applications and limitations

Dictionaries suit labelled records, indexes, counters, and lookup tables.

• Structured data: A dictionary such as {"title": "Python", "pages": 320} associates each value with a descriptive label.
• Counting: Frequencies can be accumulated with counts[item] = counts.get(item, 0) + 1.
• Average performance: Lookup, insertion, and deletion by key are typically constant-time operations, though worst-case behavior can differ.
• Nested mappings: Dictionaries can contain lists or other dictionaries, but deeply nested structures require careful missing-key handling.
• Ordering distinction: Insertion order is preserved, but a dictionary is still a mapping; values should be retrieved by keys rather than treated as positional fields.