I found two bugs in the LinkedList data structure in Absolute Beginner’s Guide to Algorithms. Both involve not updating the tail pointer.

Fixed Code:

removeData(data) {
if (this.size === 0) {
throw new Error("List is empty");
}
if (this.head.data === data) {
this.head = this.head.next;
this.size--;
return;
}
let current = this.head;
while (current.next) {
if (current.next.data === data) {
if(current.next === this.tail) {
this.tail = current;
}
current.next = current.next.next;
this.size--;
return;
}
current = current.next;
}
throw new Error(`Node with data '${data}' not found in list!`);
}
addAfter(afterData, data) {
const newNode = new LinkedListNode(data);
if (this.size === 0) {
this.head = newNode;
this.size++;
return;
}
let current = this.head;
while (current) {
if (current.data === afterData) {
newNode.next = current.next;
if(current === this.tail) {
this.tail = newNode;
}
current.next = newNode;
this.size++;
return;
}
current = current.next;
}
throw new Error(`Node with data '${afterData}' not found in list!`);
}

I found another issue with the book but don’t feel like it warrants a separate post. The issue is with the Towers of Hanoi explanation. There is a rather confusing formatting problem. I am using the Kindle version on the PC Kindle reader. The issue may be specific to this version.

(Imagine that I inserted an image of the induction proof here. I did. But I had to delete it since new users can only insert one embedded media item per post)

In any case, the proof states that the number of turns required to move the discs is 2n-1 instead of 2^n - 1 then concludes with the following blurb:

That is indeed a formatting error. It should be 2^64 - 1, but I think superscripts are getting ignored in the Kindle edition. Let me flag this with the right team to see if they can quickly fix this.

The main one is a bad variable in the breadthFirstTraversal function:

observed.enqueue(root);

But observed doesn’t exist. It should be

discovered.enqueue(root);

The other issue is with the call to Stack.length in the depthFirstTraversal function:

while (discovered.length > 0) {

This works fine using the code provided online. However, there is no get length() function in the Stack implementation from the book. So, this will fail if using the book implementation of the Stack.

Ok. I’m done with the book, so this is my last comment. (Really). And it is pretty minor.

In the selection sort chapter, when you were very clearly discussing selection sort, you accidentally wrote, “From a memory point of view, insertion sort is very good.”

Gah! I will flag that for fixing in the next printings

Thank you so much for your feedback! I’d like to send you an autographed copy of the book with possibly a little doodle as well. If you are OK with that, please DM me your address and I’ll ship it over to you quickly!