Think Data Structures: Algorithms and Information Retrieval in Java

by Allen Downey

Overview

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.

Product Details

ISBN-13:	9781491972397
Publisher:	O'Reilly Media, Incorporated
Publication date:	08/04/2017
Pages:	155
Product dimensions:	6.90(w) x 9.10(h) x 0.50(d)

About the Author

Allen B. Downey is a Professor of Computer Science at Olin College of Engineering. He has taught at Wellesley College, Colby College, and U.C. Berkeley. He has a Ph.D. in Computer Science from U.C. Berkeley and Master’s and Bachelor’s degrees from MIT.

Table of Contents

Preface vii

1 Interfaces 1

Why Are There Two Kinds of List? 2

Interfaces in Java 2

List Interface 3

Exercise 1 4

2 Analysis of Algorithms 7

Selection Sort 8

Big O Notation 10

Exercise 2 11

3 Arraylist 15

Classifying MyArrayList Methods 15

Classifying add 17

Problem Size 19

Linked Data Structures 19

Exercise 3 21

A Note on Garbage Collection 23

4 LinkedList 25

Classifying MyLinkedList Methods 25

Comparing MyArrayList and MyLinkedList 27

Profiling 28

Interpreting Results 30

Exercise 4 32

5 Doubly Linked List 33

Performance Profiling Results 33

Profiling LinkedList Methods 35

Adding to the End of a LinkedList 36

Doubly Linked List 38

Choosing a Structure 39

6 Tree Traversal 41

Search Engines 41

Parsing HTML 42

Using jsoup 44

Iterating Through the DOM 46

Depth-First Search 46

Stacks in Java 47

Iterative DFS 48

7 Getting to Philosophy 51

Getting Started 51

Iterables and Iterators 52

WikiFetcher 54

Exercise 5 55

8 Indexer 57

Data Structure Selection 57

TermCounter 59

Exercise 6 61

9 The Map Interface 65

Implementing MyLinearMap 65

Exercise 7 66

Analyzing MyLinearMap 67

10 Hashing 71

Hashing 71

How Does Hashing Work? 73

Hashing and Mutation 74

Exercise 8 76

11 HashMap 77

Exercise 9 77

Analyzing MyHashMap 78

The Tradeoffs 80

Profiling MyHashMap 81

Fixing MyHashMap 81

UML Class Diagrams 83

12 TreeMap 85

What's Wrong with Hashing? 85

Binary Search Tree 86

Exercise 10 88

Implementing a TreeMap 89

13 Binary Search Tree 93

A Simple MyTreeMap 93

Searching for Values 94

Implementing put 95

In-Order Traversal 97

The Logarithmic Methods 98

Self-Balancing Trees 100

One More Exercise 100

14 Persistence 101

Redis 102

Redis Clients and Servers 103

Making a Redis-Backed Index 103

Redis Data Types 105

Exercise 11 107

More Suggestions If You Want Them 108

A Few Design Hints 109

15 Crawling Wikipedia 111

The Redis-Backed Indexer 111

Analysis of Lookup 113

Analysis of Indexing 114

Graph Traversal 115

Exercise 12 116

16 Boolean Search 119

Crawler Solution 119

Information Retrieval 121

Boolean Search 122

Exercise 13 122

Comparable and Comparator 124

Extensions 127

17 Sorting 129

Insertion Sort 130

Exercise 14 131

Analysis of Merge Sort 133

Radix Sort 134

Heap Sort 136

Bounded Heap 137

Space Complexity 138

Index 139