Data Structures & Algorithms in Python

Data Structures & Algorithms in Python

by John Canning, Alan Broder, Robert Lafore
Released October 2022
Publisher(s): Addison-Wesley Professional
ISBN: 9780134855912

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

This practical introduction to data structures and algorithms can help every programmer who wants to write more efficient software. Building on Robert Lefore's legendary Java-based guide, this book helps you understand exactly how data structures and algorithms operate. You'll learn how to efficiently apply them with the enormously popular Python language and scale your code to handle today's big data challenges.

Throughout, the authors focus on real-world examples, communicate key ideas with intuitive, interactive visualizations, and limit complexity and math to what you need to improve performance. Step-by-step, they introduce arrays, sorting, stacks, queues, linked lists, recursion, binary trees, 2-3-4 trees, hash tables, spatial data structures, graphs, and more. Their code examples and illustrations are so clear, you can understand them even if you're a near-beginner, or your experience is with other procedural or object-oriented languages.

  • Build core computer science skills that take you beyond merely "writing code"

  • Learn how data structures make programs (and programmers) more efficient

  • See how data organization and algorithms affect how much you can do with today's, and tomorrow's, computing resources

  • Develop data structure implementation skills you can use in any language

  • Choose the best data structure(s) and algorithms for each programming problem-and recognize which ones to avoid

Table of contents

  1. Cover
  2. Halftitle Page
  3. Title Page
  4. Copyright Page
  5. Pearson’s Commitment to Diversity, Equity, and Inclusion
  6. Dedication Page
  7. Contents
  8. Table of Contents
  9. Acknowledgments
    1. Acknowledgments to the First Edition
    2. Acknowledgments to the Second Edition
  10. About the Author
  11. Introduction
    1. Who This Book Is For
    2. What You Need to Know Before You Read This Book
    3. What You Can Learn from This Book
    4. Structure
    5. History
  12. 1. Overview
    1. What Are Data Structures and Algorithms?
    2. Overview of Data Structures
    3. Overview of Algorithms
    4. Some Definitions
    5. Programming in Python
    6. Object-Oriented Programming
    7. Summary
    8. Questions
    9. Experiments
  13. 2. Arrays
    1. The Array Visualization Tool
    2. Using Python Lists to Implement the Array Class
    3. The Ordered Array Visualization Tool
    4. Python Code for an Ordered Array Class
    5. Logarithms
    6. Storing Objects
    7. Big O Notation
    8. Why Not Use Arrays for Everything?
    9. Summary
    10. Questions
    11. Experiments
    12. Programming Projects
  14. 3. Simple Sorting
    1. How Would You Do It?
    2. Bubble Sort
    3. Selection Sort
    4. Insertion Sort
    5. Comparing the Simple Sorts
    6. Summary
    7. Questions
    8. Experiments
    9. Programming Projects
  15. 4. Stacks and Queues
    1. Different Structures for Different Use Cases
    2. Stacks
    3. Queues
    4. Priority Queues
    5. Parsing Arithmetic Expressions
    6. Summary
    7. Questions
    8. Experiments
    9. Programming Projects
  16. 5. Linked Lists
    1. Links
    2. The Linked List Visualization Tool
    3. A Simple Linked List
    4. Linked List Efficiency
    5. Abstract Data Types and Objects
    6. Ordered Lists
    7. Doubly Linked Lists
    8. Circular Lists
    9. Iterators
    10. Summary
    11. Questions
    12. Experiments
    13. Programming Projects
  17. 6. Recursion
    1. Triangular Numbers
    2. Factorials
    3. Anagrams
    4. A Recursive Binary Search
    5. The Tower of Hanoi
    6. Sorting with mergesort
    7. Eliminating Recursion
    8. Some Interesting Recursive Applications
    9. Summary
    10. Questions
    11. Experiments
    12. Programming Projects
  18. 7. Advanced Sorting
    1. Shellsort
    2. Partitioning
    3. Quicksort
    4. Degenerates to O(N2) Performance
    5. Radix Sort
    6. Timsort
    7. Summary
    8. Questions
    9. Experiments
    10. Programming Projects
  19. 8. Binary Trees
    1. Why Use Binary Trees?
    2. Tree Terminology
    3. An Analogy
    4. How Do Binary Search Trees Work?
    5. Finding a Node
    6. Inserting a Node
    7. Traversing the Tree
    8. Finding Minimum and Maximum Key Values
    9. Deleting a Node
    10. The Efficiency of Binary Search Trees
    11. Trees Represented as Arrays
    12. Printing Trees
    13. Duplicate Keys
    14. The BinarySearchTreeTester.py Program
    15. The Huffman Code
    16. Summary
    17. Questions
    18. Experiments
    19. Programming Projects
  20. 9. 2-3-4 Trees and External Storage
    1. Introduction to 2-3-4 Trees
    2. The Tree234 Visualization Tool
    3. Python Code for a 2-3-4 Tree
    4. Efficiency of 2-3-4 Trees
    5. 2-3 Trees
    6. External Storage
    7. Summary
    8. Questions
    9. Experiments
    10. Programming Projects
  21. 10. AVL and Red-Black Trees
    1. Our Approach to the Discussion
    2. Balanced and Unbalanced Trees
    3. AVL Trees
    4. The Efficiency of AVL Trees
    5. Red-Black Trees
    6. Using the Red-Black Tree Visualization Tool
    7. Experimenting with the Visualization Tool
    8. Rotations in Red-Black Trees
    9. Inserting a New Node
    10. Deletion
    11. The Efficiency of Red-Black Trees
    12. 2-3-4 Trees and Red-Black Trees
    13. Red-Black Tree Implementation
    14. Summary
    15. Questions
    16. Experiments
    17. Programming Projects
  22. 11. Hash Tables
    1. Introduction to Hashing
    2. Open Addressing
    3. Separate Chaining
    4. Hash Functions
    5. Hashing Efficiency
    6. Hashing and External Storage
    7. Summary
    8. Questions
    9. Experiments
    10. Programming Projects
  23. 12. Spatial Data Structures
    1. Spatial Data
    2. Computing Distances Between Points
    3. Circles and Bounding Boxes
    4. Searching Spatial Data
    5. Lists of Points
    6. Grids
    7. Quadtrees
    8. Theoretical Performance and Optimizations
    9. Practical Considerations
    10. Further Extensions
    11. Summary
    12. Questions
    13. Experiments
    14. Programming Projects
  24. 13. Heaps
    1. Introduction to Heaps
    2. The Heap Visualization Tool
    3. Python Code for Heaps
    4. A Tree-Based Heap
    5. Heapsort
    6. Order Statistics
    7. Summary
    8. Questions
    9. Experiments
    10. Programming Projects
  25. 14. Graphs
    1. Introduction to Graphs
    2. Traversal and Search
    3. Minimum Spanning Trees
    4. Topological Sorting
    5. Connectivity in Directed Graphs
    6. Summary
    7. Questions
    8. Experiments
    9. Programming Projects
  26. 15. Weighted Graphs
    1. Minimum Spanning Tree with Weighted Graphs
    2. The Shortest-Path Problem
    3. The All-Pairs Shortest-Path Problem
    4. Efficiency
    5. Intractable Problems
    6. Summary
    7. Questions
    8. Experiments
    9. Programming Projects
  27. 16. What to Use and Why
    1. Analyzing the Problem
    2. Foundational Data Structures
    3. Special-Ordering Data Structures
    4. Sorting
    5. Specialty Data Structures
    6. External Storage
    7. Onward
  28. Appendix A. Running the Visualizations
    1. For Developers: Running and Changing the Visualizations
    2. For Managers: Downloading and Running the Visualizations
    3. For Others: Viewing the Visualizations on the Internet
    4. Using the Visualizations
  29. Appendix B. Further Reading
    1. Data Structures and Algorithms
    2. Object-Oriented Programming Languages
    3. Object-Oriented Design (OOD) and Software Engineering
  30. Appendix C. Answers to Questions
    1. Chapter 1, “Overview”
    2. Chapter 2, “Arrays”
    3. Chapter 3, “Simple Sorting”
    4. Chapter 4, “Stacks and Queues”
    5. Chapter 5, “Linked Lists”
    6. Chapter 6, “Recursion”
    7. Chapter 7, “Advanced Sorting”
    8. Chapter 8, “Binary Trees”
    9. Chapter 9, “2-3-4 Trees and External Storage”
    10. Chapter 10, “AVL and Red-Black Trees”
    11. Chapter 11, “Hash Tables”
    12. Chapter 12, “Spatial Data Structures”
    13. Chapter 13, “Heaps”
    14. Chapter 14, “Graphs”
    15. Chapter 15, “Weighted Graphs”

Product information

  • Title: Data Structures & Algorithms in Python
  • Author(s): John Canning, Alan Broder, Robert Lafore
  • Release date: October 2022
  • Publisher(s): Addison-Wesley Professional
  • ISBN: 9780134855912