3.10 Lists

Enduring Understanding

The way statements are sequenced and combined in a program determines the computed result. Programs incorporate iteration and selection constructs to represent repetition and make decisions to handle varied input values.

Learning Objective

For list operations:

a. Write expressions that use list indexing and list procedures.

b. Evaluate expressions that use list indexing and list procedures.

Essential Knowledge

The exam reference sheet provides basic operations on lists, including:

• accessing an element by index

Text:

aList[i]

Block:

accesses the element of aList at index i. The first element of aList is at index 1 and is accessed using the notation aList[1].

• assigning a value of an element of a list to a variable

Text:

x <-- aList[i]

Block:

• assigning a value to an element of a list

Text:

aList[i] <-- x

Block:

assigns the value of x to aList[i].

Text:

aList[i] <-- aList[j]

Block:

assigns the value of aList[j] to aList[i].

• inserting elements at a given index

Text:

INSERT(aList, i, value)

Block:

shifts to the right any values in aList at indices greater than or equal to i. The length of the list is increased by 1, and value is placed at index i in aList.

• adding elements to the end of the list

Text:

APPEND(aList, value)

Block:

evaluates to the number of elements currently in aList.

List procedures are implemented in accordance with the syntax rules of the programming language.

• removing elements

Text:

REMOVE(aList, value)

Block:

removes the item at index i in aList and shifts to the left any values at indices greater than i. The length of aList is decreased by 1.

• determining the length of a list

Text:

LENGTH(aList)

Block:

evaluates to the number of elements currently in aList.

List procedures are implemented in accordance with the syntax rules of the programming language.

Learning Objective

For algorithms involving elements of a list:

a. Write iteration statements to traverse a list.

b. Determine the result of an algorithm that includes list traversals.

Essential Knowledge

Traversing a list can be a complete traversal, where all elements in the list are accessed, or a partial traversal, where only a portion of elements are accessed.

Exclusion Statement: Traversing multiple lists at the same time using the same index for both (parallel traversals) is outside the scope of this course and the AP Exam.

Iteration statements can be used to traverse a list.

The exam reference sheet provides

Text:

FOR EACH item IN aList

{

<block of statements>

}

Block:

The variable item is assigned the value of each element of aList sequentially, in order, from the first element to the last element. The code in block of statements is executed once for each assignment of item.

Knowledge of existing algorithms that use iteration can help in constructing new algorithms. Some examples of existing algorithms that are often used with lists include:

• determining a minimum or maximum value in a list

• computing a sum or average of a list of numbers

Linear search or sequential search algorithms check each element of a list, in order, until the desired value is found or all elements in the list have been checked.