Sentinel Node in a C Linked List

Question

I'm trying to learn more about linked lists in C and I recently stumbled upon the Sentinel Node concept, but I can't wrap my head around it. According to the slides I have, the sentinel node should be the first thing on the list when it's created and the last when other nodes are added. There should be a pointer to permanently point to the Sentinel Node. All those stuff confuse me and I would love some help with the implementation.

/*this is a simple LL implementation*/
#include <stdio.h>
#include <stdlib.h>

struct List
{
    int data;
    struct List *next;
};

void ListInsert(int new_data)
{
    struct List *p;
    p = (struct List *)malloc(sizeof(struct List));
    p->data = new_data;
    p->next = (head);
    head = p;
}

void printList(struct List *q)
{
    q = head;
    while (q != NULL)
    {
        printf("%d ", q->data);
        q = q->next;
    }
    printf("\n");
}

int main()
{
    ListInsert(5);
    ListInsert(7);
    ListInsert(6);
    ListInsert(4);
    ListInsert(2);
    printList(head);
    return 0;
}

Now, if I want to create the sentinel node, how should I proceed?

`head` is used without being declared. Also it looks weird to overwrite the value of arguments to something unconditionally without reading the value in `printList`. — MikeCAT, Aug 06 '21 at 13:33
Also casting results of `malloc()` family is [considered as a bad practice](https://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc). — MikeCAT, Aug 06 '21 at 13:34
You dont need a sentinel node. Either it is the last node on the list, or a sentinel pointer to its ->next pointer. In both cases it can be derived from the actual list. — wildplasser, Aug 06 '21 at 13:59
You can use the pointer value `NULL` to represent the sentinel node "virtually". It cannot be dereferenced, but it serves the purpose of being distinguishable from pointers to non-sentinel nodes. — Ian Abbott, Aug 06 '21 at 14:25
True, @IanAbbott. I am inclined to think, however, that the primary advantage of using an actual sentinel node is that you *can* dereference it. That's especially relevant for doubly-linked lists, but I imagine that it provides a minor convenience for implementing list operations even for singly-linked lists. — John Bollinger, Aug 06 '21 at 14:34

score 3 · Accepted Answer · answered Aug 06 '21 at 13:52

According to the slides i have, the sentinel node should be the first thing on the list when its created and the last when other nodes are added.There should be a pointer to permanently point to the Sentinel Node.

Let's start with the most important point: the purpose of a sentinel node, which is to mark the end of the list. There will not be real data associated with a sentinel node, so a list containing only a sentinel node is logically empty.

A few things follow from that, including:

the identity of the sentinel node is a property of the whole list, not of any (other) particular node
list manipulation algorithms need to be written differently for linked lists whose ends are marked by a sentinel than for those whose ends are marked by some other means.
each list need a place to store the sentinel's identity
a list that is expected to have a sentinel is invalid if it does not have one

There are many ways to implement the details, all with their own advantages and disadvantages.

Personally, I would be inclined (in the non-sentinel case, too) to have a structure to represent an overall list, separate from the structure used to represent a list node. A pointer to the list's head node would be a member of this structure, and in the sentinel-terminated-list case, so would be a pointer to the sentinel node. When you create a new list, you create a sentinel node for it, too; initially, the list's head and sentinel pointers will both point to that node. The head pointer may be changed, but the sentinel pointer must not be. When you append to the list, the appended node gets placed just before the sentinel. It is an error to try to delete the sentinel from the list.

It is to your advantage to write the code for this yourself.

In your answer, you wrote: `"Personally, I would be inclined (in the non-sentinel case, too) to have a structure to represent an overall list, separate from the structure used to represent a list node"` -- In the case of a singly-linked list when not using a sentinel node, I don't consider it meaningful to represent the linked list as a whole in a `struct`, as that `struct` would consist of only a single member: The head. However, I do consider it meaningful to do this when using a doubly-linked list or when using a sentinel node, as the `struct` would contain more than one member. — Andreas Wenzel, Aug 06 '21 at 14:21
Suit yourself, @AndreasWenzel, but I have no qualms about a list structure with no members other than a link to the head node. Semantically, the difference is between there always being an object representing the list on one hand, and empty lists being represented by the absence of any object on the other. There are practical consequences, too, such as whether different empty lists can be distinguished from each other. — John Bollinger, Aug 06 '21 at 14:24

score 2 · Answer 2 · edited Aug 06 '21 at 13:49

2

Create it. You said "There should be a pointer to permanently point to the Sentinel Node", so create the pointer. Then use the pointer as the terminator of the list instead of NULL.

Sentinel node - Wikipedia

/*this is a simple LL implementation*/
#include <stdio.h>
#include <stdlib.h>

struct List
{
    int data;
    struct List *next;
};

struct List sentinel_node_instance;
/* a pointer to permanently point to the Sentinel Node */
struct List* const SENTINEL_NODE = &sentinel_node_instance;

/* the sentinel node should be the first thing on the list when it's created */
struct List* head = SENTINEL_NODE;

void ListInsert(int new_data)
{
    struct List *p;
    p = (struct List *)malloc(sizeof(struct List));
    p->data = new_data;
    p->next = (head);
    head = p;
}

void printList(void)
{
    struct List* q = head;
    while (q != SENTINEL_NODE)
    {
        printf("%d ", q->data);
        q = q->next;
    }
    printf("\n");
}

int main()
{
    ListInsert(5);
    ListInsert(7);
    ListInsert(6);
    ListInsert(4);
    ListInsert(2);
    printList();
    return 0;
}

edited Aug 06 '21 at 13:49

Jonathan Leffler

730,956
141
904
1,278

answered Aug 06 '21 at 13:42

MikeCAT

73,922
11
45
70

Thank you very much for your help! Your implementation allowed me to tinker a bit more and try to look up some more stuff. – user3745168 Aug 06 '21 at 14:43
I run out of time sr. I still have some questions though, from what i gathered "struct List sentinel_node_instance" creates a new node with the name "sentinel_node_instance" right? I tried to give said new struct a data integer so now i can check if the number im searching is inside the linked list proper or inside the sentinel node. The next question is why typedef doesnt play well with "struct List sentinel_node_instance" and the third one is that head= SENTINEL_NODE gives an "expression must have a constant value" warning. – user3745168 Aug 06 '21 at 14:53
@user3745168 1. Yes, `struct List sentinel_node_instance;` create a node with the name `sentinel_node_instance`. 2. It seems you are not using `typedef` properly. The code here doesn't contain any `typedef`. 3. [I didn't get the warning](https://wandbox.org/permlink/3X44kekLvWLlBhsf). What is your compiler? – MikeCAT Aug 10 '21 at 11:37

score 0 · Answer 3 · answered Aug 06 '21 at 15:04

Another variation of a sentinel node is for a circular doubly linked list, where it is both a head node and a sentinel node. Visual Studio implements std::list in this manner.

head.next  = pointer to first node or to head if empty list
head.prev  = pointer to last  node or to head if empty list
first.prev = pointer to head node
last.next  = pointer to head node

Sentinel Node in a C Linked List

3 Answers3