Think Data Structures · Algorithms and Information Retrieval in Java by Downey, Allen B. -- Read -- Imperial Library of Trantor

Index

Preface

The Philosophy Behind the Book Prerequisites Working with the Code Conventions Used in This Book Safari® Books Online How to Contact Us Contributors

1. Interfaces

Why Are There Two Kinds of List? Interfaces in Java List Interface Exercise 1

2. Analysis of Algorithms

Selection Sort Big O Notation Exercise 2

3. ArrayList

Classifying MyArrayList Methods Classifying add Problem Size Linked Data Structures Exercise 3 A Note on Garbage Collection

4. LinkedList

Classifying MyLinkedList Methods Comparing MyArrayList and MyLinkedList Profiling Interpreting Results Exercise 4

5. Doubly Linked List

Performance Profiling Results Profiling LinkedList Methods Adding to the End of a LinkedList Doubly Linked List Choosing a Structure

6. Tree Traversal

Search Engines Parsing HTML Using jsoup Iterating Through the DOM Depth-First Search Stacks in Java Iterative DFS

7. Getting to Philosophy

Getting Started Iterables and Iterators WikiFetcher Exercise 5

8. Indexer

Data Structure Selection TermCounter Exercise 6

9. The Map Interface

Implementing MyLinearMap Exercise 7 Analyzing MyLinearMap

10. Hashing

Hashing How Does Hashing Work? Hashing and Mutation Exercise 8

11. HashMap

Exercise 9 Analyzing MyHashMap The Tradeoffs Profiling MyHashMap Fixing MyHashMap UML Class Diagrams

12. TreeMap

What’s Wrong with Hashing? Binary Search Tree Exercise 10 Implementing a TreeMap

13. Binary Search Tree

A Simple MyTreeMap Searching for Values Implementing put In-Order Traversal The Logarithmic Methods Self-Balancing Trees One More Exercise

14. Persistence

Redis Redis Clients and Servers Making a Redis-Backed Index Redis Data Types Exercise 11 More Suggestions If You Want Them A Few Design Hints

15. Crawling Wikipedia

The Redis-Backed Indexer Analysis of Lookup Analysis of Indexing Graph Traversal Exercise 12

16. Boolean Search

Crawler Solution Information Retrieval Boolean Search Exercise 13 Comparable and Comparator Extensions

17. Sorting

Insertion Sort Exercise 14 Analysis of Merge Sort Radix Sort Heap Sort Bounded Heap Space Complexity

Index