Think Data Structures

Think Data Structures

by Allen B. Downey
Released July 2017
Publisher(s): O'Reilly Media, Inc.
ISBN: 9781491972397

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 Amazon Buy on ebooks.com
Start your free trial

Book description

If you’re a student studying computer science or a software developer preparing for technical interviews, this practical book will help you learn and review some of the most important ideas in software engineering—data structures and algorithms—in a way that’s clearer, more concise, and more engaging than other materials.

By emphasizing practical knowledge and skills over theory, author Allen Downey shows you how to use data structures to implement efficient algorithms, and then analyze and measure their performance. You’ll explore the important classes in the Java collections framework (JCF), how they’re implemented, and how they’re expected to perform. Each chapter presents hands-on exercises supported by test code online.

  • Use data structures such as lists and maps, and understand how they work
  • Build an application that reads Wikipedia pages, parses the contents, and navigates the resulting data tree
  • Analyze code to predict how fast it will run and how much memory it will require
  • Write classes that implement the Map interface, using a hash table and binary search tree
  • Build a simple web search engine with a crawler, an indexer that stores web page contents, and a retriever that returns user query results

Other books by Allen Downey include Think Java, Think Python, Think Stats, and Think Bayes.

Publisher resources

View/Submit Errata

Table of contents

  1. Preface
    1. The Philosophy Behind the Book
    2. Prerequisites
    3. Working with the Code
    4. Conventions Used in This Book
    5. Safari® Books Online
    6. How to Contact Us
    7. Contributors
  2. 1. Interfaces
    1. Why Are There Two Kinds of List?
    2. Interfaces in Java
    3. List Interface
    4. Exercise 1
  3. 2. Analysis of Algorithms
    1. Selection Sort
    2. Big O Notation
    3. Exercise 2
  4. 3. ArrayList
    1. Classifying MyArrayList Methods
    2. Classifying add
    3. Problem Size
    4. Linked Data Structures
    5. Exercise 3
    6. A Note on Garbage Collection
  5. 4. LinkedList
    1. Classifying MyLinkedList Methods
    2. Comparing MyArrayList and MyLinkedList
    3. Profiling
    4. Interpreting Results
    5. Exercise 4
  6. 5. Doubly Linked List
    1. Performance Profiling Results
    2. Profiling LinkedList Methods
    3. Adding to the End of a LinkedList
    4. Doubly Linked List
    5. Choosing a Structure
  7. 6. Tree Traversal
    1. Search Engines
    2. Parsing HTML
    3. Using jsoup
    4. Iterating Through the DOM
    5. Depth-First Search
    6. Stacks in Java
    7. Iterative DFS
  8. 7. Getting to Philosophy
    1. Getting Started
    2. Iterables and Iterators
    3. WikiFetcher
    4. Exercise 5
  9. 8. Indexer
    1. Data Structure Selection
    2. TermCounter
    3. Exercise 6
  10. 9. The Map Interface
    1. Implementing MyLinearMap
    2. Exercise 7
    3. Analyzing MyLinearMap
  11. 10. Hashing
    1. Hashing
    2. How Does Hashing Work?
    3. Hashing and Mutation
    4. Exercise 8
  12. 11. HashMap
    1. Exercise 9
    2. Analyzing MyHashMap
    3. The Tradeoffs
    4. Profiling MyHashMap
    5. Fixing MyHashMap
    6. UML Class Diagrams
  13. 12. TreeMap
    1. What’s Wrong with Hashing?
    2. Binary Search Tree
    3. Exercise 10
    4. Implementing a TreeMap
  14. 13. Binary Search Tree
    1. A Simple MyTreeMap
    2. Searching for Values
    3. Implementing put
    4. In-Order Traversal
    5. The Logarithmic Methods
    6. Self-Balancing Trees
    7. One More Exercise
  15. 14. Persistence
    1. Redis
    2. Redis Clients and Servers
    3. Making a Redis-Backed Index
    4. Redis Data Types
    5. Exercise 11
    6. More Suggestions If You Want Them
    7. A Few Design Hints
  16. 15. Crawling Wikipedia
    1. The Redis-Backed Indexer
    2. Analysis of Lookup
    3. Analysis of Indexing
    4. Graph Traversal
    5. Exercise 12
  17. 16. Boolean Search
    1. Crawler Solution
    2. Information Retrieval
    3. Boolean Search
    4. Exercise 13
    5. Comparable and Comparator
    6. Extensions
  18. 17. Sorting
    1. Insertion Sort
    2. Exercise 14
    3. Analysis of Merge Sort
    4. Radix Sort
    5. Heap Sort
    6. Bounded Heap
    7. Space Complexity
  19. Index

Product information

  • Title: Think Data Structures
  • Author(s): Allen B. Downey
  • Release date: July 2017
  • Publisher(s): O'Reilly Media, Inc.
  • ISBN: 9781491972397