High Performance Python

Chapter 3. Lists and Tuples

Questions You’ll Be Able to Answer After This Chapter

• What are lists and tuples good for?
• What is the complexity of a lookup in a list/tuple?
• How is that complexity achieved?
• What are the differences between lists and tuples?
• How does appending to a list work?
• When should I use lists and tuples?

One of the most important things in writing efficient programs is understanding the guarantees of the data structures you use. In fact, a large part of performant programming is understanding what questions you are trying to ask of your data and picking a data structure that can answer these questions quickly. In this chapter, we will talk about the kinds of questions that lists and tuples can answer quickly, and how they do it.

Lists and tuples are a class of data structures called arrays. An array is simply a flat list of data with some intrinsic ordering. This a priori knowledge of the ordering is important: by knowing that data in our array is at a specific position, we can retrieve it in O(1)! In addition, arrays can be implemented in multiple ways. This demarcates another line between lists and tuples: lists are dynamic arrays while tuples are static arrays.

Let’s unpack these previous statements a bit. System memory on a computer can be thought of as a series of numbered buckets, each capable of holding a number. These numbers can be used to represent any variables we care about (integers, floats, strings, or other data structures), since they are simply ...