Unit 3 · Topic 3.10

3.10 Lists

Lists are where most exam code questions live. This topic covers every list operation on the reference sheet, traversing a list with FOR EACH or an index, the standard list algorithms (minimum, maximum, sum, average) and linear search.

Key terms

traversal
FOR EACH
APPEND, INSERT, REMOVE
LENGTH
linear (sequential) search

List operations on the reference sheet

Remember that indexes run from 1 to LENGTH(aList), and any index outside that range stops the program with an error.

Operation	What it does
aList[i]	Gets the element at index i
aList[i] ← x	Replaces the element at index i with x
INSERT(aList, i, value)	Shifts the elements at index i and above one place right, then puts value at index i; length goes up by 1
APPEND(aList, value)	Adds value to the end; length goes up by 1
REMOVE(aList, i)	Removes the element at index i and shifts later elements one place left; length goes down by 1
LENGTH(aList)	The number of elements in the list right now

Tracing list changes

After an INSERT or REMOVE, the indexes of later elements change. Rewrite the whole list after each step:

pets ← ["cat", "dog", "fish"] APPEND(pets, "bird") INSERT(pets, 2, "frog") REMOVE(pets, 1) DISPLAY(LENGTH(pets)) DISPLAY(pets[1]) DISPLAY(pets[4])

Start: ["cat", "dog", "fish"]. After APPEND: ["cat", "dog", "fish", "bird"]. After INSERT at 2: ["cat", "frog", "dog", "fish", "bird"]. After REMOVE at 1: ["frog", "dog", "fish", "bird"]. It displays 4 frog bird.

Traversing a list

Traversing a list means accessing its elements one by one. A complete traversal visits every element; a partial traversal visits only some, such as the first three.

FOR EACH item IN aList assigns each element to item in order, from first to last, and runs the block once per element:

FOR EACH item IN aList { <block of statements> }

FOR EACH is the simplest choice when you need every element but not its position. When you need the index, or only part of the list, use a counter variable with REPEAT n TIMES or REPEAT UNTIL:

nums ← [12, 5, 8, 20, 3] i ← 1 sum ← 0 REPEAT 3 TIMES { sum ← sum + nums[i] i ← i + 1 } DISPLAY(sum)

This adds only the first three elements, 12 + 5 + 8, and displays 25.

Standard list algorithms

Minimum or maximum: start a "best so far" with the first element, then compare every element to it.

PROCEDURE findMin(aList) { smallest ← aList[1] FOR EACH value IN aList { IF (value < smallest) { smallest ← value } } RETURN(smallest) }

findMin([7, -2, 4, -9, 0]) returns -9. Starting with aList[1] instead of 0 matters: with 0 as the start, a list of all positive numbers would wrongly return 0.

Sum and average: start a total at 0, add every element, then divide by LENGTH(aList) for the average.

Linear search

A linear (or sequential) search checks each element in order until it finds the target or runs out of elements. It works on any list, sorted or not. In the worst case, when the target is last or missing, it checks every element.

PROCEDURE findIndex(aList, target) { index ← 1 FOR EACH item IN aList { IF (item = target) { RETURN(index) } index ← index + 1 } RETURN(-1) }

findIndex([4, 9, 2, 9], 9) returns 2, the first match. RETURN ends the procedure right away, so the search stops early. If the loop finishes without a match, it returns -1 to mean "not found."

Worked examples

Try each one yourself first, then open the solution.

Example 1
Removing while traversing
This segment is supposed to remove every 8 from the list. What does the list hold afterward, and why?nums ← [3, 8, 8, 5] i ← 1 REPEAT UNTIL (i > LENGTH(nums)) { IF (nums[i] = 8) { REMOVE(nums, i) } i ← i + 1 }
Show the solutionHide the solution
1. Step 1: i = 1: nums[1] is 3, not 8. i becomes 2.
2. Step 2: i = 2: nums[2] is 8, so REMOVE(nums, 2). The list is now [3, 8, 5]. The second 8 slid into index 2. Then i becomes 3.
3. Step 3: i = 3: nums[3] is 5. Not 8. i becomes 4.
4. Step 4: i = 4: 4 > LENGTH(nums), which is 3, so the loop stops. The 8 that slid into index 2 was never checked.
5. Step 5: Fix: only add 1 to i when nothing was removed:nums ← [3, 8, 8, 5] i ← 1 REPEAT UNTIL (i > LENGTH(nums)) { IF (nums[i] = 8) { REMOVE(nums, i) } ELSE { i ← i + 1 } }This leaves [3, 5].
Answer: The list becomes [3, 8, 5]. One 8 is skipped because REMOVE shifts the next element into the index that was just checked.
Example 2
Write a procedure: count values above a limit
Write a procedure countAbove(aList, limit) that returns how many elements of aList are greater than limit. For example, countAbove([4, 10, 7, 12], 7) should return 2.
Show the solutionHide the solution
1. Step 1: You need a counter that starts at 0 and goes up by 1 for each match, so set count ← 0 before the loop.
2. Step 2: You need every element but not its index, so use FOR EACH.
3. Step 3: Inside the loop, an IF checks value > limit and adds 1 to count when it's true.
4. Step 4: After the loop, return count. Full solution:PROCEDURE countAbove(aList, limit) { count ← 0 FOR EACH value IN aList { IF (value > limit) { count ← count + 1 } } RETURN(count) }
5. Step 5: Check: for [4, 10, 7, 12] with limit 7, only 10 and 12 count (7 > 7 is false). It returns 2.
Answer: A procedure that sets count to 0, adds 1 for each element greater than limit, and returns count; countAbove([4, 10, 7, 12], 7) returns 2.

Common mistakes

Forgetting that INSERT and REMOVE shift later elements, so their indexes change.
Writing a loop that goes one index too far, such as REPEAT UNTIL (i > LENGTH(aList) + 1), which causes an index error.
Starting a minimum or maximum at 0 instead of the first element.
Thinking linear search needs a sorted list. That's binary search.

On the exam

Expect several questions that trace list operations or loops over lists. Rewrite the whole list after each change.
Your Create task must use a list. Written Response 2(c) may ask you to explain an algorithm that uses your list, step by step. Practice describing what your loop does to each element.

Connected topics

Videos

AP CSP Topic 3.10 - Lists - Explanations and 5 MCQs!
Dr_WuWatch on YouTube (opens in a new tab)
AP CS Principles Exam Review - Lists and Iteration
Flavio KupermanWatch on YouTube (opens in a new tab)
Adding and Removing from an Array - AP CSP in Roblox
CodeHSWatch on YouTube (opens in a new tab)
CS Principles: Processing Lists
CodeAIWatch on YouTube (opens in a new tab)
List iteration | Intro to CS - Python | Khan Academy
Khan AcademyWatch on YouTube (opens in a new tab)
AP CSP Topic 3.10 - Lists - Speedrun! 28 MCQs
Dr_WuWatch on YouTube (opens in a new tab)

Check yourself

4 questions on 3.10 Lists. Pick an answer to see if you got it, and why.

Question 1 of 4

What is displayed when the following code segment is run? nums ← [5, 8, 2] APPEND(nums, 6) INSERT(nums, 2, 9) REMOVE(nums, 4) DISPLAY(nums)

Question 2 of 4

What is displayed when the following program is run? PROCEDURE findIndex(aList, target) { index ← 1 REPEAT UNTIL (index > LENGTH(aList)) { IF (aList[index] = target) { RETURN (index) } index ← index + 1 } RETURN (-1) } DISPLAY(findIndex([4, 7, 1, 7], 7)) DISPLAY(findIndex([4, 7, 1, 7], 3))

Question 3 of 4

What happens when the following code segment is run? vals ← [3, 6, 9] i ← 0 REPEAT 3 TIMES { DISPLAY(vals[i]) i ← i + 1 }

Question 4 of 4

The following code segment is intended to remove every 0 from the list nums. For which starting list does nums still contain a 0 after the code segment runs? i ← 1 REPEAT UNTIL (i > LENGTH(nums)) { IF (nums[i] = 0) { REMOVE(nums, i) } i ← i + 1 }

0 of 4 answered