3.10 Lists

What you need to know

• AP pseudocode list operations (all 1-indexed): list[i] accesses element i; list[i] ← value assigns it; LENGTH(list) gives the number of elements.
• APPEND(list, value) adds to the end and increases length by 1. INSERT(list, i, value) puts value at index i, shifting later elements right. REMOVE(list, i) deletes the element at i, shifting later elements left.
• After INSERT or REMOVE, indices of later elements change. A question that removes index 2 and then reads index 3 is reading what used to be index 4.
• Traversal means visiting every element. FOR EACH item IN list is the complete traversal; a REPEAT UNTIL with an index can do partial traversals.
• Common list algorithms: linear search (check each element until found), filtering into a new list, counting, sum/average, min/max, reversing, checking for duplicates.
• A list can be empty: [], with LENGTH 0. Accessing list[1] on an empty list is a run-time error.
• Lists can contain lists, allowing grids or tables — but the CED keeps most questions to one dimension.

Worked example

a ← [10, 20, 30, 40]
REMOVE(a, 2)
APPEND(a, 50)
INSERT(a, 1, 5)
DISPLAY(a[3])
DISPLAY(LENGTH(a))

Step through: start [10,20,30,40] → REMOVE index 2 → [10,30,40] → APPEND 50 → [10,30,40,50] → INSERT 5 at index 1 → [5,10,30,40,50]. Then a[3] = 30, LENGTH = 5. Output: 30 5.

Trace it yourself

Step through with the buttons, or use the ← → keys. Changed variables are highlighted.

Going deeper

The nuance, edge cases, and connections that turn a 3 into a 5.

• The complete list of operations on the AP reference sheet: list[i] (access), list[i] ← value (assign), LENGTH(list), APPEND(list, value), INSERT(list, i, value), REMOVE(list, i), and FOR EACH. That's all. Anything else is defined in the question.
• INSERT shifts right: the element at index i and everything after it moves to i + 1, i + 2, … and the new value goes at i. Length grows by 1. REMOVE shifts left: the element at i is gone, and everything after moves down. Length shrinks by 1. APPEND is INSERT at LENGTH + 1.
• After a REMOVE, the index you just removed now holds what used to be the next element. This causes the classic "remove every matching element in a forward loop" bug: matching elements adjacent to each other get skipped. (The Java version of this bug is in CSA 4.9.)
• FOR EACH item IN list visits every element in order. The variable item holds a copy of the current element. Changing item inside the loop does not change the list. To change list elements you need an index loop with list[i] ← ….
• Linear search — checking each element until you find the target — is the only search you can do on an unsorted list. It's O(n) in the worst case: n elements means up to n comparisons.
• Building a new list by filtering: start with an empty list, FOR EACH over the original, APPEND matches. The original is unchanged. This is how "return a list of all elements that…" is done.
• An empty list has LENGTH 0, and accessing any index is an error. Algorithms that read list[1] before checking length will fail on empty input — a testable edge case.

Mistakes that cost points

• Not rewriting the list after each operation. Index shifts are invisible unless you write the list out. Do it every time.
• Reading the wrong index after INSERT/REMOVE. After REMOVE(a, 2), what was a[3] is now a[2]. Questions are built around this.
• Modifying the FOR EACH variable and expecting the list to change. It won't.
• Using index 0. Still 1-based. Still tested.

Practice questions

Written in the style of the real exam. Try each one before revealing the answer.

nums ← [3, 8, 1, 6]
INSERT(nums, 2, 9)
REMOVE(nums, 4)
DISPLAY(nums)

PROCEDURE contains(list, target)
{
    FOR EACH item IN list
    {
        IF (item = target)
        {
            RETURN true
        }
    }
    RETURN false
}