What are you using the sentinel for? A marker for the end of the list?
A common way to implement a linked list is to use a sentinal as the
head of a circularly linked list.
Thus, an empty list is a pointer to the sentinal which is linked to
itsself.
The advantage is that there are fewer special
Exactly. The other trick is when maintaining a list in ascending
sorted order, to give the sentinel a key of infinite. This way you
need not check for the end of list at all. The key comparison will
always stop before the last element. I vaguely recall Wirth uses this
example in his book
@don,@gene: i know the pros of using it.but pbm occurs when we see
pbm
LIST-SEARCH(l,k)
x - next[nil[l]] //nil[l] denotes the
sentinel node
while x != nil[l] and key[x] != k
x - next[x]
return x
here to eliminate extra comparison (x != nil[l] ) in while loop ,