Data Structures and Algorithms in Python

Chapter 5

Array-Based Sequences

Contents

5.1 Python's Sequence Types

5.2 Low-Level Arrays

5.2.1 Referential Arrays

5.2.2 Compact Arrays in Python

5.3 Dynamic Arrays and Amortization

5.3.1 Implementing a Dynamic Array

5.3.2 Amortized Analysis of Dynamic Arrays

5.3.3 Python's List Class

5.4 Efficiency of Python's Sequence Types

5.4.1 Python's List and Tuple Classes

5.4.2 Python's String Class

5.5 Using Array-Based Sequences

5.5.1 Storing High Scores for a Game

5.5.2 Sorting a Sequence

5.5.3 Simple Cryptography

5.6 Multidimensional Data Sets

5.7 Exercises

5.1 Python's Sequence Types

In this chapter, we explore Python's various “sequence” classes, namely the built-in list, tuple, and str classes. There is significant commonality between these classes, most notably: each supports indexing to access an individual element of a sequence, using a syntax such as seq[k], and each uses a low-level concept known as an array to represent the sequence. However, there are significant differences in the abstractions that these classes represent, and in the way that instances of these classes are represented internally by Python. Because these classes are used so widely in Python programs, and because they will become building blocks upon which we will develop more complex data structures, it is imperative that we establish a clear understanding of both the public behavior and inner workings ...