Errata for Data Structures & Algorithms in Dart 1st Edition

[jellodiil]

Creating this topic to catch any typos and bugs in the 1st Edition of Data Structures & Algorithms in Dart.

[osmanbah]

Hello, I think the logarithmic time complexity in chapter has a bug,
only the first operation is O(log n) the rest on O(n).
here the code from the book:

bool betterNaiveContains(int value, List<int> list) {
  if (list.isEmpty) return false;
  final middleIndex = list.length ~/ 2;

  if (value > list[middleIndex]) {
    for (var i = middleIndex; i < list.length; i++) {
      if (list[i] == value) return true;
    }
  } else {
    for (var i = middleIndex; i >= 0; i--) {
      if (list[i] == value) return true;
    }
  }

  return false;
}

This is my test case:

void main() {
  var numbers = <int>[];
  var i = 1;
  while (i < 101) {
    numbers.add(i);
    i++;
  }
  print(betterNaiveContains(100, numbers));
}

It first set the middleIndex variable to 50 which is O(log n) and in the loop just increment the middleIndex by 1 e.g 51, 52, 53… 100 which O(n) .I was expecting the middleIndex variable get divide by two each time we loop through which we get something like this 50 75, 88 ,94 97 99 and then we get 100 which will result to O(log n) I think. Anyway I new to this topic so hoping someone will help me with my expectation can’t still figure it out!

[suragch]

Good job on thinking algorithmically! You’re right that only the first check cuts the list in half and after that the algorithm is O(n). This results in the entire function being O(n). The O(log n) version of this algorithm isn’t presented until Chapter 12.

The original idea with this example was to gently ease readers into the notion of logarithmic time by showing how you can cut your work in half. However, now that I read your comment, I can see how this is confusing. I’ve created an internal GitHub issue to reevaluate this section when we publish version 2.0. For now just refer to Chapter 12.

Thanks a lot for leaving a comment. That helps to improve the book for everyone. Please leave more comments as you work through the book.

[urbanmarton]

Hi, in “Chapter 5 Solutions”, for the “Solution to Challenge 4”, the while loop looks like this:

while (head != null && head!.value == value) {
  head = head!.next;
}

Am I correct to assume that the separate null check is a bit redundant here as this shorter version does exactly the same:

while (head?.value == value) {
  head = head!.next;
}

That way the evaluation will still be false if head is null.

[suragch]

Good point! That refactoring is much simpler. Thank you. I’ve opened an issue to make this change in the next book update.

[suragch]

Actually it turns out there is an edge case that will cause a crash if you don’t do the additional null check:

var list = LinkedList<int?>();
list.removeAll(null);

If you use this code in removeAll:

while (head?.value == value) {
  head = head!.next;
}

Then the while loop will begin but head will be null since the list is empty and head!.next will crash.

[urbanmarton]

Oh, you are right, head?.value evaluates to null on an empty list, hence the while loop will begin (null == null). Great find, and I truly appreciate authors like you, who are so commited to their work. Will definitely recommend your book! Thank you!