Lists

from os.path import basename, exists

def download(url):
    """Download a file if it isn't already here, and return its filename."""
    filename = basename(url)
    if not exists(filename):
        from urllib.request import urlretrieve

        local, _ = urlretrieve(url, filename)
        print("Downloaded " + str(local))
    return filename

download('https://github.com/porttack/working-in-python/raw/v3/working_in_python_v2.py');
download('https://github.com/AllenDowney/ThinkPython/raw/v3/diagram.py');

import working_in_python_v2 as working_in_python
# apcsp:begin type="note" chapter="09"
working_in_python.enable_docstring_reminders()
# apcsp:end

9. Lists#

This chapter presents one of Python’s most useful built-in types, lists. You will also learn more about objects and what can happen when multiple variables refer to the same object.

In the exercises at the end of the chapter, we’ll make a word list and use it to search for special words like palindromes and anagrams.

9.1. A list is a sequence#

Like a string, a list is a sequence of values. In a string, the values are characters; in a list, they can be any type. The values in a list are called elements.

There are several ways to create a new list; the simplest is to enclose the elements in square brackets ([ and ]). For example, here is a list of two integers.

numbers = [42, 123]

And here’s a list of three strings.

cheeses = ['Cheddar', 'Edam', 'Gouda']

The elements of a list don’t have to be the same type. The following list contains a string, a float, an integer, and even another list.

t = ['spam', 2.0, 5, [10, 20]]

A list within another list is nested.

A list that contains no elements is called an empty list; you can create one with empty brackets, [].

empty = []

The len function returns the length of a list.

len(cheeses)

The length of an empty list is 0.

len(empty)

A common way to represent variables on paper is to write the name with an arrow pointing to its value. This kind of figure is called a state diagram because it shows what state each of the variables is in. We’ll use state diagrams throughout the book to represent a model of how Python stores variables and their values.

The following figure shows the state diagram for cheeses, numbers and empty.

from diagram import make_list, Binding, Value

list1 = make_list(cheeses, dy=-0.3, offsetx=0.17)
binding1 = Binding(Value('cheeses'), list1)

list2 = make_list(numbers, dy=-0.3, offsetx=0.17)
binding2 = Binding(Value('numbers'), list2)

list3 = make_list(empty, dy=-0.3, offsetx=0.1)
binding3 = Binding(Value('empty'), list3)

from diagram import diagram, adjust, Bbox

width, height, x, y = [3.66, 1.58, 0.45, 1.2]
ax = diagram(width, height)
bbox1 = binding1.draw(ax, x, y)
bbox2 = binding2.draw(ax, x+2.25, y)
bbox3 = binding3.draw(ax, x+2.25, y-1.0)

bbox = Bbox.union([bbox1, bbox2, bbox3])
#adjust(x, y, bbox)

Lists are represented by boxes with the word “list” outside and the numbered elements of the list inside.

9.2. Lists are mutable#

To read an element of a list, we can use the bracket operator. The index of the first element is 0.

cheeses[0]

Unlike strings, lists are mutable. When the bracket operator appears on the left side of an assignment, it identifies the element of the list that will be assigned.

numbers[1] = 17
numbers

The second element of numbers, which used to be 123, is now 17.

List indices work the same way as string indices:

Any integer expression can be used as an index.
If you try to read or write an element that does not exist, you get an IndexError.
If an index has a negative value, it counts backward from the end of the list.

The in operator works on lists – it checks whether a given element appears anywhere in the list.

'Edam' in cheeses

'Wensleydale' in cheeses

Although a list can contain another list, the nested list still counts as a single element – so in the following list, there are only four elements.

t = ['spam', 2.0, 5, [10, 20]]
len(t)

And 10 is not considered to be an element of t because it is an element of a nested list, not t.

10 in t

9.3. List slices#

The slice operator works on lists the same way it works on strings. The following example selects the second and third elements from a list of four letters.

letters = ['a', 'b', 'c', 'd']
letters[1:3]

If you omit the first index, the slice starts at the beginning.

letters[:2]

If you omit the second, the slice goes to the end.

letters[2:]

So if you omit both, the slice is a copy of the whole list.

letters[:]

Another way to copy a list is to use the list function.

list(letters)

Because list is the name of a built-in function, you should avoid using it as a variable name.

9.4. List operations#

The + operator concatenates lists.

t1 = [1, 2]
t2 = [3, 4]
t1 + t2

The * operator repeats a list a given number of times.

['spam'] * 4

No other mathematical operators work with lists, but the built-in function sum adds up the elements.

sum(t1)

And min and max find the smallest and largest elements.

min(t1)

max(t2)

9.5. List methods#

Python provides methods that operate on lists. For example, append adds a new element to the end of a list:

letters.append('e')
letters

extend takes a list as an argument and appends all of the elements:

letters.extend(['f', 'g'])
letters

There are two methods that remove elements from a list. If you know the index of the element you want, you can use pop.

t = ['a', 'b', 'c']
t.pop(1)

The return value is the element that was removed. And we can confirm that the list has been modified.

If you know the element you want to remove (but not the index), you can use remove:

t = ['a', 'b', 'c']
t.remove('b')

The return value from remove is None. But we can confirm that the list has been modified.

If the element you ask for is not in the list, that’s a ValueError.

t.remove('d')

9.6. Lists and strings#

A string is a sequence of characters and a list is a sequence of values, but a list of characters is not the same as a string. To convert from a string to a list of characters, you can use the list function.

s = 'spam'
t = list(s)
t

The list function breaks a string into individual letters. If you want to break a string into words, you can use the split method:

s = 'pining for the fjords'
t = s.split()
t

An optional argument called a delimiter specifies which characters to use as word boundaries. The following example uses a hyphen as a delimiter.

s = 'ex-parrot'
t = s.split('-')
t

If you have a list of strings, you can concatenate them into a single string using join. join is a string method, so you have to invoke it on the delimiter and pass the list as an argument.

delimiter = ' '
t = ['pining', 'for', 'the', 'fjords']
s = delimiter.join(t)
s

In this case the delimiter is a space character, so join puts a space between words. To join strings without spaces, you can use the empty string, '', as a delimiter.

9.7. Looping through a list#

You can use a for statement to loop through the elements of a list.

for cheese in cheeses:
    print(cheese)

For example, after using split to make a list of words, we can use for to loop through them.

s = 'pining for the fjords'

for word in s.split():
    print(word)

A for loop over an empty list never runs the indented statements.

for x in []:
    print('This never happens.')

9.8. Sorting lists#

Python provides a built-in function called sorted that sorts the elements of a list.

scramble = ['c', 'a', 'b']
sorted(scramble)

The original list is unchanged.

scramble

sorted works with any kind of sequence, not just lists. So we can sort the letters in a string like this.

sorted('letters')

The result is a list. To convert the list to a string, we can use join.

''.join(sorted('letters'))

With an empty string as the delimiter, the elements of the list are joined with nothing between them.

9.9. Objects and values#

If we run these assignment statements:

a = 'banana'
b = 'banana'

We know that a and b both refer to a string, but we don’t know whether they refer to the same string. There are two possible states, shown in the following figure.

from diagram import Frame, Stack

s = 'banana'
bindings = [Binding(Value(name), Value(repr(s))) for name in 'ab']
frame1 = Frame(bindings, dy=-0.25)

binding1 = Binding(Value('a'), Value(repr(s)), dy=-0.11)
binding2 = Binding(Value('b'), draw_value=False, dy=0.11)
frame2 = Frame([binding1, binding2], dy=-0.25)

stack = Stack([frame1, frame2], dx=1.7, dy=0)

width, height, x, y = [2.85, 0.76, 0.17, 0.51]
ax = diagram(width, height)
bbox = stack.draw(ax, x, y)
# adjust(x, y, bbox)

In the diagram on the left, a and b refer to two different objects that have the same value. In the diagram on the right, they refer to the same object. To check whether two variables refer to the same object, you can use the is operator.

a = 'banana'
b = 'banana'
a is b

In this example, Python only created one string object, and both a and b refer to it. But when you create two lists, you get two objects.

a = [1, 2, 3]
b = [1, 2, 3]
a is b

So the state diagram looks like this.

t = [1, 2, 3]
binding1 = Binding(Value('a'), Value(repr(t)))
binding2 = Binding(Value('b'), Value(repr(t)))
frame = Frame([binding1, binding2], dy=-0.25)

width, height, x, y = [1.16, 0.76, 0.21, 0.51]
ax = diagram(width, height)
bbox = frame.draw(ax, x, y)
# adjust(x, y, bbox)

In this case we would say that the two lists are equivalent, because they have the same elements, but not identical, because they are not the same object. If two objects are identical, they are also equivalent, but if they are equivalent, they are not necessarily identical.

9.10. Aliasing#

If a refers to an object and you assign b = a, then both variables refer to the same object.

a = [1, 2, 3]
b = a
b is a

So the state diagram looks like this.

t = [1, 2, 3]
binding1 = Binding(Value('a'), Value(repr(t)), dy=-0.11)
binding2 = Binding(Value('b'), draw_value=False, dy=0.11)
frame = Frame([binding1, binding2], dy=-0.25)

width, height, x, y = [1.11, 0.81, 0.17, 0.56]
ax = diagram(width, height)
bbox = frame.draw(ax, x, y)
# adjust(x, y, bbox)

The association of a variable with an object is called a reference. In this example, there are two references to the same object.

An object with more than one reference has more than one name, so we say the object is aliased. If the aliased object is mutable, changes made with one name affect the other. In this example, if we change the object b refers to, we are also changing the object a refers to.

b[0] = 5
a

So we would say that a “sees” this change. Although this behavior can be useful, it is error-prone. In general, it is safer to avoid aliasing when you are working with mutable objects.

For immutable objects like strings, aliasing is not as much of a problem. In this example:

a = 'banana'
b = 'banana'

It almost never makes a difference whether a and b refer to the same string or not.

9.11. List arguments#

When you pass a list to a function, the function gets a reference to the list. If the function modifies the list, the caller sees the change. For example, pop_first uses the list method pop to remove the first element from a list.

def pop_first(lst):
    return lst.pop(0)

We can use it like this.

letters = ['a', 'b', 'c']
pop_first(letters)

The return value is the first element, which has been removed from the list – as we can see by displaying the modified list.

letters

In this example, the parameter lst and the variable letters are aliases for the same object, so the state diagram looks like this:

lst = make_list('abc', dy=-0.3, offsetx=0.1)
binding1 = Binding(Value('letters'), draw_value=False)
frame1 = Frame([binding1], name='__main__', loc='left')

binding2 = Binding(Value('lst'), draw_value=False, dx=0.61, dy=0.35)
frame2 = Frame([binding2], name='pop_first', loc='left', offsetx=0.08)

stack = Stack([frame1, frame2], dx=-0.3, dy=-0.5)

width, height, x, y = [2.04, 1.24, 1.06, 0.85]
ax = diagram(width, height)
bbox1 = stack.draw(ax, x, y)
bbox2 = lst.draw(ax, x+0.5, y)
bbox = Bbox.union([bbox1, bbox2])
adjust(x, y, bbox)

Passing a reference to an object as an argument to a function creates a form of aliasing. If the function modifies the object, those changes persist after the function is done.

9.12. Making a word list#

In the previous chapter, we read the file words.txt and searched for words with certain properties, like using the letter e. But we read the entire file many times, which is not efficient. It is better to read the file once and put the words in a list. The following loop shows how.

download('https://raw.githubusercontent.com/AllenDowney/ThinkPython/v3/words.txt');

word_list = []

for line in open('words.txt'):
    word = line.strip()
    word_list.append(word)
    
len(word_list)

Before the loop, word_list is initialized with an empty list. Each time through the loop, the append method adds a word to the end. When the loop is done, there are more than 113,000 words in the list.

Another way to do the same thing is to use read to read the entire file into a string.

string = open('words.txt').read()
len(string)

The result is a single string with more than a million characters. We can use the split method to split it into a list of words.

word_list = string.split()
len(word_list)

Now, to check whether a string appears in the list, we can use the in operator. For example, 'demotic' is in the list.

'demotic' in word_list

But 'contrafibularities' is not.

'contrafibularities' in word_list

And I have to say, I’m anaspeptic about it.

9.13. Debugging#

Note that most list methods modify the argument and return None. This is the opposite of the string methods, which return a new string and leave the original alone.

If you are used to writing string code like this:

word = 'plumage!'
word = word.strip('!')
word

It is tempting to write list code like this:

t = [1, 2, 3]
t = t.remove(3)           # WRONG!

remove modifies the list and returns None, so next operation you perform with t is likely to fail.

t.remove(2)

This error message takes some explaining. An attribute of an object is a variable or method associated with it. In this case, the value of t is None, which is a NoneType object, which does not have a attribute named remove, so the result is an AttributeError.

If you see an error message like this, you should look backward through the program and see if you might have called a list method incorrectly.

9.14. Glossary#

list: An object that contains a sequence of values.

element: One of the values in a list or other sequence.

nested list: A list that is an element of another list.

state diagram: A graphical representation of a set of variables and the values they refer to.

delimiter: A character or string used to indicate where a string should be split.

equivalent: Having the same value.

identical: Being the same object (which implies equivalence).

reference: The association between a variable and its value.

aliased: If there is more than one variable that refers to an object, the object is aliased.

attribute: One of the named values associated with an object.

See also: the full vocabulary glossary collects every term in this book, alphabetized, alongside the complete AP CSP exam vocabulary list.

9.15. Exercises#

# This cell tells Jupyter to provide detailed debugging information
# when a runtime error occurs. Run it before working on the exercises.

%xmode Verbose

9.15.1. Exercise#

Two words are anagrams if you can rearrange the letters from one to spell the other. For example, tops is an anagram of stop.

One way to check whether two words are anagrams is to sort the letters in both words. If the lists of sorted letters are the same, the words are anagrams.

Write a function called is_anagram that takes two strings and returns True if they are anagrams.

To get you started, here’s an outline of the function with doctests.

def is_anagram(word1, word2):
    """Checks whether two words are anagrams.
    
    >>> is_anagram('tops', 'stop')
    True
    >>> is_anagram('skate', 'takes')
    True
    >>> is_anagram('tops', 'takes')
    False
    >>> is_anagram('skate', 'stop')
    False
    """
    return None

You can use doctest to test your function.

from doctest import run_docstring_examples

def run_doctests(func):
    run_docstring_examples(func, globals(), name=func.__name__)

run_doctests(is_anagram)

Using your function and the word list, find all the anagrams of takes.

9.15.2. Exercise#

Python provides a built-in function called reversed that takes as an argument a sequence of elements – like a list or string – and returns a reversed object that contains the elements in reverse order.

reversed('parrot')

If you want the reversed elements in a list, you can use the list function.

list(reversed('parrot'))

Or if you want them in a string, you can use the join method.

''.join(reversed('parrot'))

So we can write a function that reverses a word like this.

def reverse_word(word):
    return ''.join(reversed(word))

A palindrome is a word that is spelled the same backward and forward, like “noon” and “rotator”. Write a function called is_palindrome that takes a string argument and returns True if it is a palindrome and False otherwise.

Here’s an outline of the function with doctests you can use to check your function.

def is_palindrome(word):
    """Check if a word is a palindrome.
    
    >>> is_palindrome('bob')
    True
    >>> is_palindrome('alice')
    False
    >>> is_palindrome('a')
    True
    >>> is_palindrome('')
    True
    """
    return False

run_doctests(is_palindrome)

You can use the following loop to find all of the palindromes in the word list with at least 7 letters.

for word in word_list:
    if len(word) >= 7 and is_palindrome(word):
        print(word)

9.15.3. Exercise#

Write a function called reverse_sentence that takes as an argument a string that contains any number of words separated by spaces. It should return a new string that contains the same words in reverse order. For example, if the argument is “Reverse this sentence”, the result should be “Sentence this reverse”.

Hint: You can use the capitalize methods to capitalize the first word and convert the other words to lowercase.

To get you started, here’s an outline of the function with doctests.

def reverse_sentence(input_string):
    '''Reverse the words in a string and capitalize the first.
    
    >>> reverse_sentence('Reverse this sentence')
    'Sentence this reverse'

    >>> reverse_sentence('Python')
    'Python'

    >>> reverse_sentence('')
    ''

    >>> reverse_sentence('One for all and all for one')
    'One for all and all for one'
    '''
    return None

run_doctests(reverse_sentence)

9.15.4. Exercise#

Write a function called total_length that takes a list of strings and returns the total length of the strings. The total length of the words in word_list should be \(902{,}728\).

9.16. Homework#

Required work is five problems: whichever of Problem 1 or Problem 2, plus Problems 3-5, about 30 minutes total. Doing both 1 and 2 is fine, but the second one earns no additional credit. The time check below must be filled in. The extra credit at the end is optional and never substitutes for a required problem.

Every function you write in this section needs a docstring, the same as chapter 4 on. Use run_doctests (defined above) to check your work before you submit.

Note: the exercises above (is_anagram, is_palindrome, reverse_sentence, and total_length) are practice. They aren’t graded. This is the graded homework.

9.16.1. Problem 1: first_last (do 1 or 2)#

Write a function called first_last that takes a list and returns a new list containing just its first and last elements, using indexing. The docstring and its doctests are already written below; write only the body, then run the cell to check your work.

def first_last(lst):
    """Return a new list containing just the first and last elements of lst.

    >>> first_last([1, 2, 3, 4])
    [1, 4]
    >>> first_last(['a', 'b'])
    ['a', 'b']
    >>> first_last([5])
    [5, 5]
    """
    # Solution goes here


run_doctests(first_last)

9.16.2. Problem 2: without_first_last (do 1 or 2)#

Write a function called without_first_last that takes a list and returns a new list with the first and last elements removed, using slicing. The docstring and its doctests are already written below; write only the body, then run the cell to check your work.

def without_first_last(lst):
    """Return a new list with the first and last elements of lst removed.

    >>> without_first_last([1, 2, 3, 4])
    [2, 3]
    >>> without_first_last(['a', 'b', 'c'])
    ['b']
    >>> without_first_last([1, 2])
    []
    """
    # Solution goes here


run_doctests(without_first_last)

9.16.3. Problem 3: how many long words?#

Write a function called long_words that takes a list of words and a length n, and returns a list of the words that have at least n letters. Use a loop and append, the same way the chapter built up lists one element at a time. The docstring and its doctests are already written below; write only the body.

def long_words(word_list, n):
    """Return a list of the words in word_list with at least n letters.

    >>> long_words(['cat', 'elephant', 'dog', 'rhinoceros'], 6)
    ['elephant', 'rhinoceros']
    """
    # Solution goes here


run_doctests(long_words)

Now call your function on word_list with n = 12.

If your loop is right, the result has 7170 words, out of 113,783 in the list.

9.16.4. Problem 4: debug remove_all#

The function below is supposed to remove every occurrence of item from lst. Its doctests are correct. Run them, read the failure report, and fix the function so all tests pass. Do not change the docstring.

def remove_all(lst, item):
    """Remove every occurrence of item from lst, and return the result.

    >>> remove_all([1, 2, 1, 3, 1], 1)
    [2, 3]
    >>> remove_all(['a', 'b', 'a'], 'a')
    ['b']
    """
    while item in lst:
        lst = lst.remove(item)
    return lst


run_doctests(remove_all)

9.16.5. Problem 5: reflection#

This chapter’s Debugging section explained why t = t.remove(x) breaks a list, because remove returns None. Problem 4 was exactly that bug. Explain in your own words why reassigning lst inside the loop causes the problem, and why removing the reassignment fixes it.

Answer in the markdown cell below.

Type your answer here.

9.16.6. Time check#

This is graded on being filled in, not on the numbers. There’s no right answer, and low numbers don’t score better. If this chapter took you three hours, I need to know that. These are estimates: nobody expects you to have timed yourself, so a rough number is exactly what’s wanted.

# Fill this in before you submit. Rough estimates are fine, and low numbers
# don't score better. Don't count time on the extra credit below.
# chapter_minutes -> reading the chapter and its practice exercises
# extra_exercises_minutes -> the five numbered problems above
# longest -> which problem took longest, e.g. 1
chapter_minutes = 0
extra_exercises_minutes = 0
longest = 0

from working_in_python import time_check
time_check(chapter_minutes, extra_exercises_minutes, longest)

9.17. Extra credit: the most common word length#

Worth 0.5 points. Open to you once you’ve finished the five required problems above; never a substitute for any of them.

Using a dictionary that maps each word length to how many words in word_list have that length, and a single loop, find out which word length is most common.

Answer in the markdown cell below: which length wins, and how many words have it?

# Your code here

Type your answer here.

9.17.1. Finished? Copy your work#

This isn’t part of the problems above. It’s a tool. Run the cell below to copy your Homework section (including anything you’ve run) as rich text, so it pastes into a document already formatted. Works in JupyterLite and in VS Code/a Codespace – click the button either way, it detects which one you are in.

working_in_python.show_copy_homework_button("chap09.ipynb")

9.17.2. OR save your homework for submission#

Run the cell below. It writes two files into this same folder – chap09-homework.ipynb and chap09-homework.md – containing everything from “Homework” above, including whatever you wrote and ran. Submit those two files, not the whole chapter.

working_in_python.write_homework_files("chap09.ipynb")

Working in Python — modified by Eric Brown for a high school Computer Science Principles class. Source and modifications: github.com/porttack/working-in-python

Think Python: 3rd Edition

Code license: MIT License

Text license: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International

9.18. Standards alignment#

AP CSP: 3.10 Lists (Big Idea 3, 30–35% of the exam) — this chapter’s own topic. Also 3.2 Data Abstraction, shared with chapters 10–11, and 1.4 Identifying and Correcting Errors, headers only. California 9-12: 9-12.AP.13, a direct match. Also 9-12.AP.12 and its specialty counterpart 9-12S.AP.12, shared with chapter 7’s linear search. CSTA 2026: HS-ALG-PS-01 and HS-PRO-VD-16, shared with chapters 10–11. CA CTE (ICT): C4.7, shared with chapters 8, 10, 11, and 13.

A list groups related values under one name instead of a pile of separately numbered variables — California’s own phrasing for 9-12.AP.13, and the same idea AP calls data abstraction and CSTA calls picking the right built-in structure.

Lists

Contents

9. Lists#

9.1. A list is a sequence#

9.2. Lists are mutable#

9.3. List slices#

9.4. List operations#

9.5. List methods#

9.6. Lists and strings#

9.7. Looping through a list#

9.8. Sorting lists#

9.9. Objects and values#

9.10. Aliasing#

9.11. List arguments#

9.12. Making a word list#

9.13. Debugging#

9.14. Glossary#

9.15. Exercises#

9.15.1. Exercise#

9.15.2. Exercise#

9.15.3. Exercise#

9.15.4. Exercise#

9.16. Homework#

9.16.1. Problem 1: first_last (do 1 or 2)#

9.16.2. Problem 2: without_first_last (do 1 or 2)#

9.16.3. Problem 3: how many long words?#

9.16.4. Problem 4: debug remove_all#

9.16.5. Problem 5: reflection#

9.16.6. Time check#

9.17. Extra credit: the most common word length#

9.17.1. Finished? Copy your work#

9.17.2. OR save your homework for submission#

9.18. Standards alignment#