Safari, the world’s most comprehensive technology and business learning platform.

Find the exact information you need to solve a problem on the fly, or go deeper to master the technologies and skills you need to succeed

Start Free Trial

No credit card required

O'Reilly logo
Fundamentals of Python®: Data Structures

Book Description

Written for computer programming students, hobbyists, and professionals, FUNDAMENTALS OF PYTHON: DATA STRUCTURES is an introduction to object-oriented design and data structures using the popular Python programming language. The level of instruction assumes at least one semester of programming in an object-oriented language such as Java, C++, or Python. Through the step-by-step instruction and exercises in this book, you'll cover such topics as the design of collection classes with polymorphism and inheritance, multiple implementations of collection interfaces, and the analysis of the space/time tradeoffs of different collection implementations (specifically array-based implementations and link-based implementations). Collections covered include sets, lists, stacks, queues, trees, dictionaries, and graphs. Get ready to dig into Python data structures with FUNDAMENTALS OF PYTHON: DATA STRUCTURES. - See more at:

Table of Contents

  1. Cover Page
  2. Title Page
  3. Copyright Page
  4. Dedication
  5. Acknowledgments
  6. About the Author
  8. Introduction
  9. Chapter 1 Basic Python Programming
    1. Basic Program Elements
    2. Control Statements
    3. Strings and Their Operations
    4. Built-In Python Collections and Their Operations
    5. Creating New Functions
    6. Catching Exceptions
    7. Files and Their Operations
    8. Creating New Classes
    9. Projects
  10. Chapter 2 An Overview of Collections
    1. Collection Types
    2. Operations on Collections
    3. Implementations of Collections
    4. Summary
    5. Review Questions
    6. Projects
  11. Chapter 3 Searching, Sorting, and Complexity Analysis
    1. Measuring the Efficiency of Algorithms
    2. Complexity Analysis
    3. Search Algorithms
    4. Basic Sort Algorithms
    5. Faster Sorting
    6. An Exponential Algorithm: Recursive Fibonacci
    7. Case Study: An Algorithm Profiler
    8. Summary
    9. Review Questions
    10. Projects
  12. Chapter 4 Arrays and Linked Structures
    1. The Array Data Structure
    2. Operations on Arrays
    3. Two-Dimensional Arrays (Grids)
    4. Linked Structures
    5. Operations on Singly Linked Structures
    6. Variations on a Link
    7. Summary
    8. Review Questions
    9. Projects
  13. Chapter 5 Interfaces, Implementations, and Polymorphism
    1. Developing an Interface
    2. Developing an Array-Based Implementation
    3. Developing a Link-Based Implementation
    4. Run-Time Performance of the Two Bag Implementations
    5. Testing the Two Bag Implementations
    6. Diagramming the Bag Resource with UML
    7. Summary
    8. Review Questions
    9. Projects
  14. Chapter 6 Inheritance and Abstract Classes
    1. Using Inheritance to Customize an Existing Class
    2. Using Abstract Classes to Eliminate Redundant Code
    3. An Abstract Class for All Collections
    4. Summary
    5. Review Questions
    6. Projects
  15. Chapter 7 Stacks
    1. Overview of Stacks
    2. Using a Stack
    3. Three Applications of Stacks
    4. Implementations of Stacks
    5. Case Study: Evaluating Postfix Expressions
    6. Summary
    7. Review Questions
    8. Projects
  16. Chapter 8 Queues
    1. Overview of Queues
    2. The Queue Interface and Its Use
    3. Two Applications of Queues
    4. Implementations of Queues
    5. Case Study: Simulating a Supermarket Checkout Line
    6. Priority Queues
    7. Case Study: An Emergency Room Scheduler
    8. Summary
    9. Review Questions
    10. Projects
  17. Chapter 9 Lists
    1. Overview of Lists
    2. Using Lists
    3. Applications of Lists
    4. List Implementations
    5. Implementing a List Iterator
    6. Case Study: Developing a Sorted List
    7. Summary
    8. Review Questions
    9. Projects
  18. Chapter 10 Trees
    1. An Overview of Trees
    2. Why Use a Tree?
    3. The Shape of Binary Trees
    4. Three Common Applications of Binary Trees
    5. Binary Tree Traversals
    6. Developing a Binary Search Tree
    7. Recursive Descent Parsing and Programming Languages
    8. Case Study: Parsing and Expression Trees
    9. An Array Implementation of Binary Trees
    10. Implementing Heaps
    11. Summary
    12. Review Questions
    13. Projects
  19. Chapter 11 Sets and Dictionaries
    1. Using Sets
    2. The Python set Class
    3. Array-Based and Linked Implementations of Sets
    4. Using Dictionaries
    5. Array-Based and Linked Implementations of Dictionaries
    6. Hashing Strategies
    7. Case Study: Profiling Hashing Strategies
    8. Hashing Implementation of Sets
    9. Hashing Implementation of Dictionaries
    10. Sorted Sets and Dictionaries
    11. Summary
    12. Review Questions
    13. Projects
  20. Chapter 12 Graphs
    1. Graph Terminology
    2. Why Use Graphs?
    3. Representations of Graphs
    4. Graph Traversals
    5. Trees Within Graphs
    6. Topological Sort
    7. The Shortest-Path Problem
    8. Developing a Graph Collection
    9. Case Study: Testing Graph Algorithms
    10. Summary
    11. Review Questions
    12. Projects
  21. Appendix A Collection Framework for Python Programmers
  22. Index