Errata

Errata for Think Data Structures

Submit your own errata for this product.

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
	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. Should be “MyLinkedList”	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