Usually, in our push functions for Singly Linked Lists, we must check if we are looking at the tail node, and whether it had been assigned with a value, correct? Because if it's the tail node which hadn't been assigned a value yet, we shouldn't be creating a new node; we must simply assign its storage variable with a value. In rest of the cases - we have to create one before assigning.

But what is the proper way to check if the tail (has a garbage value/zero/not utilized/remains untouched by the user)? Or is there another approach to ALL this (including treating unused tail as a special case scenario when pushing into SLL), that everyone else is using?

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

struct ListNode
{
    int val;
    struct ListNode *next;
};

void linked_init(struct ListNode **p)
{
    (*(p)) = malloc(sizeof(struct ListNode));
    (*(p))->next = NULL;
    //Basically saying that for every linked list that I'll create and initialize, using the "ListNode" struct definition, I will assign to...
    //...its Tail Node, a "Unique Code (int value)", which will indicate that no SENSICAL value had been assigned to the tail, yet.
    (*(p))->val = 98989;
}

void linked_push(struct ListNode **p, int curval)
{
    //If it's the tail, and within the tail, the storage hasn't been used - aka - a usable int value hasn't been assigned.
    if ((*(p))->next == NULL && (*(p))->val == 98989)
    {
        //Push it into the already existing Tail Node
        (*(p))->val = curval;
    }
    else
    {
        //It's either not a tail, or it is indeed a tail which has already been assigned a value.
        //Therefore, we must create a new node before assigning into its tail node, a value.
        struct ListNode *temp;
        temp = malloc(sizeof(struct ListNode));
        temp->val = curval;
        temp->next = (*(p));
        (*(p)) = temp;
    }
}

void linked_display(struct ListNode *p)
{
    struct ListNode *temp;
    temp = p;
    while (temp)
    {
        printf("%d", (temp)->val);
        printf("\n");
        temp = temp->next;
    }
}

int main(int argc, char **argv)
{
    struct ListNode *list;
    linked_init(&list);

    // Initial push would be targeted at the tail, since we were the ones who initialized it; using the linked_init() function.
    // This whole thing only works if the linked list belonged to us; if we initialized it.
    // If we are applying these functions on a list imported from external sources - ex. from questions on online coding platforms, etc - then this wouldn't work.
    linked_push(&list, 14);
    linked_push(&list, 17);
    linked_push(&list, 20);
    linked_push(&list, 90);

    linked_display(list);

    return 0;
}

This is how I'm doing it currently, but I don't think it is a practical approach. I couldn't find anything online regarding this issue.

CodePudding user response：

There is no need to allocate a node with a magic value as the tail node. An empty list is just a null pointer. Using sentinel values is confusing and error prone: tutorials that advocate such methods should be disregarded.

Here is a simplified version:

#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

void linked_init(struct ListNode **p) {
    *p = NULL;
}

void linked_push(struct ListNode **p, int curval) {
    // allocate a new node and insert it at the head of the list
    struct ListNode *temp = malloc(sizeof(*temp));
    if (temp) {
        temp->val = curval;
        temp->next = *p;
        *p = temp;
    }
}

int linked_pop(struct ListNode **p) {
    struct ListNode *temp = *p;
    int val = 0;
    if (temp) {
        val = temp->val;
        *p = temp->next;
        free(temp);
    }
    return val;
}

void linked_display(const struct ListNode *p) {
    const struct ListNode *temp;
    for (temp = p; temp; temp = temp->next) {
        printf("%d ", temp->val);
    }
    printf("\n");
}

int main(int argc, char **argv) {
    struct ListNode *list;

    // Initialize the list. Could just write: struct ListNode *list = NULL;
    linked_init(&list);

    // Insert values
    linked_push(&list, 14);
    linked_push(&list, 17);
    linked_push(&list, 20);
    linked_push(&list, 90);

    // Print the list values: 90 20 17 14
    linked_display(list);

    // Free the list.
    while (list) {
        linked_pop(&list);
    }

    return 0;
}