Think Data Structures & Algorithms in Java – eBook PDF Download | Data Structure Class Notes & Course material
Topics covered by Data Structures & Algorithms in Java | Contents
The topics covered by this eBook:
1.1 Why are there two kinds of List? . . . . . . . . . . . . . . . 2
1.2 Interfaces in Java . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 The List interface . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1 Selection sort . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Big O notation . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Exercise 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3 ArrayList 19
3.1 Classifying MyArrayList methods . . . . . . . . . . . . . . . 19
3.4 Linked Data Structures . . . . . . . . . . . . . . . . . . . . . 24
3.6 A note on garbage collection . . . . . . . . . . . . . . . . . . 30
4 LinkedList 31
4.2 Comparing MyArrayList and MyLinkedList . . . . . . . . . 34
5 Doubly-linked list 41
5.1 Performance profiling results . . . . . . . . . . . . . . . . . . 41
5.2 Profiling LinkedList methods . . . . . . . . . . . . . . . . . 43
5.3 Adding to the end of a LinkedList . . . . . . . . . . . . . . 44
5.4 Doubly-linked list . . . . . . . . . . . . . . . . . . . . . . . . 47
5.5 Choosing a Structure . . . . . . . . . . . . . . . . . . . . . . 48
6 Tree traversal 51
6.1 Search engines . . . . . . . . . . . . . . . . . . . . . . . . . . 51
6.2 Parsing HTML . . . . . . . . . . . . . . . . . . . . . . . . . 52
6.3 Using jsoup . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
6.4 Iterating through the DOM . . . . . . . . . . . . . . . . . . 56
6.5 Depth-first search . . . . . . . . . . . . . . . . . . . . . . . . 57
6.6 Stacks in Java . . . . . . . . . . . . . . . . . . . . . . . . . . 58
6.7 Iterative DFS . . . . . . . . . . . . . . . . . . . . . . . . . . 59
7.1 Getting started . . . . . . . . . . . . . . . . . . . . . . . . . 61
7.2 Iterables and Iterators . . . . . . . . . . . . . . . . . . . . . 62
7.3 WikiFetcher . . . . . . . . . . . . . . . . . . . . . . . . . . 64
8 Indexer 69
8.1 Data structure selection . . . . . . . . . . . . . . . . . . . . 69
8.2 TermCounter . . . . . . . . . . . . . . . . . . . . . . . . . . 71
8.3 Exercise 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
9 The Map interface 79
9.1 Implementing MyLinearMap . . . . . . . . . . . . . . . . . . 79
9.2 Exercise 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
9.3 Analyzing MyLinearMap . . . . . . . . . . . . . . . . . . . . 81
10 Hashing 85
10.1 Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
10.2 How does hashing work? . . . . . . . . . . . . . . . . . . . . 87
10.3 Hashing and mutation . . . . . . . . . . . . . . . . . . . . . 89
10.4 Exercise 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
11 HashMap 93
11.1 Exercise 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
11.2 Analyzing MyHashMap . . . . . . . . . . . . . . . . . . . . . . 95
11.3 The tradeoffs . . . . . . . . . . . . . . . . . . . . . . . . . . 96
11.4 Profiling MyHashMap . . . . . . . . . . . . . . . . . . . . . . . 97
11.5 Fixing MyHashMap . . . . . . . . . . . . . . . . . . . . . . . . 98
11.6 UML class diagrams . . . . . . . . . . . . . . . . . . . . . . 100
12 TreeMap 103
12.1 What’s wrong with hashing? . . . . . . . . . . . . . . . . . . 103
12.2 Binary search tree . . . . . . . . . . . . . . . . . . . . . . . . 104
12.3 Exercise 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
12.4 Implementing a TreeMap . . . . . . . . . . . . . . . . . . . . 108
13 Binary search tree 111
13.1 A simple MyTreeMap . . . . . . . . . . . . . . . . . . . . . . 111
13.2 Searching for values . . . . . . . . . . . . . . . . . . . . . . . 112
13.3 Implementing put . . . . . . . . . . . . . . . . . . . . . . . . 114
13.4 In-order traversal . . . . . . . . . . . . . . . . . . . . . . . . 116
13.5 The logarithmic methods . . . . . . . . . . . . . . . . . . . . 117
13.6 Self-balancing trees . . . . . . . . . . . . . . . . . . . . . . . 119
13.7 One more exercise . . . . . . . . . . . . . . . . . . . . . . . . 120
14 Persistence 121
14.1 Redis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
14.2 Redis clients and servers . . . . . . . . . . . . . . . . . . . . 123
14.3 Making a Redis-backed index . . . . . . . . . . . . . . . . . 124
14.4 Redis data types . . . . . . . . . . . . . . . . . . . . . . . . 126
14.5 Exercise 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
14.6 More suggestions if you want them . . . . . . . . . . . . . . 130
14.7 A few design hints . . . . . . . . . . . . . . . . . . . . . . . . 131
15 Crawling Wikipedia 133
15.1 The Redis-backed indexer . . . . . . . . . . . . . . . . . . . 133
15.2 Analysis of lookup . . . . . . . . . . . . . . . . . . . . . . . . 136
15.3 Analysis of indexing . . . . . . . . . . . . . . . . . . . . . . . 137
15.4 Graph traversal . . . . . . . . . . . . . . . . . . . . . . . . . 138
15.5 Exercise 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
16 Boolean search 143
16.1 Crawler solution . . . . . . . . . . . . . . . . . . . . . . . . . 143
16.2 Information retrieval . . . . . . . . . . . . . . . . . . . . . . 146
16.3 Boolean search . . . . . . . . . . . . . . . . . . . . . . . . . 146
16.4 Exercise 13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
16.5 Comparable and Comparator . . . . . . . . . . . . . . . . . . 150
16.6 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
17 Sorting 155
17.1 Insertion sort . . . . . . . . . . . . . . . . . . . . . . . . . . 156
17.2 Exercise 14 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
17.3 Analysis of merge sort . . . . . . . . . . . . . . . . . . . . . 159
17.4 Radix sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
17.5 Heap sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
17.6 Bounded heap . . . . . . . . . . . . . . . . . . . . . . . . . . 165
17.7 Space complexity . . . . . . . . . . . . . . . . . . . . . . . . 166
Data Structures & Algorithms in Java | PDF Book
The person behind this site is an NIT (National Institute of Technology) Grad with 20+ years of industry experience. The team has nicknamed him Mr. ClassNotes. With a group of blogs and websites, Mr. ClassNotes shares his knowledge and experience with global readers.