AP Computer Science Principles · Unit 3 lecture · Part 8 of 14 · 10 min

3.2 and 3.10 Data abstraction and listsMany values under one name

Mr. Thompkins
Imagine a program for a class of 30 students with a separate variable for every test score: score1, score2, all the way to score30. Now imagine a new student joins. Lists fix this, and they're the most important data structure on the exam.

A list is an ordered sequence of elements. Each element is an individual value, and each has an index, a whole number giving its position. On the AP exam the first element is at index 1, and the last is at index LENGTH(aList). Other languages call lists arrays and may start at 0, but the exam counts from 1. Using any index less than 1 or greater than the length is an error, and the program stops.

songs"Hype""Calm""Drive"index 1index 2index 3songs[1] is "Hype"songs[LENGTH(songs)] is "Drive", the last onesongs[0] and songs[4] are errors:the program stopsAP lists start at 1, not 0
A list of three songs. Indexes run from 1 to LENGTH(songs).

Lists are a data abstraction. Data abstraction gives a collection of data a name, so the program can work with all of it without referring to the specific details of how it's stored. It separates what the data is (the songs on a playlist) from how it's represented. That manages complexity: one name, any number of items, and the same code works for 3 songs or 3,000. Programs built around good data abstractions are easier to develop and maintain. A list can hold mixed kinds of elements, and a string is also an ordered sequence, of characters.

?Wait, what does "manage complexity" mean on the written response?
It means making the program simpler to write, read and change. For a list, say what it stores under one name, how that lets one loop handle every item, and what you'd have to write without it: a separate variable and separate code for each item, with a fixed number of items.
Reference sheetWhat it does
aList ← [1, 2, 3]Makes a list; [] is an empty list
aList[i]The element at index i (1 is first)
aList[i] ← xReplaces the element at i. Nothing shifts
INSERT(aList, i, x)Puts x at i; later elements shift right
APPEND(aList, x)Adds x to the end
REMOVE(aList, i)Deletes the element at i; later ones shift left
LENGTH(aList)The number of elements
aList ← bListaList gets a copy of bList
The list operations on the reference sheet.

Two pairs of operations get mixed up. INSERT adds a new element and shifts later elements right; assignment, aList[i] ← x, replaces an element and nothing shifts. REMOVE deletes an element and shifts later elements left, so the list gets shorter and every index after it changes. And aList ← bList gives aList a copy of bList, so later changes to one don't affect the other.

1songs ← ["Hype", "Calm", "Drive"]2APPEND(songs, "Rain")3INSERT(songs, 1, "Intro")4REMOVE(songs, 3)5songs[2] ← "Wake"6DISPLAY(songs)7DISPLAY(LENGTH(songs))
output › ["Intro", "Wake", "Drive", "Rain"] 4
Five list operations in a row.
after linesongsLENGTH
1["Hype", "Calm", "Drive"]3
2["Hype", "Calm", "Drive", "Rain"]4
3["Intro", "Hype", "Calm", "Drive", "Rain"]5
4["Intro", "Hype", "Drive", "Rain"]4
5["Intro", "Wake", "Drive", "Rain"]4
Write out the whole list after every line. Indexes change after INSERT and REMOVE.
?Wait, after INSERT(songs, 1, "Intro"), what is songs[3]?
Everything shifted right by one. Before, songs[3] was "Drive". After, the list is ["Intro", "Hype", "Calm", "Drive", "Rain"], so songs[3] is "Calm". That's why line 4, REMOVE(songs, 3), removes "Calm", not "Drive".
Pause and think
A list has 4 elements. Which of these causes an error: songs[4], REMOVE(songs, 5), INSERT(songs, 5, "X"), APPEND(songs, "X")?
I thought about it. Show me
Only REMOVE(songs, 5): there is no element at index 5. songs[4] is the last element. APPEND always works. INSERT at LENGTH + 1 is allowed by some definitions, but the exam usually avoids that edge; when in doubt, indexes 1 to LENGTH are safe.
Trace list operations

What is displayed?

nums ← [5, 8, 2]
INSERT(nums, 2, 6)
APPEND(nums, nums[1] + nums[4])
REMOVE(nums, 1)
nums[2] ← 0
DISPLAY(nums)
  1. Line 2: insert 6 at index 2, shifting 8 and 2 right: [5, 6, 8, 2].
    Why?
    INSERT shifts. Now 8 is at index 3 and 2 is at index 4.
  2. Line 3: nums[1] is 5 and nums[4] is now 2, so append 7: [5, 6, 8, 2, 7].
    Why?
    Use the indexes after the INSERT, not the original ones.
  3. Line 4: remove index 1, shifting everything left: [6, 8, 2, 7].
  4. Line 5: replace index 2 (the 8) with 0: [6, 0, 2, 7].
    Why?
    Assignment replaces. Nothing shifts.

Answer: [6, 0, 2, 7]

Stuck? Get a hint
  1. Rewrite the whole list after every line.
  2. After the INSERT, the list is [5, 6, 8, 2]: what is at index 4?
  3. REMOVE shifts left; assignment just replaces.
Check yourself
Which best explains how using a list called scores manages complexity in a gradebook program?
  1. AIt makes the program run faster than any other way.
  2. BAll the scores are stored under one name, so the same loop can process any number of scores without a separate variable for each.
  3. CIt prevents all errors involving scores.
  4. DIt lets the program skip storing the scores.
Show the answer

B. Data abstraction gives the collection one name, so one loop handles every score, for any class size. Speed and error-proofing aren't what the course means by managing complexity.

  • A list is an ordered sequence of elements. Indexes go from 1 to LENGTH(aList); others are errors.
  • INSERT and REMOVE shift later elements. Assignment to aList[i] replaces without shifting.
  • Data abstraction: one name for a collection, hiding details. It manages complexity.
  • aList ← bList makes a copy. Always rewrite the whole list after each change.