3.10 Lists

TLDR

Lists let you store many related values in one ordered variable and reach each value by its index. In AP Computer Science Principles, you need to use list operations like indexing, INSERT, APPEND, REMOVE, and LENGTH, and you need to traverse a list with loops to do things like search, sum, or find a max or min. Remember that the AP exam reference sheet uses 1-based indexing, so the first element is at index 1.

Lists show up across the Algorithms and Programming material, which is the largest part of the multiple-choice section. You will often need to trace code that uses list operations and predict the exact result, or pick the code segment that produces a given list. The exam pseudocode on the reference sheet has its own list rules, so being fluent in that notation helps you read questions quickly and avoid indexing slips.

Lists are also useful for the Create performance task. A list is a clean way to build a data abstraction, which means using one named list to represent a collection of related values instead of many separate variables. If your program uses a list with a loop, you have a strong piece to write about when you explain how an abstraction manages complexity in your program.

What to Know About Lists

• A list is an ordered sequence of elements, and each element has a unique index. On the AP reference sheet, indexes run from 1 to the length of the list.
• Know every reference-sheet list operation: aList[i], x ← aList[i], aList[i] ← x, INSERT, APPEND, REMOVE, and LENGTH.
• INSERT and REMOVE change the length of the list and shift other elements, so the index of values can change after you use them.
• Traversing a list can be complete (every element) or partial (only some elements), using a loop.
• FOR EACH item IN aList walks through every element in order, which is ideal for sums, averages, and finding a max or min.
• Linear (sequential) search checks each element in order until it finds the target or runs out of elements.

Lists on the AP Computer Science Principles Exam

Exam Pseudocode List Operations:

These are the list operations on the AP exam reference sheet. The notation is what you will see in multiple-choice questions, so practice reading and writing it.

• aList[i] gets the element stored in aList at position i. AP lists start counting at 1, so aList[1] is the first element.
• x ← aList[i] copies whatever is stored at aList[i] into the variable x.
• aList[i] ← x assigns the value of x to aList[i].
• INSERT(aList, i, value) shifts to the right any values at indices greater than or equal to i, increases the length by 1, and places value at index i.
• APPEND(aList, value) increases the length by 1 and places value at the end.
• REMOVE(aList, i) removes the item at index i, shifts left any values at indices greater than i, and decreases the length by 1.
• LENGTH(aList) evaluates to the number of elements currently in aList.

According to the exam reference sheet, using an index below 1 or above the number of items in the list causes an error, and the program stops running. Watch for this in trace questions.

Code Tracing: Most list questions ask you to determine the result of a code segment. A reliable method:

1. Write out the list as a row of boxes and label each index, starting at 1.
2. Run each statement one line at a time, updating your boxes.
3. After every INSERT or REMOVE, recount the indexes, because elements shifted and the length changed.
4. Track any separate variables (like a running sum or a current max) next to your boxes.

Here is the same idea in exam pseudocode. Trace it by hand:

</>Code
aList ← [10, 20, 30]
APPEND(aList, 40)
INSERT(aList, 2, 15)
REMOVE(aList, 4)

Step by step: after APPEND, the list is [10, 20, 30, 40]. After INSERT(aList, 2, 15), everything from index 2 on shifts right, giving [10, 15, 20, 30, 40]. After REMOVE(aList, 4), the item at index 4 (which is 30) is removed, giving [10, 15, 20, 40].

Traversing a List:

A traversal visits elements of a list using a loop. Use FOR EACH when you want every element and you do not need the index:

</>Code
total ← 0
FOR EACH item IN aList
{
    total ← total + item
}

This pattern gives you a sum. Divide total by LENGTH(aList) to get an average. For a max or min, set a starting value to the first element, then compare each item as you traverse and keep the larger (or smaller) one.

A partial traversal visits only part of the list, which usually means an index-based loop that starts or stops somewhere other than the ends. Note that parallel traversals, meaning stepping through two lists at once with the same index, are outside the scope of this course and the exam.

Linear Search: Linear search checks elements one at a time, in order, until it finds the target or reaches the end. It works on any list, sorted or not. To write one, traverse the list and compare each element to the value you want, stopping when you find a match.

Knowing existing iterative algorithms, such as linear search, summing, and finding a max or min, helps you build new ones. You can often adapt a familiar pattern to a new task. For example, a count of values above 10 is the sum pattern with a condition added.

Using Lists in the Create Performance Task: If you use a list in your program, you can explain it as a data abstraction: one named list stands in for a whole collection of related values, so you do not need a separate variable for each item. Pair the list with a loop that does real work, like searching or totaling, and describe how the program would be harder to write or maintain without that list.

Common Misconceptions

• Misconception: The first element is at index 0.
  Actually: The first element is at index 1 on the AP reference sheet, not index 0. Many languages like Python use 0-based indexing, so if you practice in Python, remember to switch to 1-based thinking for exam pseudocode questions.
• Misconception: INSERT and REMOVE do not change the length or shift elements.
  Actually: INSERT and REMOVE change the length and shift elements. After you remove an item, the values after it slide down to fill the gap, so indexes are different from before.
• Misconception: INSERT(aList, i, value) overwrites the element at index i.
  Actually: INSERT(aList, i, value) puts value at index i and pushes existing elements toward the end; it does not overwrite the element that was there. To replace an element, use aList[i] ← value.
• Misconception: An out-of-range index is ignored.
  Actually: An out-of-range index is not ignored. If the index is below 1 or above the length, the exam reference sheet says the program produces an error and stops.
• Misconception: aList[i] ← x adds a new element.
  Actually: aList[i] ← x changes an element that already exists; it does not add a new one. Use APPEND or INSERT to make the list longer.
• Misconception: FOR EACH item IN aList gives you each item's index.
  Actually: FOR EACH item IN aList gives you each value, not its index. If you need the position of an element, use an index-based loop instead.
• Misconception: Reassigning one element creates a new list.
  Actually: A list is one variable that holds many values, so reassigning one element does not create a new list; it modifies the existing one in place.

Related AP Computer Science Principles Guides

• 3.1 Variables and Assignments
• Big Idea 3: Algorithms and Programming
• 3.12 Calling Procedures
• 3.18 Undecidable Problems
• 3.17 Algorithmic Efficiency
• 3.2 Data Abstraction