What is the advantage of using a sentinel?
Primarily it allows implementation to be shifted from the list
to the nodes themselves. Generally this is more efficient because
the list's sole responsibility is the sentinel (which is guaranteed
to exist so long as the list is in scope) to which it delegates all
responsibility with regards the actual nodes. A tail sentinel
improves efficiency further by ensuring the head sentinel node
never points to NULL.
Head and tail sentinels are most useful in sorted lists. When
data is added to the list, the list immediately passes the data to
the head node. When the head node receives data it immediately
passes it to the next node, and sets its next node to the return
value. The data passes from one node to the next until it reaches a
node that contains larger data, or it reaches the tail sentinel.
Either way, a new node is created such that it points to the
current node, and returns the new node to the calling node which
updates its next node to point to the new node. All previous nodes
remain unchanged by returning themselves to the calling nodes, all
the way back to the head.
This is more efficient than using a non-sentinel list. With this
implementation, the list itself must traverse the nodes (if any) to
locate the insertion point and then update the links between the
nodes. This is because if there are no nodes, the list must handle
the insertion itself. Therefore it must handle all insertions,
nodes or not. in other words, sentinel nodes shift the
responsibility for insertion to the nodes themselves. Since
traversal is required anyway, it makes sense to reduce the level of
indirection and let the nodes sort themselves out, rather than
forcing them into order by a class that has no inherent knowledge
of the data it is trying to insert. Data sorting is the
responsibility of the nodes that contain it, not the list
itself.