If you thought that data structures and algorithms were all just theory, you’re missing out on what they can do for your code. Learn to use Big O notation to make your code run faster by orders of magnitude. Choose from data structures such as hash tables, trees, and graphs to increase your code’s efficiency exponentially. With simple language and clear diagrams, this book makes this complex topic accessible, no matter your background. This new edition features practice exercises in every chapter, and new chapters on topics such as dynamic programming and heaps and tries. Get the hands-on info you need to master data structures and algorithms for your day-to-day work.
Algorithms and data structures are much more than abstract concepts. Mastering them enables you to write code that runs faster and more efficiently, which is particularly important for today’s web and mobile apps. Take a practical approach to data structures and algorithms, with techniques and real-world scenarios that you can use in your daily production code, with examples in JavaScript, Python, and Ruby. This new and revised second edition features new chapters on recursion, dynamic programming, and using Big O in your daily work.
Use Big O notation to measure and articulate the efficiency of your code, and modify your algorithm to make it faster. Find out how your choice of arrays, linked lists, and hash tables can dramatically affect the code you write. Use recursion to solve tricky problems and create algorithms that run exponentially faster than the alternatives. Dig into advanced data structures such as binary trees and graphs to help scale specialized applications such as social networks and mapping software. You’ll even encounter a single keyword that can give your code a turbo boost. Practice your new skills with exercises in every chapter, along with detailed solutions.
Use these techniques today to make your code faster and more scalable.
Author(s): Jay Wengrow
Edition: 2
Publisher: Pragmatic Bookshelf
Preface
Who Is This Book For?
What’s New in the Second Edition
What’s in This Book?
How to Read This Book
Code Examples
Online Resources
Acknowledgments
Connecting
Why Data Structures Matter
Data Structures
The Array: The Foundational Data Structure
Measuring Speed
Reading
Searching
Insertion
Deletion
Sets: How a Single Rule Can Affect Efficiency
Wrapping Up
Exercises
Why Algorithms Matter
Ordered Arrays
Searching an Ordered Array
Binary Search
Binary Search vs. Linear Search
Wrapping Up
Exercises
O Yes! Big O Notation
Big O: How Many Steps Relative to N Elements?
The Soul of Big O
An Algorithm of the Third Kind
Logarithms
O (log N) Explained
Practical Examples
Wrapping Up
Exercises
Speeding Up Your Code with Big O
Bubble Sort
Bubble Sort in Action
The Efficiency of Bubble Sort
A Quadratic Problem
A Linear Solution
Wrapping Up
Exercises
Optimizing Code with and Without Big O
Selection Sort
Selection Sort in Action
The Efficiency of Selection Sort
Ignoring Constants
Big O Categories
Wrapping Up
Exercises
Optimizing for Optimistic Scenarios
Insertion Sort
Insertion Sort in Action
The Efficiency of Insertion Sort
The Average Case
A Practical Example
Wrapping Up
Exercises
Big O in Everyday Code
Mean Average of Even Numbers
Word Builder
Array Sample
Average Celsius Reading
Clothing Labels
Count the Ones
Palindrome Checker
Get All the Products
Password Cracker
Wrapping Up
Exercises
Blazing Fast Lookup with Hash Tables
Hash Tables
Hashing with Hash Functions
Building a Thesaurus for Fun and Profit, but Mainly Profit
Hash Table Lookups
Dealing with Collisions
Making an Efficient Hash Table
Hash Tables for Organization
Hash Tables for Speed
Wrapping Up
Exercises
Crafting Elegant Code with Stacks and Queues
Stacks
Abstract Data Types
Stacks in Action
The Importance of Constrained Data Structures
Queues
Queues in Action
Wrapping Up
Exercises
Recursively Recurse with Recursion
Recurse Instead of Loop
The Base Case
Reading Recursive Code
Recursion in the Eyes of the Computer
Filesystem Traversal
Wrapping Up
Exercises
Learning to Write in Recursive
Recursive Category: Repeatedly Execute
Recursive Category: Calculations
Top-Down Recursion: A New Way of Thinking
The Staircase Problem
Anagram Generation
Wrapping Up
Exercises
Dynamic Programming
Unnecessary Recursive Calls
The Little Fix for Big O
The Efficiency of Recursion
Overlapping Subproblems
Dynamic Programming through Memoization
Dynamic Programming through Going Bottom-Up
Wrapping Up
Exercises
Recursive Algorithms for Speed
Partitioning
Quicksort
The Efficiency of Quicksort
Quicksort in the Worst-Case Scenario
Quickselect
Sorting as a Key to Other Algorithms
Wrapping Up
Exercises
Node-Based Data Structures
Linked Lists
Implementing a Linked List
Reading
Searching
Insertion
Deletion
Efficiency of Linked List Operations
Linked Lists in Action
Doubly Linked Lists
Queues as Doubly Linked Lists
Wrapping Up
Exercises
Speeding Up All the Things with Binary Search Trees
Trees
Binary Search Trees
Searching
Insertion
Deletion
Binary Search Trees in Action
Binary Search Tree Traversal
Wrapping Up
Exercises
Keeping Your Priorities Straight with Heaps
Priority Queues
Heaps
Heap Properties
Heap Insertion
Looking for the Last Node
Heap Deletion
Heaps vs. Ordered Arrays
The Problem of the Last Node…Again
Arrays as Heaps
Heaps as Priority Queues
Wrapping Up
Exercises
It Doesn’t Hurt to Trie
Tries
Storing Words
Trie Search
The Efficiency of Trie Search
Trie Insertion
Building Autocomplete
Completing Autocomplete
Tries with Values: A Better Autocomplete
Wrapping Up
Exercises
Connecting Everything with Graphs
Graphs
Directed Graphs
Object-Oriented Graph Implementation
Graph Search
Depth-First Search
Breadth-First Search
The Efficiency of Graph Search
Weighted Graphs
Dijkstra’s Algorithm
Wrapping Up
Exercises
Dealing with Space Constraints
Big O of Space Complexity
Trade-Offs Between Time and Space
The Hidden Cost of Recursion
Wrapping Up
Exercises
Techniques for Code Optimization
Prerequisite: Determine Your Current Big O
Start Here: The Best-Imaginable Big O
Magical Lookups
Recognizing Patterns
Greedy Algorithms
Change the Data Structure
Wrapping Up
Parting Thoughts
Exercises
Exercise Solutions
Chapter 1
Chapter 2
Chapter 3
Chapter 4
Chapter 5
Chapter 6
Chapter 7
Chapter 8
Chapter 9
Chapter 1
Chapter 11
Chapter 12
Chapter 13
Chapter 14
Chapter 15
Chapter 16
Chapter 17
Chapter 18
Chapter 19
Chapter 20
