3.2 and 3.10 Data abstraction and listsMany values under one name

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.
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?
| Reference sheet | What 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] ← x | Replaces 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 ← bList | aList gets a copy of bList |
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))
| after line | songs | LENGTH |
|---|---|---|
| 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 |
?Wait, after INSERT(songs, 1, "Intro"), what is songs[3]?
I thought about it. Show me
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)
- 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. - 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. - Line 4: remove index 1, shifting everything left: [6, 8, 2, 7].
- 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
- Rewrite the whole list after every line.
- After the INSERT, the list is [5, 6, 8, 2]: what is at index 4?
- REMOVE shifts left; assignment just replaces.
- AIt makes the program run faster than any other way.
- BAll the scores are stored under one name, so the same loop can process any number of scores without a separate variable for each.
- CIt prevents all errors involving scores.
- 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.