Chapter 3. 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 knowing 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 a flat list of data with some intrinsic ordering. Usually in these sorts of data structures, the relative ordering of the elements is as important as the elements themselves! In addition, this a priori knowledge of the ordering is incredibly valuable: by knowing that data in our array is at a specific position, we can retrieve it in O(1)!¹ There are also many ways to implement arrays, and each solution has its own useful features and guarantees. This is why in Python we have two types of arrays: lists and tuples. Lists are dynamic arrays that let us modify and resize the data we are storing, while tuples are static arrays whose contents are fixed and ...