Think Data Structures

“Think Data Structures” delves into the fundamental concepts and practical applications of organizing and manipulating data efficiently. The content explores various data structures like arrays, linked lists, trees, and graphs, highlighting their strengths and use cases. Additionally, the document discusses algorithms for searching, sorting, and optimizing data structures for improved performance. By drawing insights from real-world examples and problem-solving scenarios, “Think Data Structures” aims to equip readers with a solid understanding of how to leverage different data structures to solve complex computational problems effectively.

Visit Think Data Structures

Chapter 13 Binary search tree

This chapter presents solutions to the previous exercise, then tests the performance of the tree-backed map. I present a problem with the implementation and explain how Java’s TreeMap solves it. 13.1 ...

Chapter 12 TreeMap

Think Data Structures

This chapter presents the binary search tree, which is an efficient implementation of the Map interface that is particularly useful if we want to keep the elements sorted. 12.1 What’s wrong with hashi...

Chapter 16 Boolean search

Think Data Structures

In this chapter I present a solution to the previous exercise. Then you will write code to combine multiple search results and sort them by their relevance to the search terms. 16.1 Crawler solution F...

Chapter 17 Sorting

Think Data Structures

Computer science departments have an unhealthy obsession with sort algorithms. Based on the amount of time CS students spend on the topic, you would think that choosing sort algorithms is the cornerst...

Index

Think Data Structures

Ant, 0.1 , 1.4 , 2.3 , 7.1 , 8.3 , 8.3 , 9.2 , 10.4 , 11.1 , 11.4 , 12.4 , 14.3 , 15.5 , 16.4 , 17.2 API, 0.1 Apache Ant, 0.1 ArrayDeque, 6.7 ArrayList, 1 , 1.1 , 1.3 , 3 , 4.4 , 9.1 , 10.1 AVL tree, ...

Chapter 6 Tree traversal

Think Data Structures

This chapter introduces the application we will develop during the rest of the book, a web search engine. I describe the elements of a search engine and introduce the first application, a Web crawler ...

Chapter 8 Indexer

Think Data Structures

At this point we have built a basic Web crawler; the next piece we will work on is the index . In the context of web search, an index is a data structure that makes it possible to look up a search ter...

Chapter 7 Getting to Philosophy

Think Data Structures

The goal of this chapter is to develop a Web crawler that tests the “Getting to Philosophy” conjecture, which we presented in Section 6.1 . 7.1 Getting started In the repository for this book, you’ll ...

Chapter 9 The Map interface

Think Data Structures

In the next few exercises, I present several implementations of the Map interface. One of them is based on a hash table , which is arguably the most magical data structure ever invented. Another, whic...

Chapter 14 Persistence

Think Data Structures

In the next few exercises we will get back to building a web search engine. To review, the components of a search engine are: Crawling: We’ll need a program that can download a web page, parse it, and...

Chapter 15 Crawling Wikipedia

Think Data Structures

In this chapter, I present a solution to the previous exercise and analyze the performance of Web indexing algorithms. Then we build a simple Web crawler. 15.1 The Redis-backed indexer In my solution,...

Chapter 10 Hashing

Think Data Structures

In this chapter, I define MyBetterMap , a better implementation of the Map interface than MyLinearMap , and introduce hashing , which makes MyBetterMap more efficient. 10.1 Hashing To improve the perf...