# Errata

## Errata for Think Data Structures

The errata list is a list of errors and their corrections that were found after the product was released. If the error was corrected in a later version or reprint the date of the correction will be displayed in the column titled "Date Corrected".

The following errata were submitted by our customers and approved as valid errors by the author or editor.

Color key: Serious technical mistake Minor technical mistake Language or formatting error Typo Question Note Update

Version Location Description Submitted By Date submitted Date corrected
Chapter 3
paragraph 4 and 5 starting from section: Exercise 3

Exercise 3 refers to MyLinkedList.java and the instructions say: "Run ant MyArrayList to run MyArrayList.java, which contains a few simple tests." The mistake is to reference to the class MyArrayList instead of MyLinkedList class.

Anonymous  Sep 15, 2017
PDF
Page 38

My implementation of a linked list, MyLinkedList, uses a singly linked
list; that is, each element contains a link to the next, and the
MyArrayList object
itself has a link to the first node.

O'Reilly Media

Feb 06, 2018
PDF, ePub, Mobi
Page 66

There’s not much to it; an Entry is just a container for a key and a value.
This definition is nested inside MyLinearList, so it uses the same type
parameters, K and V.

Should be "MyLinearMap"

O'Reilly Media

Feb 06, 2018
PDF, ePub, Mobi
Page 87

In this example, it takes nine comparisons to find the target, even though
the tree contains nine keys. In general, the number of comparisons is
proportional to the height of the tree, not the number of keys in the tree.

Should be 4

O'Reilly Media

Feb 06, 2018
PDF
Page 137-138

Using a heap with the smallest element at the top, we can keep track of the
largest k elements. Let’s analyze the performance of this algorithm. For each
element, we perform one of:

• Branch 1: Adding an element to the heap is O(log k).

• Branch 2: Finding the smallest element in the heap is O(1).

• Branch 3: Removing the smallest element is O(log k). Adding x is also
O(log k).

Should be rewritten as:

Let’s analyze the performance of this algorithm. For each element, we
perform one, two, or all of these operations:

• Finding the smallest element in the heap, which is O(1).

• Removing the smallest element, which is O(log k).

• Adding an element to the heap, which is O(log k).

O'Reilly Media

Feb 06, 2018