Lesson 08: Data Abstraction: Lists & Strings

Warm-Up

A quick self-test. Given this list:

colors ← ["red", "blue", "green", "gold"]

What is colors[2]?

If you've programmed in Python, JavaScript, or Java, every instinct says "green" — those languages start counting at 0. AP pseudocode starts at 1. colors[1] is "red", so colors[2] is "blue".

The exam writers know exactly which languages you've used, and they write distractors for your instincts. Every list question on the exam offers the 0-indexed answer as a choice. Retrain now: first element, index 1.

Core Concept

Lists: one name, many values

A list is an ordered collection of elements, each accessible by its index — its position, starting at 1.

scores ← [88, 92, 75, 99, 84]

Elements can be read and written: scores[3] ← 80 replaces 75 with 80. An index can be any expression: scores[i + 1] — evaluate the expression first, then index.

Accessing an index below 1 or beyond LENGTH causes a run-time error (Lesson 2's crash-on-certain-inputs, now with a cause you'll actually write).

The list operations — trace them exactly

Starting fresh each time from L ← [10, 20, 30]:

The shifting is where points are won: after INSERT(L, 2, 15), the value 20 — previously at index 2 — now lives at index 3. After a REMOVE, indexes of later elements each drop by 1. When a question chains operations, re-draw the list after every operation:

L ← [5, 8, 2]
APPEND(L, 9)        → [5, 8, 2, 9]
REMOVE(L, 2)        → [5, 2, 9]
INSERT(L, 1, 7)     → [7, 5, 2, 9]
DISPLAY (L[2])      → displays 5

Why lists exist: data abstraction

Suppose a gradebook program used separate variables: score1, score2, ..., score30. Now the class adds a student — you rewrite the program. Compute an average — thirty-term expression, written by hand.

A list replaces the mob of variables with one name managing many values. That's data abstraction, and the CED credits it with two specific powers:

1. Managing complexity: one name (scores) stands for the whole collection; the program says what to do with the collection, not each element by name.
2. Change-resilience: code written with LENGTH(scores) and loops (Lesson 12) works unchanged whether there are 3 scores or 3,000. You can change the data without changing the code.

That second sentence is nearly verbatim what Written Response 2(c) wants about your PT list. Learn it as a sentence-shape now: "Because my program refers to the list ___ rather than individual values, it works without modification when the number of ___ changes."

Strings

A string is an ordered sequence of characters: name ← "Ada". The CED requires two operations:

• Concatenation joins strings end to end. "sun" + "set" → "sunset" (some AP materials write CONCAT("sun", "set"); either way, joining). Order matters: "set" + "sun" → "setsun".
• Substring extracts part of a string. Convention used in AP materials: characters are numbered from 1, and a substring call names the start and end positions inclusively. From "COMPUTER": positions 1–3 → "COM"; positions 4–6 → "PUT".

Numbers vs. strings matters: "3" + "4" concatenates to "34"; 3 + 4 adds to 7. If a question mixes them, the type wins.

Worked Examples

Example 1 (easy): Indexing drill

Problem: animals ← ["cat", "owl", "fox", "bee", "elk"]. Evaluate: (i) animals[3] (ii) animals[LENGTH(animals)] (iii) animals[LENGTH(animals) − 3]

Solution: (i) "fox" (1→cat, 2→owl, 3→fox). (ii) LENGTH = 5 → animals[5] = "elk". (iii) 5 − 3 = 2 → "owl" — evaluate the index expression first, then look up.

Interpretation: (i) catches 0-indexers (they say "bee"). If you said "bee," do twenty of these tonight.

Example 2 (medium): Chained operations

Problem: What does this display?

L ← [4, 11, 4, 7]
REMOVE(L, 3)
APPEND(L, 2)
INSERT(L, 2, 9)
DISPLAY (L[3])

Strategy: Redraw the list after every line.

Solution:

Start:            [4, 11, 4, 7]
REMOVE(L, 3):     [4, 11, 7]        (the 4 at index 3 gone; 7 shifts to index 3)
APPEND(L, 2):     [4, 11, 7, 2]
INSERT(L, 2, 9):  [4, 9, 11, 7, 2]  (9 enters at 2; 11, 7, 2 shift right)
L[3] = 11 → displays 11

Interpretation: Four redraws, zero shortcuts. The distractors here are "7" (forgot INSERT shifts things) and "4" (misapplied REMOVE).

Example 3 (medium): Strings

Problem: first ← "GRACE", last ← "HOPPER". A program builds code ← substring of first from position 1 to 2, concatenated with substring of last from position 5 to 6. What is code?

Solution: first positions 1–2 (inclusive) → "GR". last = H(1) O(2) P(3) P(4) E(5) R(6); positions 5–6 → "ER". Concatenated: "GRER".

Interpretation: Number the characters with your pencil before extracting — counting on faith produces off-by-one substrings, and yes, "GRPE" (positions 4–5) is among the choices when this appears.

Example 4 (AP-style): Why the list version is better

Problem: A programmer replaces this:

total ← n1 + n2 + n3 + n4

with a list nums and code that sums the list (using a loop). Which is the BEST reason the list version is preferable?

(A) The list version runs faster (B) Lists use less memory than four variables (C) The list version works without code changes if the number of values changes (D) The original version contains a syntax error

Solution: (C) — data abstraction's change-resilience, the CED's stated benefit. (A)/(B) are unfounded micro-claims (and not CED reasoning); (D) is false — the original is valid, just brittle.

Interpretation: When the exam asks "why use a list," the answer is manage complexity / survive data-size changes — never speed or memory.

Common Mistakes

1. 0-indexing. The first element is L[1]. The distractor one position off is ALWAYS offered. This mistake alone costs unprepared students 2–3 exam points.
2. Forgetting the shift. INSERT pushes the element at that index (and everything after) rightward; REMOVE pulls later elements leftward. After any INSERT/REMOVE, old index knowledge is stale — redraw.
3. Confusing APPEND with INSERT. APPEND takes no index and always adds at the end. INSERT places at a stated index, shifting others.
4. L[LENGTH(L) + 1] to read the last element. The last element is L[LENGTH(L)]; one past it is a run-time error. (Writing via APPEND is how you extend.)
5. Treating "34" as 34. String concatenation glues digits; arithmetic adds numbers. Check whether values wear quotation marks.

Practice Problems

L ← [3, 6, 9]
INSERT(L, 2, 5)

L ← [8, 1, 6, 2]
REMOVE(L, 2)
APPEND(L, 4)

words ← ["hot", "cold", "warm"]
words[1] ← words[3]
DISPLAY (words[1] + words[2])

L ← [2, 4, 6, 8, 10]
i ← 2
DISPLAY (L[i + 2])

Create PT Connection

This is the most PT-loaded lesson in the course. The Create PT requires your program to use a list (or other collection) that manages complexity — and your Personalized Project Reference must include screenshots of (i) where the list is created or initialized and (ii) where it's used. Written Response 2(c) then asks you to explain it.

The winning explanation has exactly this lesson's shape:

"My program stores ___ in the list ___. Because the code processes the list with loops and LENGTH, it handles any number of entries without modification — without the list, I would need a separate variable for every ___ and would have to rewrite the program whenever the count changed."

Do this now: take one idea from your PT idea list (Lesson 6) and write its version of that paragraph with real names. If you can't name what the list holds, the idea isn't PT-ready yet — fix that before Lesson 14, where you'll add the required procedure.