Topic 3.10 Notes – Lists

1. What Lists Are and How Indexing Works

A list is an ordered collection of elements.
Ordered means each item has a specific position, called its index.

On the AP Exam, indexing starts at 1, not 0.

• First element → aList[1]
• Second element → aList[2]
• Last element → aList[LENGTH(aList)]

If scores ← [88, 91, 79] then:

• scores[1] is 88
• scores[3] is 79

That 1-based indexing is one of the most common mistakes on multiple-choice questions.

Accessing and Updating Elements

All of these come directly from the Exam Reference Sheet.

Access an element

aList[i]

Gets the value at index i.

Store an element in a variable

x ← aList[i]

Copies the value into x.

Replace an element

aList[i] ← x

Overwrites the value at index i.

Copy one element to another

aList[i] ← aList[j]

Copies the value at position j into position i.

Important: replacing a value does not change the length of the list. You are changing what’s there, not adding or removing anything.

2. List Procedures on the Exam Reference Sheet

These actually change the structure of the list.

INSERT(aList, i, value)

• Places value at index i.
• Everything at index i and above shifts right.
• List length increases by 1.

Here is what that looks like when inserting into the middle of a list.

If you insert at position 2, the old element at 2 moves to 3.

APPEND(aList, value)

• Adds value to the end.
• Length increases by 1.
• No shifting happens.

REMOVE(aList, i)

• Deletes the element at index i.
• Everything after index i shifts left.
• Length decreases by 1.

Now compare that to removing from the middle.

After a REMOVE, every index after that point changes.

LENGTH(aList)

Returns the current number of elements.
Commonly used in loop conditions like:

i ≤ LENGTH(aList)

3. Traversing a List with Iteration

To traverse a list means to access elements one at a time using iteration.

Complete Traversal

Access every element.

FOR EACH item IN aList
{
   DISPLAY(item)
}

• item becomes each value in order.
• Runs once per element.
• You don’t control the index directly.

Use this when you only need values, not positions.

Index-Based Traversal

When you need positions:

i ← 1
REPEAT UNTIL i > LENGTH(aList)
{
   DISPLAY(aList[i])
   i ← i + 1
}

You control where it starts and stops.

Partial Traversal

Sometimes you don’t visit every element.

Examples:

• Start at index 3.
• Stop when a value is found.
• Only process even indices.

The AP Exam does not include parallel traversal of multiple lists at once.

4. Common List Algorithms You Must Recognize

These patterns show up constantly.

Minimum or Maximum

1. Set min ← aList[1]
2. Traverse the rest.
3. If aList[i] < min, update min.

You are always comparing to a stored “best so far.”

Sum and Average

total ← 0
FOR EACH num IN aList
{
   total ← total + num
}

Average:

average ← total / LENGTH(aList)

If you forget to divide by LENGTH, you just computed a sum.

Linear Search

Checks elements in order until:

• Target found, or
• End of list reached.

Worst case checks every element.
It works on sorted or unsorted lists.

On tests, they often hide the search inside a loop with a Boolean flag. Trace carefully.

5. How to Evaluate List Code on the Exam

When tracing list problems:

• Rewrite the entire list after every INSERT or REMOVE.
• Update the LENGTH when size changes.
• Watch loop bounds carefully (≤ LENGTH matters).
• Pay attention to whether the list is modified while being traversed.

The exam loves giving you a REMOVE inside a loop and asking for the final list. If indices shift and you don’t notice, your answer will be off by one element.

Everything comes back to this idea: the order statements execute determines the result. With lists, a small index change can completely change the output.