Introduction to Algorithm, Exercise 10.2-4

Question

This is a question from exercise of Introduction to Algorithms, 3rd edtion: (I know this is trivial question, but I can't get my head around this.)

Chapter 10, page 240:

10.2-4

As written, each loop iteration in the LIST-SEARCH procedure requires two tests: one for x != L.nil and one for x.key != k. Show how to eliminate the test for x != L.nil in each iteration.

LIST-SEARCH(L, k)
  x = L.nil.next
  while x != L.nil and x.key != k
    x = x.next
  return x

L is circular, doubly linked list with a sentinel. (A sentinel is a fixed static element in the starting, that helps to simplify boundary conditions. For example, suppose that we provide with list L an object L.nil that represents NIL but has all the attributes of other objects in the list.)

Unless, k you search for is always present, simple removing x != L.nil would cause infinite iteration.

You can transform, this expression x != L.nil to other expressions (such as count of elements in the list), but that isn't a solution, I guess.

What am I lacking in solving this question?

Answer 1

The trick is to set your sentinel's key to value k before entering the loop. That way, you can eliminate the nil check and still be sure the loop terminates. When k is found, the node found is either the sentinel, or the value you wanted to find.

Answer 2

Do something like this:

LIST-SEARCH(L,k)
    nil.key = k;
    currentPtr = nil.next;
         while(currentPtr.key != k) 
    currentPtr = currentPtr.next;
    nil.data = -1; // dummy key
    return currentPtr;