Big Ideas

  • Understanding how to edit lists by adding, inserting, and removing data
  • Using loops to iterate through lists and abstract data
  • Determine the results or side effects of iteration statements
  • Write sorting algorithms using iteration

Necessary Vocabulary

  • Indexing / List Index - The position of an element in a list, starting from 0
  • append, remove, pop - Various methods, append adds an element to the end, remove removes at an index, and pop removes the last item.
  • Elements [in a list] - An item in a list.
  • Nesting - Having one data type or function inside another data type or function, such as lists or loops.
  • array - Another name for a list, depends on the language

Examples of List Operations

Extra Resource: Documentation

Language List Documentation
Python link
Javascript link

What are Lists?

  • Lists are a collection of data in a sequence that is an iterable
  • Each sequence is demarcated with an index, starting from 0. This is known as base 0 indexing
  • In memory, it is stored as a variable name with multiple pointers to each variable stored in a certain order
  • Lists can also be called arrays
  • Lists have methods that act upon the list and change them. This moves the pointers within RAM to change the parts of the list.

A MASSIVE NOTE: Lists methods Mutate, meaning they actively change the list, but they don't return anything. This means that return a None-type, which you cannot manipulate

Adding Something to a List 

fruits = ["apple", "banana", "kiwi", "pomegranate"]

print(f"Fruits before append: {fruits}")

fruits.append("dragonfruit") # ADDS TO THE END OF THE LIST

print(f"Fruits after append: {fruits}")

Fruits before append: ['apple', 'banana', 'kiwi', 'pomegranate']
Fruits after append: ['apple', 'banana', 'kiwi', 'pomegranate', 'dragonfruit']

food = ["apple", "banana", "kiwi", "pomegranate"]
vegetables = ["carrot", "cucumber", "eggplant"]

print(f"Fruits before extend: {fruits}")

fruits.extend(vegetables) # adds the vegetable list to the end of the food list 

print(f"Fruits after extend: {fruits}")

Fruits before extend: ['apple', 'banana', 'kiwi', 'pomegranate', 'dragonfruit']
Fruits after extend: ['apple', 'banana', 'kiwi', 'pomegranate', 'dragonfruit', 'carrot', 'cucumber', 'eggplant']

fruits = ["apple", "banana", "kiwi", "pomegranate"]

print(f"Fruits before insert: {fruits}")

fruits.insert(1, "dragonfruit")

print(f"Fruits after insert: {fruits}")

Fruits before insert: ['apple', 'banana', 'kiwi', 'pomegranate']
Fruits after insert: ['apple', 'dragonfruit', 'banana', 'kiwi', 'pomegranate']

Removing Items 

fruits = ["apple", "banana", "kiwi", "pomegranate"]

print(f"Fruits before pop: {fruits}")

fruits.pop()

print(f"Fruits after pop (no parameter): {fruits}")

fruits.pop(0)

print(f"Fruits after pop (specifying index 0): {fruits}")

Fruits before pop: ['apple', 'banana', 'kiwi', 'pomegranate']
Fruits after pop (no parameter): ['apple', 'banana', 'kiwi']
Fruits after pop (specifying index 0): ['banana', 'kiwi']

fruits = ["apple", "banana", "kiwi", "pomegranate"]

print(f"Fruits before remove: {fruits}")

fruits.remove("apple")

print(f"Fruits after remove (removing apple): {fruits}")

fruits.remove("kiwi")

print(f"Fruits after remove (removing kiwi): {fruits}")

Fruits before remove: ['apple', 'banana', 'kiwi', 'pomegranate']
Fruits after remove (removing apple): ['banana', 'kiwi', 'pomegranate']
Fruits after remove (removing kiwi): ['banana', 'pomegranate']

Practice

Question 1

Consider the Following Code Segment

{
    lst =  ["your", "a", "very", "skilled", "individual"]
    lst.append("Person")
    lst.pop()
    lst.remove("your")
    lst.insert(0, "you're")
    print(lst)
}
Answer! ["you're", 'a', 'very', 'skilled', 'individual']

Question 2

In each instance, would we use a list? We want to represent a sequence of children in order.
We want to represent the number of animals in a zoo.
We want to repeatedly find the derivative of a number.
We want to represent Key value pairs of schools and their quantities We want to represent the grades of a classroom

Answer! 1. Yes
2 No
3. No
4. No
5. Yes

Question 3 

{
mgAmounts ← [50, 230, 63, 98, 80, 120, 71, 158, 41]
bestAmounts ← []
mgPerDay ← 360
mgMin ← mgPerDay * 0.3
FOR EACH mgAmount IN mgAmounts
{
    IF (mgAmount ≥ mgMin)
    {
        <MISSING CODE>
    }
} 
}

What can replace so that this program will work as expected?</strong> However, there may multiple answers a. INSERT(bestAmounts, mgAmount) b. APPEND(bestAmounts, mgAmount) c. INSERT(bestAmounts, mgAmounts) d. INSERT(mgAmounts, mgAmount) e. APPEND(bestAmounts, mgAmounts) f. APPEND(mgAmounts, mgAmount)</p>

Answer! Only b, as it is the only item that correctly uses the method and doesn't improperly extend the length.
</div> </div> </div>

Question 4

Consider the following code segment

{
sevenWonders ← ["Aurora", "Grand Canyon", "Great Barrier Reef", "Guanabara Bay", "Mount Everest", "Parícutin", "Victoria Falls"]

sevenWonders[4] ← "Komodo"
sevenWonders[6] ← "Table Mountain"
}

What does sevenWonders store?

Answer! "Aurora", "Grand Canyon", "Great Barrier Reef", "Komodo", "Mount Everest", "Table Mountain", "Victoria Falls"

Question 5

Consider the Following Code Segment

{

lst = [12,3,4,5,14,6,1,234]

lst.pop()
lst.append('x')
lst.insert(lst[0])

print(lst.pop())
print(lst)

}

What would this display

Answer! :P try and get it without checking the answer!

Nested Lists

Uses of Nested lists

Placing lists within lists allows you to have arrays of similar data together, and create complexity.

Some uses include:

  • Creating 2d Arrays
  • Storing similar, but slightly different categories (sublists)
  • Create a matrix
TwoDArray = [[1, 0, 1, 0, 1, 0, 0, 0], [0, 0, 0, 0, 1, 0, 1, 1], [1, 1, 0, 0, 0, 1, 1, 1], [0, 0, 0, 0, 1, 1, 1, 1]]
print(TwoDArray[0]) # print first sublist
print(TwoDArray[1]) # print second sublist
print(TwoDArray[2]) # print third sublist

# These 1s and 0s could represent anything. AMAZING DATA ABSTRACTION!

[1, 0, 1, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 1, 1]
[1, 1, 0, 0, 0, 1, 1, 1]

You can also iterate over these using multiple loops, but we'll talk about that later 

bin_0 = 0
bin_1 = 0
for array in TwoDArray:
    for bin in array:
        if bin == 0:
            bin_0 += 1
        elif bin == 1:
            bin_1 += 1

print(f"Num 0s: {bin_0}")
print(f"Num 1s: {bin_1}")

Num 0s: 17
Num 1s: 15

Iterating Through a List and Sorting

Applying Iteration

We can use for and while loops to iterate over loops! Then we can manipulate each element in the list for a certain purpose (adding, adding to another list, removing, etc.)

However, recall that each list item is at an index, and we can't exceed the number of indices that an element has, otherwise we get a IndexError: List out of range

The two programs below are both intended to display the total number of hours from a list of durations in minutes.

Program One:

{
totalMins ← 0
durations ← [32, 56, 28, 27]
FOR EACH duration IN durations
{
   totalMins ← totalMins + duration
}
totalHours ← totalMins / 60
DISPLAY(totalHours)
}

Program Two

{
totalMins ← 0
durations ← [32, 56, 28, 27]
FOR EACH duration IN durations
{
   totalMins ← totalMins + duration
   totalHours ← totalMins / 60
}
DISPLAY(totalHours)
}

a. Program 1 displays the correct total number of hours, while Program 2 does not.
b. Program 2 displays the correct total number of hours, while Program 1 does not.
c. Both programs display the correct total number of hours, but Program 1 unnecessarily repeats arithmetic operations.
d. Both programs display the correct total number of hours, but Program 2 unnecessarily repeats arithmetic operations.

Answer! Correct answer: d

A javelin thrower is writing code to track the distance of their throws and how far they are from their target distance. This is what they have so far:

{
totalDistance ← 0
targetDistance ← 90
throw1 ←  85.2
DISPLAY(targetDistance - throw1)
totalDistance ← totalDistance + throw1
throw2 ←  82.8
DISPLAY(targetDistance - throw2)
totalDistance ← totalDistance + throw2
throw3 ←  87.3
DISPLAY(targetDistance - throw3)
totalDistance ← totalDistance + throw3
avgDistance ← totalDistance / 3
DISPLAY(avgDistance)

A friend points out that they can reduce the complexity of their code by using the abstractions of lists and loops. The programmer decides to "refactor" the code, to rewrite it so that it produces the same output but is structured better.

Which of these is the best refactor of the code?
These are all closed so you can see each without being eye-bombed.

a targetDistance ← 90
throws ← [85.2, 82.8, 87.3]
totalDistance ← 0
FOR EACH throw IN throws
{
DISPLAY(targetDistance - throw)
totalDistance ← totalDistance + throw
}
avgDistance ← totalDistance / LENGTH(throws)
DISPLAY(avgDistance)

b targetDistance ← 90
throws ← [85.2, 82.8, 87.3]
totalDistance ← 0
FOR EACH throw IN throws
{
DISPLAY(targetDistance - throw)
totalDistance ← totalDistance + throw
}
avgDistance ← totalDistance / 3
DISPLAY(avgDistance)

c targetDistance ← 90
throws ← [85.2, 82.8, 87.3]
totalDistance ← 0
FOR EACH throw IN throws
{
DISPLAY(targetDistance - throw)
totalDistance ← totalDistance + throw
avgDistance ← totalDistance / LENGTH(throws)
}
DISPLAY(avgDistance)

d targetDistance ← 90
throws ← [85.2, 82.8, 87.3]
FOR EACH throw IN throws
{
totalDistance ← 0
DISPLAY(targetDistance - throw)
totalDistance ← totalDistance + throw
avgDistance ← totalDistance / LENGTH(throws)
}
DISPLAY(avgDistance)

e targetDistance ← 90
throws ← [85.2, 82.8, 87.3]
FOR EACH throw IN throws
{
totalDistance ← 0
DISPLAY(targetDistance - throw)
totalDistance ← totalDistance + throw
}
avgDistance ← totalDistance / LENGTH(throws)
DISPLAY(avgDistance)

Answer! Correct answer: a

The following code snippet processes a list of strings with a loop and conditionals:

{
words ← ["cab", "lab", "cable", "cables", "bales", "bale"]
wordScore ← 0
FOR EACH word IN words {
    IF (LEN(word) ≥ 5) {
        wordScore ← wordScore + 3
    } ELSE {
        IF (LEN(word) ≥ 4) {
            wordScore ← wordScore + 2
        } ELSE {
            IF (LEN(word) ≥ 3) {
                wordScore ← wordScore + 1
            }
        }
    }
}
DISPLAY(wordScore)
}

The code relies on one string procedure, LEN(string), which returns the number of characters in the string.
What value will this program display?

Answer! Correct answer: 13

Examples

Sorting algorithms

Insertion Sort:

  • Takes in unsorted list with numerical elements and returns with numerical elements in order
  • iterates through every element one at a time
  • check if element before the selected element is greater than or less than the selected element and adjust accordingly
arr = [9,1,5,6,3,7,2,8]
print(f"array before sort {arr}")
def insertion_sort(arr):
    for index in range(1,len(arr)): # repeats through length of the array
        value = arr[index]
        i = index - 1
        while i >= 0:
            if value < arr[i]:
                arr[i+1] = arr[i] # shift number in slot i to the right
                arr[i] = value # shift value left into slot i
                i = i - 1
            else:
                break

IS = insertion_sort(arr)
print(f"array after sort {arr}")

array before sort [9, 1, 5, 6, 3, 7, 2, 8]
array after sort [1, 2, 3, 5, 6, 7, 8, 9]

Homework

Sources
  • AP Classroom/AP Classroom Website
  • Khan Academy APCSP module
  • Coursera python courss by UMich
</div>