12. Lists

  • We saw that strings were a little different when compared to the other types we’ve seen (int, float, bool)

  • We can generalize the idea of strings to more types

    • A string is a collection of characters

    • We can use lists to have a collection of other types

Activity

Run the following code:

1some_list = [5, 7, 9, 10]
2print(some_list)
3print(some_list[0])
4print(some_list[1:3])
5print(type(some_list))

  1. Determine what types can be in a list.

  2. Can a list contain things of different types at the same time?

  3. How can you access the last element in a list?

  4. Can we find the length of a list?

  5. Is it possible to have a list of length 0? This would be an empty list, or a list with nothing in it.

12.1. Data Structures

  • The list is your first real data structure

  • As the name suggests, a data structure is some structure that holds data

  • Lists, although simple, are exceptionally useful and important

Activity

Apply what you know about loops, strings, and lists to solve the following problems — combining algorithms and data structures is a big part of programming. Hint: You will probably find the linear searches from the strings topic to be helpful.

  1. Write a function contains_while(needle, haystack) -> bool: that uses a while loop and returns True if needle is contained in the haystack and False otherwise.

  2. Write a function index_of_for(needle, haystack) -> int: that uses a for loop and returns the index of needle within the haystack or -1 if it is not found.

  3. Write some assert tests for both functions to verify correctness.

12.2. List Operators and Methods

  • Similar to strings, we can concatenate lists with the + operator

    1some_list = [5, 6, 7, 8, 9]
2some_other_list = ["this", "is", "a", "list"]
3bigger_list = some_list + some_other_list
4print(bigger_list)
5# Results in [5, 6, 7, 8, 9, 'this', 'is', 'a', 'list']

  • We can concatenate a list with itself multiple times using the * operator

    1some_list = [5, 6, 7, 8, 9]
2triple_list = some_list * 3
3print(triple_list)
4# Results in [5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9]

Activity

  1. Create some list and assign it to a variable some_list

  2. print out the list — print(some_list)

  3. After running the code, type some_list. and wait

    • Don’t forget the dot .

  4. Play around with some of the methods you see

12.3. Mutability

  • Although lists and strings have some things in common, one thing they do not have in common is mutability

    • Remember, strings are immutable

  • We can index strings and lists the same way to access individual elements

  • But unlike strings, we can also change the elements at a specific index

1another_list = ["a", "b", "c", "d", "e"]
2another_list[2] = "X"
3print(another_list)
4# Results in ['a', 'b', 'X', 'd', 'e']

12.4. Lists & Loops

  • Similar to how for loops made it easy to iterate over each character in a string

  • for loops can be used the same way on lists to iterate over each element in the list

    • for each thing in a collection of things

 1collection_of_things = ["Hello", 10, True, 100.001]
 2
 3for thing in collection_of_things:
 4  print(thing)
 5
 6# Results in
 7#   Hello
 8#   10
 9#   True
10#   100.001

  • Iterating over a collection of things is very common

  • Expect to start using for loops like this a lot

  • In fact, this was used in assignment 1 multiple times

    • Iterating over the contents of the file being read

    • Iterating over the list of (latitude, longitude) pairs

12.4.1. Range

  • range is a very handy function that we often use with for loops

  • It provides an easy way to loop over a specific range of numbers

1for i in range(5):
2  print(i)
3
4# Results in
5#   0
6#   1
7#   2
8#   3
9#   4

  • Notice that the integer 5 was specified in the range function, and the loop ran a total of 5 times

    • But because of 0 based indexing, the the number 5 is not actually included

  • A big reason we like to use for loops this way is because the syntax is so simple and clean

  • The above functionality can be achieved with a while loop, but the code needed is a little more cumbersome

 1i = 0
 2while i < 5:
 3  print(i)
 4  i += 1
 5
 6# Results in
 7#   0
 8#   1
 9#   2
10#   3
11#   4

Activity

Write a function beer_on_wall that prints out "n bottles of beer on the wall" for all n from 99 down to 0. This function must use a for loop with the range function.

The difficulty here is the need to count backwards.

Perhaps a read of the documentation can help.

12.4.2. Looping Over Indices and Enumerate

  • Sometimes it is important to know the indices of each element being printed out

  • For example, if the goal is to do a linear search to find the index of a given element, the following would be problematic

1def index_of_uhoh(needle, haystack):
2    for element in haystack:
3        if element == needle:
4            return "????" # How do I find the index?
5    return -1

  • Using the range function would help in this situation as we can use it to loop over each index in haystack

  • The only catch is that we need to actually index haystack

1def index_of(needle, haystack):
2    haystack_length = len(haystack)
3    for i in range(haystack_length):
4        if haystack[i] == needle:
5            return i
6    return -1

  • To make what is going on a little clearer, consider the following example

 1another_list = ["a", "b", "c", "d", "e"]
 2for i in range(len(another_list)):
 3    print(i, another_list[i])
 4
 5# Results in
 6#   0 a
 7#   1 b
 8#   2 c
 9#   3 d
10#   4 e

  • This loop prints out the index (i) along with the element at the given index (another_list[i])

  • This functionality is quite common and Python even provides a shorthand for achieving it — enumerate

 1another_list = ["a", "b", "c", "d", "e"]
 2for i, element in enumerate(another_list):
 3    print(i, element)
 4
 5# Results in
 6#   0 a
 7#   1 b
 8#   2 c
 9#   3 d
10#   4 e

  • Here there is no need to actually index the list since the element variable already has the value another_list[i]

12.5. For Next Class