Chapter 13
Lists

In this chapter you will learn:

• What lists are and why they are useful.
• How to create empty and nonempty lists.
• How to append values to a list.
• How to measure the length of a list.
• How to access list items via their indices.
• How to parse lists via the for loop.
• How to check if a given item is in a list.
• How to remove and return ("pop") items from a list.
• How to add lists and multiply them with integers.
• How to delete items from a list.
  

As usual, first we will cover the necessary theory and then we will show you some cool applications of lists at the end of this chapter.

13.1. What are lists and why they are useful

You already know how to create and use numerical, text string and even Boolean variables. Variables are like containers - every variable can store one value. In contrast to this, a list is like a cargo train which can store many different values.

---

---

The values in a list are ordered, so one knows which one is the first and which one is the last. They can have different types - a list may contain numerical values, text strings, Booleans, and even other lists. Items can be dynamically added and/or removed at runtime as needed.

Lists are Karel’s (and Python’s) most powerful data structure. The implementation of lists in Karel is compatible with Python, although Karel does not provide all the list functionality offered by Python.

13.2. Creating empty and nonempty lists

Throughout this chapter, you will see that there are strong similarities between lists and text strings. To begin with, an empty text string txt is created via txt = ” or txt = ~~. It is also possible to create a nonempty text string such as msg = ’Hi there!’.

An empty list is created using a pair of empty square brackets:

Do not use parentheses () or curly braces {} as they have a different meaning. You can also create a non-empty list:

A list can contain text strings,

Boolean values,

and the types of values in a list can even be mixed:

13.3. Appending items to a list

Items can be appended to the end of a (empty or nonempty) list using the list method append:

Output:

---

---

Lists are perfect for storing several values at once. Like today, when Karel needs to remember the positions of all the orchids:

---

---

He can do it as follows:

Output:

---

---

13.4. Measuring the length of a list

From Section 9.5 (page 763) you know that len(txt) returns the length of the text string txt. Similarly, when working with lists, calling len(L) will return the length of the list L. The length of a list means the number of its items. For illustration, let’s change the last line of the previous program, and display the length of the list X:

Output:

---

---

13.5. Accessing list items via their indices

You already know from Section 9.8 (page 772) how to access individual characters in a text string using their indices. For example, txt[0] is the first character in the text string txt, txt[1] is the second character, etc. Also, txt[-1] is the last character of the text string, txt[-2] is the second from the end, and so on.

When working with lists, it is possible to access individual list items exactly in the same way. For example, X[0] is the first item of the list X, X[1] is its second item, X[-1] is its last item, etc.

Today, Karel is still counting orchids:

---

---

But now he wants to know the position of the first orchid, and the position of the last one before his home square:

Output:

---

---

13.6. Creating a list of lists

Karel is still in the jungle counting orchids. But now, there can be multiple of them per grid square:

---

---

He needs to not only remember their positions, but also their numbers. This naturally leads to a list of pairs of the form "position, number". In fact, each of these pairs can be a two-item list, and these lists can be stored in a list. Hence one obtains a list of lists. Here is the code from Section 13.3 (page 1101), updated for the current situation:

Output:

---

---

13.7. Parsing lists with the for loop

Let’s stay with the previous example for another moment:

---

---

The text output was too compact, and it would be good to make it nicer. It should say something like "I found 2 orchids in column 3, 1 orchid in column 5, ..." etc.

You already know from Section 9.6 (page 766) how to parse text strings one character at a time. Lists can be parsed one item at a time exactly in the same way. For example, with the list X from the previous example, the code

will display

---

---

This is still not very nice, but we are getting closer. Each item x in the list X is a two-item list containing a position-number pair. Therefore we know that x[0] is the position and x[1] the corresponding number. Therefore, a nicer output can be arranged as follows:

This will display

---

---

Although there is a minor English imperfection, this is way better than before. If we wanted to improve line 3, we would have to include one extra condition:

Final output:

---

---

13.8. Checking if an item is in a list

You already know from Section 9.12 (page 809) that Karel can check for the presence of a substring in a text string using the keyword in. The same keyword can be used to check whether an item is present in a list. For illustration, the list X we created in Section 13.3 (page 1101) provides information about the column positions of orchids:

---

---

Karel can now use the list to ask whether there is an orchid in column number 5:

Output:

---

---

Or, he can ask whether there is an orchid in column number 10:

Output:

---

---

The list of two-item lists X that we created in Section 13.6 (page 1119) provides information about positions of orchids and their numbers:

---

---

Karel can use it to ask whether there are two orchids in column number 7:

Output:

---

---

13.9. Removing and returning ("popping") items from a list

At the beginning of this chapter we said that lists can easily be modified at runtime, but so far we only showed you how to append new items at the end. Karel (and Python) provide the list method pop which will remove and return items from a list. Let’s look at a sample list names = [’Ann’, ’Brett’, ’Charles’, ’Dave’, ’Emily’, ’Frank’].

Calling names.pop() will remove and return the last item, ’Frank’:

Output:

---

---

The method pop can also be called with the index of a specific item we want to remove and return. For example, calling names.pop(0) will remove and return the item ’Ann’ from the list:

Output:

---

---

And as a last example, calling names.pop(-2) will remove and return the second item from the end which is ’Dave’:

Output:

---

---

13.10. Adding lists

From Section 9.3 (page 754) you know that text strings can be added just as numbers. Lists can be added in the same way:

Output:

---

---

And one can even use the += operator to extend a list with another one:

Output:

---

---

13.11. Multiplying lists with integers

The analogy between lists and text strings goes further. In Section 9.4 (page 760) you have seen that a text string can be multiplied with a positive integer N, which will copy and paste its contents N times. The same can be done with lists:

Output:

---

---

And as you would expect, the *= operator works as well:

Output:

---

---

13.12. Deleting items from a list

Sometimes one just needs to delete an item from a list (and destroy it) because there is no use for it. This can be done using the keyword del. Typing del L[i] will delete and destroy the item with index i from the list L. Let’s illustrate this on another Morse example:

Output:

---

---

13.13. Gardener

Let’s show a task which would be difficult to solve without using a list. Karel is working in his garden. In front of him is a flower bed with tulips:

---

---

The robot does not know the length of the flower bed, or the number or positions of the tulips. His task is to create an identical flower bed on the other side of the wall:

---

---

He has enough tulips in his bag to do it.

The best way to solve this task is to follow the wall until its end, and store the column positions of all the tulips in a list T. Then, on the other side of the wall, Karel will walk towards his home square. In each grid square he will check whether his gpsx coordinate is in the list T. If the value is found, he will place a tulip. Here is the corresponding code:

13.14. Expedition Antarctica

The following task is interesting not only because it would be very difficult to solve without using a list, but also because it involves a discussion of different ways to store data in the list.

Karel is part of an expedition to Antarctica, and his task is to find a way through ice and snow. He should record his path in such a way that later he can draw a map.

---

---

Clearly, the robot can use the First Maze Algorithm to pass through the maze. He will need to store the information about his path in a list (say P). But this can be done in many different ways.

Option #1: For every step he makes, Karel can add 0 to the list P. When he needs to turn right, he can add True. When he needs to turn left, he can add False.

Option #2: At every turn Karel can add to the list P a triplet [gpsx, gpsy, R] where R is True if the path goes to the right and False otherwise.

Option #3: Karel can count his steps and store their number in a variable N. At every turn he can add to the list P a pair [N, R] where R is True if the path goes to the right and False otherwise. He would reset N back to 0 after every turn.

Let’s evaluate these three options: The sample path shown above involves 77 steps and 20 turns. So, option #1 would produce a list of length 77 + 20 = 97. Option #2 would add three values at every turn, hence the resulting list would have length 3 ⋅ 20 = 60. And finally, option #3 would add two values at every turn, yielding a list of length 2 ⋅ 20 = 40. Since option #3 is most memory-efficient, we will implement it.

The following program will do it. Make sure to read the comments in the code:

Output:

---

---

Awesome - first part done! The second part of the task is to use this list to draw a map of the path. The program is very simple. Karel will draw the path by placing beepers he has in his bag:

Let’s start from a clean sheet:

---

---

And here is Karel’s drawing after the program finishes:

---

---

13.15. Copycat

Karel’s next task is to copy a random pattern from the left box and paste it in the box on the right:

---

---

Hence the robot needs to visit all grid squares in the left box, learn where the pumpkins are, then visit all grid squares in the box on the right again, and place pumpkins at the corresponding positions.

Rather than writing a complicated code for the robot to visit all grid squares in the first box, let’s use the method from the previous section. Here is a path through the first box, stored in a list named H:

We will use this list and the previous program to visit all grid squares in the left box, and then also in the box on the right. This time we will use a Boolean list B to store the pattern. Initially, this list will be empty. After each step, Karel will append to it True if he found a pumpkin, and False if he did not. In the box on the right, the list B will be used to place pumpkins at the corresponding positions. Here is the complete code:

When the program finishes, Karel has reproduced the pattern from the left box:

---

---

To make sure that the program works for other patterns as well, let’s try at least one more:

---

---

And here is the corresponding output:

---

---

13.16. Review questions

Friendly reminder - for every question either none, one, or several answers may be correct.

---

Table of Contents

• About
• 1. Introduction
• 2. Basic Commands
• 3. Counting Loop
• 4. Conditions
• 5. Conditional Loop
• 6. Custom Commands
• 7. Variables
• 8. Functions
• 9. Text Strings
• 10. Testing Your Programs
• 11. Boolean Values, Variables, Expressions, and Functions
• 12. Randomness and Probability
• 13. Lists
• 14. Recursion
• 15. Advanced Applications
• Appendix A. Karel App in NCLab
• Appendix B. Self-Paced Karel Course in NCLab