There will be multiple (closely) related questions instead of a single one. For our comfort, I will number them accordingly.
Based on this Wikipedia article, this question and lectures, I think I already understand the idea behind sentinel nodes and their usage in linked lists. However, a few things are still not clear to me even after reading these materials.
I was given a basic implementation of a doubly linked list (it stores only int values) and the task is to change the implementation so it uses a sentinel node like this:
Illustrative image (not allowed to embed images yet, sorry)
I am assuming that the head variable of the list will point to the first real node (the one after sentinel node) and the tail variable will simply point to the last node. Am I correct or should the head point to the sentinel node? I am asking for a best-practice or the most standard approach here.
I understand that when searching for a value in the list, I no longer have to check for nullptr since I am using a sentinel node. Since the list basically formed a circle thanks to the sentinel node, I have to terminate it after iterating through the whole list and reaching it. Can I do it by putting the value I am looking for in the sentinel node and use it as a sentinel value of sorts and then check if the result is returned from the sentinel node when the loop ends? Some sources claim that sentinel nodes should not store any values at all. Is my approach correct/reasonably effective?
When simply iterating and not searching for a particular value (e.g. counting nodes, outputting the whole list into the console), do I have to check for the sentinel node the same way as I would for a nullptr (to terminate the iterating loop) or is there a different or smarter way of doing this?
Yes this is a valid position for the sentinelnode to take. head and tail can point to the actual beginning and end of the data. But your add and delete functions will need to be aware of the aberrations caused at the list boundaries by virtue of the sentinel node
Yes this is a valid search strategy and is infact called the Elephant in Cairo technique
Yes, the purpose of the sentinel node is to let you know that it is the sentinel node. You could just maintain a constant pointer (or whatever your lang of choice supports) to this sentinel node to check if you are at the sentinel node or just stick a flag in the node.
