Lists and data abstraction

By the end you can:

• Explain how a list reduces complexity compared with separate variables, with a concrete example of growth.
• Read an item by index in AP pseudocode and in Python.
• Trace APPEND, INSERT, REMOVE and LENGTH, including how indexes shift.
• Trace a filter and a count over a list, including duplicates, no matches and an empty list.
• Recognise when a collection does not store what the program’s purpose requires.

List

An ordered collection of values stored under one name.

Element

One value in a list.

Index

The position of an element. AP pseudocode starts at 1; Python starts at 0.

Traversal

Visiting each element of a list in turn, for example with FOR EACH.

Filter

Building a new list containing only the elements that meet a condition.

Data abstraction

Using one name for a collection of data so programs can work with it without handling each value separately.

Suppose the club finder stores the places left in each club. With separate variables you write cap1 ← 0, cap2 ← 5, cap3 ← 2, cap4 ← 8, and every calculation names each variable. Adding a fifth club means editing every one of those calculations.

A list is a single named collection of values in order: caps ← [0, 5, 2, 8]. Code that traverses the list works for any number of clubs without changes. This is data abstraction: one name stands for the whole collection, so the program can be written without knowing how many items there will be.

Each item has an index, its position in the list. In AP CSP pseudocode the first item is at index 1. In Python the first item is at index 0. The same list, read with the same number, can give different items in the two languages.

So clubs[1] is "Art" in AP pseudocode but "Chess" in Python. Reading an index outside 1 to LENGTH(list) in AP pseudocode is an error.

After an INSERT or REMOVE, the items after that point have new indexes. Trace the whole list after each change rather than remembering positions.

1caps.append(9)2caps.insert(1, 7)   # Python index 1 is AP index 23caps.pop(0)         # Python index 0 is AP index 14len(caps)

Worked example

Predict the result before reading the trace: keep the clubs with at least 3 places.

1caps ← [0, 5, 2, 8]2result ← []3FOR EACH c IN caps4{5  IF (c ≥ 3)6  {7    APPEND(result, c)8  }9}10DISPLAY(result)

Displays [5, 8]. Three cases to check with any filter: duplicates — [3, 3] with minimum 3 keeps both 3s, because each item is tested separately; no matches — minimum 9 gives [], an empty list, not an error; an empty input — [] gives [] because the loop body never runs.

1caps = [0, 5, 2, 8]2result = []3for c in caps:4    if c >= 3:5        result.append(c)6print(result)

• AP and Python indexes match

  The belief: clubs[1] is the first club in both languages.

  What is actually true: AP pseudocode starts at 1; Python starts at 0. clubs[1] is the first club in AP but the second in Python.

  Check yourself: Which language is this code written in, and where does its index start?

• Filters remove duplicates

  The belief: Filtering [3, 3] keeps only one 3.

  What is actually true: Each element is tested separately. Both 3s meet the condition and both are kept.

  Check yourself: How many times did the loop body run, and how many times did APPEND run?

• Using a list explains abstraction

  The belief: “It is simpler because it uses a list.”

  What is actually true: Say what is simpler: the same code handles any number of items, so it does not change as the data grows.

  Check yourself: What would you have to change if there were 300 items instead of 4?

1. For scores ← [7, 2, 9], what is scores[2] in AP pseudocode and in Python?
2. Describe how adding 50 items changes a list-based solution and a variable-based solution.

Practice only: answers are checked in your browser and nothing is saved or sent to your teacher. Each explanation links back to the section it practises.

Lesson practice

Apply it somewhere new