Example Sentinel node

first version using null end-of-list indicator

the for-loop contains 2 tests (yellow lines) per iteration:

node != null;
if (node->key == search_key).

second version using sentinel node

the globally available pointer sentinel deliberately prepared data structure sentinel used end-of-list indicator.

the for-loop contains 1 test (yellow line) per iteration:

node->key != search_key;.

if data structure accessed concurrently sentinel-based implementation, not list pointed first has protected mutex, sentinel node has protected too; mutex in quite few use scenarios can cause severe performance degradation . 1 way avoid have list structure having both node* first, , sentinel node (this way sentinel won t need shared more original list itself).