Unit 3: String, Lists, Tuples and Dictionaries

I. Orientation: Compound Data Types in Python

A compound data type is one whose values are built from smaller pieces, each accessible individually. Python's core compound types — str, list, tuple, dict — differ along two axes: whether elements are ordered by integer index or keyed, and whether the object is mutable (can be changed in place) or immutable.

• Sequence types: str, list, tuple — support indexing s[i], slicing s[i:j], len(), in, +, *, and iteration by for.
• Mapping type: dict — unordered by design (insertion-ordered since Python 3.7), accessed by key rather than position.
• Mutability split:
  • Immutable: str, tuple — every "modification" builds a new object.
  • Mutable: list, dict — modified in place; the identity (id()) survives the change.
• Zero-based indexing: the first element is at index 0, the last at len(s)-1; negative indices count backwards, s[-1] being the last.
• Aliasing consequence: assignment copies a reference, not the object; mutable objects therefore show side effects across names, immutable ones cannot.

II. Strings — the Immutable Character Sequence

A. String a compound data type

A string is a sequence of characters, and unlike an integer it can be decomposed.

• Element access: fruit = "banana"; letter = fruit[1] gives 'a', not 'b' — indexing starts at 0.
• Character type: Python has no separate char type; fruit[0] is itself a one-character string.
• Immutability: fruit[0] = 'B' raises TypeError: 'str' object does not support item assignment. Build instead: 'B' + fruit[1:] → "Banana".

B. Length

len() returns the number of characters.

fruit = "banana"
len(fruit)          # 6
last = fruit[len(fruit)-1]   # 'a'   -- fruit[6] would be IndexError

• Off-by-one rule: valid indices are 0 … len(s)-1; s[-1] is the idiomatic last element.

C. String traversal

Traversal means visiting each character in turn.

• Index-based (while):
  
  PYTHON

    i = 0
    while i < len(fruit):
        print(fruit[i]); i += 1

• Element-based (for): for ch in fruit: print(ch) — no index bookkeeping, no IndexError risk.
• Traversal with both: for i, ch in enumerate(fruit) yields (0,'b'), (1,'a'), ….

D. String slices

A slice extracts a substring using s[start:end], including start and excluding end.

s = "Monty Python"
s[0:5]     # 'Monty'
s[6:12]    # 'Python'
s[:5]      # 'Monty'   (start omitted -> 0)
s[6:]      # 'Python'  (end omitted -> len(s))
s[:]       # whole string
s[::-1]    # 'nohtyP ytnoM'  (step -1, reversal)

• Empty slice: s[3:3] → ''; also s[5:2] → '' when start ≥ end.
• Length identity: len(s[i:j]) == j - i for in-range indices.

E. Comparison

Strings compare with the same operators as numbers, using lexicographic order on Unicode code points.

• Equality: "apple" == "apple" → True.
• Ordering: "apple" < "banana" → True, because 'a'(97) < 'b'(98).
• Case trap: all uppercase letters precede all lowercase ('Z'=90 < 'a'=97), so "Zebra" < "apple" is True. Normalise with .lower() before ordering words.

F. Find function

A find returns the index of the first occurrence of a character or substring, or -1 if absent — a generalisation of traversal.

def find(s, ch, start=0):
    i = start
    while i < len(s):
        if s[i] == ch:
            return i
        i += 1
    return -1           # sentinel for "not found"

• Built-in equivalent: "banana".find("na") → 2; "banana".rfind("na") → 4.
• find vs index: find returns -1 on failure; str.index raises ValueError.

G. Looping and counting

Counting is the canonical accumulator pattern: initialise, traverse, increment, report.

count = 0
for ch in "banana":
    if ch == 'a':
        count += 1
print(count)        # 3   -- same as "banana".count('a')

• Accumulator variable: count must be initialised outside the loop, or it resets each pass.

III. Lists — the Mutable Sequence

A. List values

A list is a comma-separated sequence of values in square brackets, of any types, including other lists.

• Heterogeneous: [10, "spam", 3.14, True] is legal.
• Nested: ["hi", 2, [5, 6]] — a list is itself a value.
• Empty list: [], whose len is 0 and which is falsy in boolean context.

B. Length

• len([1, 2, 3]) → 3; len(["hi", 2, [5, 6]]) → 3, because the inner list counts as one element.
• Range idiom: for i in range(len(lst)) gives every legal index.

C. Membership

• in / not in: 3 in [1,2,3] → True; "x" not in ["a","b"] → True.
• Cost: in on a list is a linear scan, O(n); on a dict it is O(1) hash lookup.

D. Operations

• Concatenation +: [1,2] + [3,4] → [1,2,3,4]; both operands must be lists.
• Repetition *: [0] * 4 → [0,0,0,0]; [1,2] * 2 → [1,2,1,2].
• In-place methods: append(x) adds one element, extend([...]) adds each element of an iterable, sort() reorders in place and returns None.

E. Slices

• t = ['a','b','c','d','e','f']; t[1:3] → ['b','c']; t[:4] → first four; t[3:] → last three.
• Slice assignment (lists only): t[1:3] = ['x','y','z'] replaces two elements with three, growing the list.
• Copy idiom: t[:] produces a new list with the same elements — a shallow copy.

F. Deletion

• del by index: del t[1] removes 'b'.
• del by slice: del t[1:5] removes a whole run.
• pop: x = t.pop(0) removes and returns; t.pop() removes the last.
• remove: t.remove('c') deletes by value, first match only; raises ValueError if absent.

G. Accessing elements

• Index: t[0], t[-1]; a non-integer index raises TypeError, an out-of-range one IndexError.
• Assignment: t[0] = 'A' is legal — the defining difference from strings.

H. List and for loops

for item in ["cheddar", "brie", "gouda"]:
    print(item.upper())

• Update inside a loop: modification needs the index — for i in range(len(nums)): nums[i] = nums[i] * 2.
• List comprehension: [n*2 for n in nums] builds a new list in one expression.

I. List parameters and nested list

• Pass by reference: a function receives the same object, so def chop(t): del t[0] mutates the caller's list and returns None.
• Pure alternative: def middle(t): return t[1:-1] leaves the argument untouched.
• Nested list: m = [[1,2,3],[4,5,6]]; m[1] → [4,5,6]; m[1][2] → 6. Beware [[0]*3]*2, which aliases one inner row three-deep.

IV. Tuples — Immutable Sequences

A. Mutability and tuples

A tuple is a comma-separated sequence, usually parenthesised, that cannot be altered after creation.

• Syntax: t = ('a','b','c'); the comma makes the tuple — t = 'a', is a one-element tuple, whereas ('a') is just a string.
• Immutable: t[0] = 'A' → TypeError. Rebuild instead: t = ('A',) + t[1:].
• Why it matters: immutability makes tuples hashable, so they may serve as dictionary keys or set members; lists may not.

B. Tuple assignment

Multiple assignment in a single statement, matching elements positionally.

a, b = b, a                       # swap without a temporary
(name, marks) = ("Ravi", 87)

• Arity rule: the number of names on the left must equal the number of values on the right, else ValueError: not enough values to unpack.
• Splitting example: user, domain = "sam@x.com".split('@').

C. Tuple as return values

A function returns one object, so a tuple carries several results at once.

def min_max(t):
    return min(t), max(t)

low, high = min_max([4, 9, 1])    # low = 1, high = 9

• Built-in case: divmod(7, 3) returns (2, 1) — quotient and remainder together.
• Variable-length: def f(*args) gathers arguments into a tuple; f(*lst) scatters a list into arguments.

V. Dictionaries — Key-to-Value Mappings

A. Dictionaries operations and methods

A dictionary maps immutable keys to arbitrary values, with lookup by key rather than position.

• Creation: eng2sp = {'one': 'uno', 'two': 'dos'}; empty is {} (not set()).
• Core operations:
  • Add/update: eng2sp['three'] = 'tres'; assigning an existing key overwrites.
  • Lookup: eng2sp['two'] → 'dos'; a missing key raises KeyError.
  • Delete: del eng2sp['one']; len(eng2sp) counts key-value pairs.
  • Membership: 'two' in eng2sp tests keys, not values.
• Methods:
  • keys(), values(), items() — views yielding keys, values, and (k, v) pairs.
  • get(k, default) — safe lookup returning default instead of raising.
  • update(other), pop(k), copy() — merge, remove-and-return, shallow copy.
• Counting idiom:
  
  PYTHON

    d = {}
    for ch in "mississippi":
        d[ch] = d.get(ch, 0) + 1     # {'m':1,'i':4,'s':4,'p':2}

B. Sparse matrices

A sparse matrix has mostly zero entries, so storing every cell as a nested list wastes memory; a dictionary stores only the non-zeros.

• Representation: key = (row, col) tuple, value = the non-zero entry.
  
  PYTHON

    matrix = {(0, 3): 1, (2, 1): 2, (4, 3): 3}

• Space: a 100×100 matrix with 5 non-zeros needs 5 entries, not 10 000.
• Reading safely: matrix.get((1, 1), 0) returns 0 for absent cells, restoring the mathematical meaning without a KeyError.
• Requirement: the key must be a tuple, not a list — only hashable objects can be keys.

VI. Aliasing and Copying — Identity Across All Four Types

A. Aliasing

Two names bound to the same object are aliases; a change through one is visible through the other.

• Test with is vs ==: == compares values, is compares identity (id()).
  
  PYTHON

    a = [1, 2, 3]
    b = a               # alias -- b is a  -> True
    b[0] = 99
    print(a)            # [99, 2, 3]

• Immutables are safe: x = "ban"; y = x; y += "ana" leaves x == "ban", because += on a string rebinds y to a new object.
• Function arguments: the parameter is an alias of the argument, which is why list and dict parameters can be mutated by the callee.

B. Copying

Copying breaks the alias by creating a distinct object.

1. Shallow copy: b = a[:], list(a), d.copy(), or copy.copy(a). A new outer container, but the same inner objects — a is not b yet a[0] is b[0]. Mutating a nested list still shows through.
2. Deep copy: import copy; b = copy.deepcopy(a) recursively duplicates every level, so no shared sub-object remains. Costlier, and it fails on self-referential structures unless handled by deepcopy's memo table.

• Tuple caveat: tuple(t) returns the same tuple object, since immutables need no copy — but a tuple containing a list still shares that list.