This Book is Available on BuyUBooks.
com
[Link]
This Book is Available on [Link]
[Link]
This Book is Available on [Link]
Data Structures and
Algorithms in Python
Michael T. Goodrich
Department of Computer Science
University of California, Irvine
Roberto Tamassia
Department of Computer Science
Brown University
Michael H. Goldwasser
Department of Mathematics and Computer Science
Saint Louis University
[Link]
This Book is Available on [Link]
VP & PUBLISHER Don Fowley
EXECUTIVE EDITOR Beth Lang Golub
EDITORIAL PROGRAM ASSISTANT Katherine Willis
MARKETING MANAGER Christopher Ruel
DESIGNER Kenji Ngieng
SENIOR PRODUCTION MANAGER Janis Soo
ASSOCIATE PRODUCTION MANAGER Joyce Poh
This book was set in LaTEX by the authors. Printed and bound by Courier Westford.
The cover was printed by Courier Westford.
This book is printed on acid free paper.
Founded in 1807, John Wiley & Sons, Inc. has been a valued source of knowledge and understanding for
more than 200 years, helping people around the world meet their needs and fulfill their aspirations. Our
company is built on a foundation of principles that include responsibility to the communities we serve and
where we live and work. In 2008, we launched a Corporate Citizenship Initiative, a global effort to address
the environmental, social, economic, and ethical challenges we face in our business. Among the issues we are
addressing are carbon impact, paper specifications and procurement, ethical conduct within our business and
among our vendors, and community and charitable support. For more information, please visit our website:
[Link]/go/citizenship.
Copyright © 2013 John Wiley & Sons, Inc. All rights reserved. No part of this publication may be
reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical,
photocopying, recording, scanning or otherwise, except as permitted under Sections 107 or 108 of
the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or
authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc. 222
Rosewood Drive, Danvers, MA 01923, website [Link]. Requests to the Publisher for permission
should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken,
NJ 07030-5774, (201)748-6011, fax (201)748-6008, website [Link]
Evaluation copies are provided to qualified academics and professionals for review purposes only, for use
in their courses during the next academic year. These copies are licensed and may not be sold or transferred
to a third party. Upon completion of the review period, please return the evaluation copy to Wiley. Return
instructions and a free of charge return mailing label are available at [Link]/go/returnlabel. If you
have chosen to adopt this textbook for use in your course, please accept this book as your complimentary desk
copy. Outside of the United States, please contact your local sales representative.
Printed in the United States of America
10 9 8 7 6 5 4 3 2 1
[Link]
This Book is Available on [Link]
To Karen, Paul, Anna, and Jack
– Michael T. Goodrich
To Isabel
– Roberto Tamassia
To Susan, Calista, and Maya
– Michael H. Goldwasser
[Link]
This Book is Available on [Link]
[Link]
This Book is Available on [Link]
Preface
The design and analysis of efficient data structures has long been recognized as a
vital subject in computing and is part of the core curriculum of computer science
and computer engineering undergraduate degrees. Data Structures and Algorithms
in Python provides an introduction to data structures and algorithms, including their
design, analysis, and implementation. This book is designed for use in a beginning-
level data structures course, or in an intermediate-level introduction to algorithms
course. We discuss its use for such courses in more detail later in this preface.
To promote the development of robust and reusable software, we have tried to
take a consistent object-oriented viewpoint throughout this text. One of the main
ideas of the object-oriented approach is that data should be presented as being en-
capsulated with the methods that access and modify them. That is, rather than
simply viewing data as a collection of bytes and addresses, we think of data ob-
jects as instances of an abstract data type (ADT), which includes a repertoire of
methods for performing operations on data objects of this type. We then empha-
size that there may be several different implementation strategies for a particular
ADT, and explore the relative pros and cons of these choices. We provide complete
Python implementations for almost all data structures and algorithms discussed,
and we introduce important object-oriented design patterns as means to organize
those implementations into reusable components.
Desired outcomes for readers of our book include that:
• They have knowledge of the most common abstractions for data collections
(e.g., stacks, queues, lists, trees, maps).
• They understand algorithmic strategies for producing efficient realizations of
common data structures.
• They can analyze algorithmic performance, both theoretically and experi-
mentally, and recognize common trade-offs between competing strategies.
• They can wisely use existing data structures and algorithms found in modern
programming language libraries.
• They have experience working with concrete implementations for most foun-
dational data structures and algorithms.
• They can apply data structures and algorithms to solve complex problems.
In support of the last goal, we present many example applications of data structures
throughout the book, including the processing of file systems, matching of tags
in structured formats such as HTML, simple cryptography, text frequency analy-
sis, automated geometric layout, Huffman coding, DNA sequence alignment, and
search engine indexing.
v
[Link]
This Book is Available on [Link]
vi Preface
Book Features
This book is based upon the book Data Structures and Algorithms in Java by
Goodrich and Tamassia, and the related Data Structures and Algorithms in C++
by Goodrich, Tamassia, and Mount. However, this book is not simply a translation
of those other books to Python. In adapting the material for this book, we have
significantly redesigned the organization and content of the book as follows:
• The code base has been entirely redesigned to take advantage of the features
of Python, such as use of generators for iterating elements of a collection.
• Many algorithms that were presented as pseudo-code in the Java and C++
versions are directly presented as complete Python code.
• In general, ADTs are defined to have consistent interface with Python’s built-
in data types and those in Python’s collections module.
• Chapter 5 provides an in-depth exploration of the dynamic array-based un-
derpinnings of Python’s built-in list, tuple, and str classes. New Appendix A
serves as an additional reference regarding the functionality of the str class.
• Over 450 illustrations have been created or revised.
• New and revised exercises bring the overall total number to 750.
Online Resources
This book is accompanied by an extensive set of online resources, which can be
found at the following Web site:
[Link]/college/goodrich
Students are encouraged to use this site along with the book, to help with exer-
cises and increase understanding of the subject. Instructors are likewise welcome
to use the site to help plan, organize, and present their course materials. Included
on this Web site is a collection of educational aids that augment the topics of this
book, for both students and instructors. Because of their added value, some of these
online resources are password protected.
For all readers, and especially for students, we include the following resources:
• All the Python source code presented in this book.
• PDF handouts of Powerpoint slides (four-per-page) provided to instructors.
• A database of hints to all exercises, indexed by problem number.
For instructors using this book, we include the following additional teaching aids:
• Solutions to hundreds of the book’s exercises.
• Color versions of all figures and illustrations from the book.
• Slides in Powerpoint and PDF (one-per-page) format.
The slides are fully editable, so as to allow an instructor using this book full free-
dom in customizing his or her presentations. All the online resources are provided
at no extra charge to any instructor adopting this book for his or her course.
[Link]
This Book is Available on [Link]
Preface vii
Contents and Organization
The chapters for this book are organized to provide a pedagogical path that starts
with the basics of Python programming and object-oriented design. We then add
foundational techniques like algorithm analysis and recursion. In the main portion
of the book, we present fundamental data structures and algorithms, concluding
with a discussion of memory management (that is, the architectural underpinnings
of data structures). Specifically, the chapters for this book are organized as follows:
1. Python Primer
2. Object-Oriented Programming
3. Algorithm Analysis
4. Recursion
5. Array-Based Sequences
6. Stacks, Queues, and Deques
7. Linked Lists
8. Trees
9. Priority Queues
10. Maps, Hash Tables, and Skip Lists
11. Search Trees
12. Sorting and Selection
13. Text Processing
14. Graph Algorithms
15. Memory Management and B-Trees
A. Character Strings in Python
B. Useful Mathematical Facts
A more detailed table of contents follows this preface, beginning on page xi.
Prerequisites
We assume that the reader is at least vaguely familiar with a high-level program-
ming language, such as C, C++, Python, or Java, and that he or she understands the
main constructs from such a high-level language, including:
• Variables and expressions.
• Decision structures (such as if-statements and switch-statements).
• Iteration structures (for loops and while loops).
• Functions (whether stand-alone or object-oriented methods).
For readers who are familiar with these concepts, but not with how they are ex-
pressed in Python, we provide a primer on the Python language in Chapter 1. Still,
this book is primarily a data structures book, not a Python book; hence, it does not
give a comprehensive treatment of Python.
[Link]
This Book is Available on [Link]
viii Preface
We delay treatment of object-oriented programming in Python until Chapter 2.
This chapter is useful for those new to Python, and for those who may be familiar
with Python, yet not with object-oriented programming.
In terms of mathematical background, we assume the reader is somewhat famil-
iar with topics from high-school mathematics. Even so, in Chapter 3, we discuss
the seven most-important functions for algorithm analysis. In fact, sections that use
something other than one of these seven functions are considered optional, and are
indicated with a star (). We give a summary of other useful mathematical facts,
including elementary probability, in Appendix B.
Relation to Computer Science Curriculum
To assist instructors in designing a course in the context of the IEEE/ACM 2013
Computing Curriculum, the following table describes curricular knowledge units
that are covered within this book.
Knowledge Unit Relevant Material
AL/Basic Analysis Chapter 3 and Sections 4.2 & 12.2.4
AL/Algorithmic Strategies Sections 12.2.1, 13.2.1, 13.3, & 13.4.2
AL/Fundamental Data Structures Sections 4.1.3, 5.5.2, 9.4.1, 9.3, 10.2, 11.1, 13.2,
and Algorithms Chapter 12 & much of Chapter 14
Sections 5.3, 10.4, 11.2 through 11.6, 12.3.1,
AL/Advanced Data Structures
13.5, 14.5.1, & 15.3
AR/Memory System Organization Chapter 15
and Architecture
DS/Sets, Relations and Functions Sections 10.5.1, 10.5.2, & 9.4
DS/Proof Techniques Sections 3.4, 4.2, 5.3.2, 9.3.6, & 12.4.1
DS/Basics of Counting Sections 2.4.2, 6.2.2, 12.2.4, 8.2.2 & Appendix B
DS/Graphs and Trees Much of Chapters 8 and 14
DS/Discrete Probability Sections 1.11.1, 10.2, 10.4.2, & 12.3.1
Much of the book, yet especially Chapter 2 and
PL/Object-Oriented Programming
Sections 7.4, 9.5.1, 10.1.3, & 11.2.1
PL/Functional Programming Section 1.10
SDF/Algorithms and Design Sections 2.1, 3.3, & 12.2.1
SDF/Fundamental Programming Chapters 1 & 4
Concepts
Chapters 6 & 7, Appendix A, and Sections 1.2.1,
SDF/Fundamental Data Structures
5.2, 5.4, 9.1, & 10.1
SDF/Developmental Methods Sections 1.7 & 2.2
SE/Software Design Sections 2.1 & 2.1.3
Mapping IEEE/ACM 2013 Computing Curriculum knowledge units to coverage in
this book.
[Link]