Eliminate NULL check in Searching linked List

How do I eliminate the NULL ch开发者_如何学Goeck in every iteration of the while-loop searching a linked list?

You could use a sentinel element - append the element you search. If you found the sentinel return not found; remove the sentinel in both cases.

Added:

See Sentinel search example; my apology for the language. I remembered the strategy from N. Wirth's "Algorithmen und Datenstrukturen"; my apologies for the languages.

You simply can't.

As long as you are iterating over any data structure, you always want your algorithm to act differently IF it has reached the end of the structure thus requiring any kind of check. That is true whatever your data structure is and does not depend on the "way" you are iterating: for(int i = 0 ; i < sizeArray ; ++i), for(iterator it = myList.begin() ; it != mylist.end(); it++), while(currentNode.hasChildren()), while(javaIterator.hasNext()) ...

Nevertheless, whatever your loop does, checking if an accessible object is NULL will never be the bottleneck of your algorithm. It is even difficult to do less time consuming...

The ONLY way you could possibly avoid the check would be to avoid the loop itself, therefore writing each step underlying in the loop but it requires you to know the size of the linked list at compile time and in that case your compiler may have optimized your code better than you would probably have done yourself ;-)

You can use a circular (looping) linked list where the last element is linked with the first one.

You could keep track of the number of elements in your list. If you always know how many element are in the list and at which position you currently are, then there is no need to check for NULL when you want to advance to the next element.