Two Bugs in LinkedList data structure in Absolute Beginner's Guide to Algorithms

1

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!`);
}
2

@timfrobisher - thanks for pointing this out! You are totally right :facepalm:

I have posted the updated code here: kirupa/data_structures_algorithms/linkedlist.htm at master · kirupa/kirupa · GitHub

I will update the corresponding article and file the corrections tomorrow.

3

Hi,

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:

image
image724×67 5.42 KB

As formatted, this literally states that because the process takes 263 seconds, the process takes 585 billion years.

Let’s do the timewarp again!

1 Like
4

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.

5

Hi,

A couple more issues.

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.

6

Thanks for flagging this! Here is the updated source with the traversal fully working: kirupa/data_structures_algorithms/binary_tree_traversal.htm at master · kirupa/kirupa · GitHub

I’ll make the updates in a few moments to the errata!

7

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.”

8

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

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!