What is the advantage of using a sentinel?

Answer 1

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.