A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

by Jay Wengrow
Released August 2020
Publisher(s): Pragmatic Bookshelf
ISBN: 9781680507225

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.

Buy on ebooks.com
Start your free trial

Book description

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.

Publisher resources

View/Submit Errata

Table of contents

  1.  Preface
    1. Who Is This Book For?
    2. What’s New in the Second Edition
    3. What’s in This Book?
    4. How to Read This Book
    5. Code Examples
    6. Online Resources
    7. Acknowledgments
    8. Connecting
  2. 1. Why Data Structures Matter
    1. Data Structures
    2. The Array: The Foundational Data Structure
    3. Measuring Speed
    4. Reading
    5. Searching
    6. Insertion
    7. Deletion
    8. Sets: How a Single Rule Can Affect Efficiency
    9. Wrapping Up
    10. Exercises
  3. 2. Why Algorithms Matter
    1. Ordered Arrays
    2. Searching an Ordered Array
    3. Binary Search
    4. Binary Search vs. Linear Search
    5. Wrapping Up
    6. Exercises
  4. 3. O Yes! Big O Notation
    1. Big O: How Many Steps Relative to N Elements?
    2. The Soul of Big O
    3. An Algorithm of the Third Kind
    4. Logarithms
    5. O(log N) Explained
    6. Practical Examples
    7. Wrapping Up
    8. Exercises
  5. 4. Speeding Up Your Code with Big O
    1. Bubble Sort
    2. Bubble Sort in Action
    3. The Efficiency of Bubble Sort
    4. A Quadratic Problem
    5. A Linear Solution
    6. Wrapping Up
    7. Exercises
  6. 5. Optimizing Code with and Without Big O
    1. Selection Sort
    2. Selection Sort in Action
    3. The Efficiency of Selection Sort
    4. Ignoring Constants
    5. Big O Categories
    6. Wrapping Up
    7. Exercises
  7. 6. Optimizing for Optimistic Scenarios
    1. Insertion Sort
    2. Insertion Sort in Action
    3. The Efficiency of Insertion Sort
    4. The Average Case
    5. A Practical Example
    6. Wrapping Up
    7. Exercises
  8. 7. Big O in Everyday Code
    1. Mean Average of Even Numbers
    2. Word Builder
    3. Array Sample
    4. Average Celsius Reading
    5. Clothing Labels
    6. Count the Ones
    7. Palindrome Checker
    8. Get All the Products
    9. Password Cracker
    10. Wrapping Up
    11. Exercises
  9. 8. Blazing Fast Lookup with Hash Tables
    1. Hash Tables
    2. Hashing with Hash Functions
    3. Building a Thesaurus for Fun and Profit, but Mainly Profit
    4. Hash Table Lookups
    5. Dealing with Collisions
    6. Making an Efficient Hash Table
    7. Hash Tables for Organization
    8. Hash Tables for Speed
    9. Wrapping Up
    10. Exercises
  10. 9. Crafting Elegant Code with Stacks and Queues
    1. Stacks
    2. Abstract Data Types
    3. Stacks in Action
    4. The Importance of Constrained Data Structures
    5. Queues
    6. Queues in Action
    7. Wrapping Up
    8. Exercises
  11. 10. Recursively Recurse with Recursion
    1. Recurse Instead of Loop
    2. The Base Case
    3. Reading Recursive Code
    4. Recursion in the Eyes of the Computer
    5. Filesystem Traversal
    6. Wrapping Up
    7. Exercises
  12. 11. Learning to Write in Recursive
    1. Recursive Category: Repeatedly Execute
    2. Recursive Category: Calculations
    3. Top-Down Recursion: A New Way of Thinking
    4. The Staircase Problem
    5. Anagram Generation
    6. Wrapping Up
    7. Exercises
  13. 12. Dynamic Programming
    1. Unnecessary Recursive Calls
    2. The Little Fix for Big O
    3. The Efficiency of Recursion
    4. Overlapping Subproblems
    5. Dynamic Programming through Memoization
    6. Dynamic Programming through Going Bottom-Up
    7. Wrapping Up
    8. Exercises
  14. 13. Recursive Algorithms for Speed
    1. Partitioning
    2. Quicksort
    3. The Efficiency of Quicksort
    4. Quicksort in the Worst-Case Scenario
    5. Quickselect
    6. Sorting as a Key to Other Algorithms
    7. Wrapping Up
    8. Exercises
  15. 14. Node-Based Data Structures
    1. Linked Lists
    2. Implementing a Linked List
    3. Reading
    4. Searching
    5. Insertion
    6. Deletion
    7. Efficiency of Linked List Operations
    8. Linked Lists in Action
    9. Doubly Linked Lists
    10. Queues as Doubly Linked Lists
    11. Wrapping Up
    12. Exercises
  16. 15. Speeding Up All the Things with Binary Search Trees
    1. Trees
    2. Binary Search Trees
    3. Searching
    4. Insertion
    5. Deletion
    6. Binary Search Trees in Action
    7. Binary Search Tree Traversal
    8. Wrapping Up
    9. Exercises
  17. 16. Keeping Your Priorities Straight with Heaps
    1. Priority Queues
    2. Heaps
    3. Heap Properties
    4. Heap Insertion
    5. Looking for the Last Node
    6. Heap Deletion
    7. Heaps vs. Ordered Arrays
    8. The Problem of the Last Node…Again
    9. Arrays as Heaps
    10. Heaps as Priority Queues
    11. Wrapping Up
    12. Exercises
  18. 17. It Doesn’t Hurt to Trie
    1. Tries
    2. Storing Words
    3. Trie Search
    4. The Efficiency of Trie Search
    5. Trie Insertion
    6. Building Autocomplete
    7. Completing Autocomplete
    8. Tries with Values: A Better Autocomplete
    9. Wrapping Up
    10. Exercises
  19. 18. Connecting Everything with Graphs
    1. Graphs
    2. Directed Graphs
    3. Object-Oriented Graph Implementation
    4. Graph Search
    5. Depth-First Search
    6. Breadth-First Search
    7. The Efficiency of Graph Search
    8. Weighted Graphs
    9. Dijkstra’s Algorithm
    10. Wrapping Up
    11. Exercises
  20. 19. Dealing with Space Constraints
    1. Big O of Space Complexity
    2. Trade-Offs Between Time and Space
    3. The Hidden Cost of Recursion
    4. Wrapping Up
    5. Exercises
  21. 20. Techniques for Code Optimization
    1. Prerequisite: Determine Your Current Big O
    2. Start Here: The Best-Imaginable Big O
    3. Magical Lookups
    4. Recognizing Patterns
    5. Greedy Algorithms
    6. Change the Data Structure
    7. Wrapping Up
    8. Parting Thoughts
    9. Exercises
  22. A1. Exercise Solutions
    1. Chapter 1
    2. Chapter 2
    3. Chapter 3
    4. Chapter 4
    5. Chapter 5
    6. Chapter 6
    7. Chapter 7
    8. Chapter 8
    9. Chapter 9
    10. Chapter 10
    11. Chapter 11
    12. Chapter 12
    13. Chapter 13
    14. Chapter 14
    15. Chapter 15
    16. Chapter 16
    17. Chapter 17
    18. Chapter 18
    19. Chapter 19
    20. Chapter 20

Product information

  • Title: A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition
  • Author(s): Jay Wengrow
  • Release date: August 2020
  • Publisher(s): Pragmatic Bookshelf
  • ISBN: 9781680507225