You are previewing Data Structures and Algorithms in Python.
O'Reilly logo
Data Structures and Algorithms in Python

Book Description

Based on the authors' market leading data structures books in Java and C++, this textbook offers a comprehensive, definitive introduction to data structures in Python by respected authors. Data Structures and Algorithms in Python is the first mainstream object-oriented book available for the Python data structures course. Designed to provide a comprehensive introduction to data structures and algorithms, including their design, analysis, and implementation, the text will maintain the same general structure as Data Structures and Algorithms in Java and Data Structures and Algorithms in C++.

Table of Contents

  1. Cover Page
  2. Title Page
  3. Copyright
  4. Dedication
  5. Preface
    1. Book Features
    2. Online Resources
    3. Contents and Organization
    4. Prerequisites
    5. Relation to Computer Science Curriculum
    6. About the Authors
    7. Additional Books by These Authors
    8. Acknowledgments
  6. Contents
  7. Chapter 1: Python Primer
    1. 1.1 Python Overview
    2. 1.2 Objects in Python
    3. 1.3 Expressions, Operators, and Precedence
    4. 1.4 Control Flow
    5. 1.5 Functions
    6. 1.5.1 Information Passing
    7. 1.6 Simple Input and Output
    8. 1.7 Exception Handling
    9. 1.8 Iterators and Generators
    10. 1.9 Additional Python Conveniences
    11. 1.10 Scopes and Namespaces
    12. 1.11 Modules and the Import Statement
    13. 1.12 Exercises
  8. Chapter 2: Object-Oriented Programming
    1. 2.1 Goals, Principles, and Patterns
    2. 2.2 Software Development
    3. 2.3 Class Definitions
    4. 2.4 Inheritance
    5. 2.5 Namespaces and Object-Orientation
    6. 2.6 Shallow and Deep Copying
    7. 2.7 Exercises
  9. Chapter 3: Algorithm Analysis
    1. 3.1 Experimental Studies
    2. 3.2 The Seven Functions Used in This Book
    3. 3.3 Asymptotic Analysis
    4. 3.4 Simple Justification Techniques
    5. 3.5 Exercises
  10. Chapter 4: Recursion
    1. 4.1 Illustrative Examples
    2. 4.2 Analyzing Recursive Algorithms
    3. 4.3 Recursion Run Amok
    4. 4.4 Further Examples of Recursion
    5. 4.5 Designing Recursive Algorithms
    6. 4.6 Eliminating Tail Recursion
    7. 4.7 Exercises
  11. Chapter 5: Array-Based Sequences
    1. 5.1 Python's Sequence Types
    2. 5.2 Low-Level Arrays
    3. 5.3 Dynamic Arrays and Amortization
    4. 5.4 Efficiency of Python's Sequence Types
    5. 5.5 Using Array-Based Sequences
    6. 5.6 Multidimensional Data Sets
    7. 5.7 Exercises
  12. Chapter 6: Stacks, Queues, and Deques
    1. 6.1 Stacks
    2. 6.2 Queues
    3. 6.3 Double-Ended Queues
    4. 6.4 Exercises
  13. Chapter 7: Linked Lists
    1. 7.1 Singly Linked Lists
    2. 7.2 Circularly Linked Lists
    3. 7.3 Doubly Linked Lists
    4. 7.4 The Positional List ADT
    5. 7.5 Sorting a Positional List
    6. 7.6 Case Study: Maintaining Access Frequencies
    7. 7.7 Link-Based vs. Array-Based Sequences
    8. 7.8 Exercises
  14. Chapter 8: Trees
    1. 8.1 General Trees
    2. 8.2 Binary Trees
    3. 8.3 Implementing Trees
    4. 8.4 Tree Traversal Algorithms
    5. 8.5 Case Study: An Expression Tree
    6. 8.6 Exercises
  15. Chapter 9: Priority Queues
    1. 9.1 The Priority Queue Abstract Data Type
    2. 9.2 Implementing a Priority Queue
    3. 9.3 Heaps
    4. 9.4 Sorting with a Priority Queue
    5. 9.5 Adaptable Priority Queues
    6. 9.6 Exercises
  16. Chapter 10: Maps, Hash Tables, and Skip Lists
    1. 10.1 Maps and Dictionaries
    2. 10.2 Hash Tables
    3. 10.3 Sorted Maps
    4. 10.4 Skip Lists
    5. 10.5 Sets, Multisets, and Multimaps
    6. 10.6 Exercises
  17. Chapter 11: Search Trees
    1. 11.1 Binary Search Trees
    2. 11.2 Balanced Search Trees
    3. 11.3 AVL Trees
    4. 11.4 Splay Trees
    5. 11.5 (2,4) Trees
    6. 11.6 Red-Black Trees
    7. 11.7 Exercises
  18. Chapter 12: Sorting and Selection
    1. 12.1 Why Study Sorting Algorithms?
    2. 12.2 Merge-Sort
    3. 12.3 Quick-Sort
    4. 12.4 Studying Sorting through an Algorithmic Lens
    5. 12.5 Comparing Sorting Algorithms
    6. 12.6 Python's Built-In Sorting Functions
    7. 12.7 Selection
    8. 12.8 Exercises
  19. Chapter 13: Text Processing
    1. 13.1 Abundance of Digitized Text
    2. 13.2 Pattern-Matching Algorithms
    3. 13.3 Dynamic Programming
    4. 13.4 Text Compression and the Greedy Method
    5. 13.5 Tries
    6. 13.6 Exercises
  20. Chapter 14: Graph Algorithms
    1. 14.1 Graphs
    2. 14.2 Data Structures for Graphs
    3. 14.3 Graph Traversals
    4. 14.4 Transitive Closure
    5. 14.5 Directed Acyclic Graphs
    6. 14.6 Shortest Paths
    7. 14.7 Minimum Spanning Trees
    8. 14.8 Exercises
  21. Chapter 15: Memory Management and B-Trees
    1. 15.1 Memory Management
    2. 15.2 Memory Hierarchies and Caching
    3. 15.3 External Searching and B-Trees
    4. 15.4 External-Memory Sorting
    5. 15.5 Exercises
  22. Appendix A: Character Strings in Python
  23. Appendix B: Useful Mathematical Facts
  24. Bibliography
  25. Index