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