Data Structures & Algorithms in Python (Developer's Library)

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