c - Issue with detecting NULL in head node pointer of Queue Data Structure in isEmpty()

Question

I wrote a Queue Data Structure and test code for it. All the tests are PASSED until the program get to the last test. The IF STATEMENT to check if the queue was empty supposed to return FALSE because enqueue was called and a data was inserted into the queue.

The test FAILED when I am testing using link->head == NULL. However, if I were comparing using the count variable, the test is PASSED. Which means the queue was successfully enqueued and the count is '1' NOT '0' when it was being printed out.

My question is, why does the test FAILED when I test it using pointer and PASSED when I test it using count. Is there any reason for these? As I am expecting them to behaves the same way.

Test Code

#include <stdio.h>
#include "queue.h"
#include "header.h"
#define RED "33[0;31m"
#define GREEN "33[0;32m"
#define RESET "33[0m"

int main()
{
    int n1 = 10, n2 = 20;
    int *retData = NULL;
    LinkedList *queue = createQueue();

    /* First Test when nothing was enqueued */
    printf("TEST Empty: ");
    if ( isQueueEmpty( queue ) == TRUE )
        printf("%sPASSED%s

", GREEN, RESET);
    else
        printf("%sFAILED%s

", RED, RESET); 

    /* Second Test when enqueue was called */
    enqueue( queue, &n1, 'i' );
    printf("TEST Empty (Enqueue): ");
    if ( isQueueEmpty( queue ) == FALSE )
        printf("%sPASSED%s

", GREEN, RESET);
    else
        printf("%sFAILED%s

", RED, RESET); 

    /* Third test when dequeue was called */
    printf("TEST Dequeue: ");
    retData = (int *)(dequeue( queue ));
    if ( *retData == 10 )
        printf("%sPASSED%s

", GREEN, RESET);
    else
        printf("%sFAILED%s

", RED, RESET); 
        
    printf("TEST Empty (Dequeue): ");
    if ( isQueueEmpty( queue ) == TRUE )
        printf("%sPASSED%s

", GREEN, RESET);
    else
        printf("%sFAILED%s

", RED, RESET); 

    /* Fourth test when enqueue is called after dequeue */
    enqueue( queue, &n2, 'i' );
    printf("TEST Empty (Enqueue): ");
    if ( isQueueEmpty( queue ) == FALSE )
        printf("%sPASSED%s

", GREEN, RESET);
    else
        printf("%sFAILED%s

", RED, RESET); 

    return 0;
}

Queue Function

LinkedList* createQueue()
{
    LinkedList *queue = createLinkedList();
    return queue;
}

void enqueue( LinkedList *queue, void *data, char dataType )
{
    if( queue != NULL )
        insertLast( queue, data, dataType );
}

void* dequeue( LinkedList *queue )
{
    void *retData = NULL;
    if( queue != NULL )
        retData = removeStart( queue );

    return retData;
}

int isQueueEmpty( LinkedList *queue )
{
    int empty = FALSE;
    if( queue->head == NULL )
        empty = TRUE;
/*
    
    **                                                      **
    When the checking was done in such manner, the test PASSED 
    **                                                      **  
    if( queue->count == 0 )
        empty = TRUE;
    printf("%d
", queue->count);
*/
    return empty;
}

Linked List

LinkedList* createLinkedList()
{
    LinkedList *list = malloc(sizeof(LinkedList));
    list->head = NULL;
    list->tail = NULL;
    list->count = 0;
    return list;
}

void insertStart( LinkedList* list, void* inData, char valueType )
{
    /* Creating the node first */
    LinkedListNode *newNd = malloc(sizeof(LinkedListNode));
    newNd->data = inData;
    newNd->type = valueType;
    newNd->next = NULL;

    /* If head and tail is NULL, then allocate the newNd as head and tail */
    if ( list->head == NULL && list->tail == NULL )
    {
        list->head = newNd;
        list->tail = newNd;
    }
    else
    {
        /* newNd will be head, so it has new next pointer */
        newNd->next = list->head;
        list->head = newNd;
    }
    list->count++;
}

void insertLast( LinkedList* list, void *inData, char valueType )
{
    /* Creating the node first */
    LinkedListNode *newNd = malloc(sizeof(LinkedListNode));
    newNd->data = inData;
    newNd->type = valueType;
    newNd->next = NULL;

    /* If head and tail is NULL, then allocate the newNd as head and tail */
    if ( list->head == NULL && list->tail == NULL )
    {
        list->head = newNd;
        list->tail = newNd;
    }
    else
    {
        list->tail->next = newNd;   /* Current tail has new connection */
        list->tail = newNd;         /* new tail is updated */
    }
    list->count++;
}

void* removeStart( LinkedList *list )
{
    LinkedListNode *delNd = NULL;
    void *delData = NULL;

    /* Make sure the list is not empty */
    if ( list->head != NULL && list->tail != NULL )
    {
        delNd = list->head;         /* Remove start is removing from head */
        list->head = delNd->next;   /* Move to next pointer */

        delData = delNd->data;
        free(delNd); delNd = NULL;
        list->count--;
    }
    return delData;
}

void* removeLast( LinkedList *list )
{
    LinkedListNode *delNd = NULL, *travelNd = NULL;
    void *delData = NULL;

    /* Make sure the list is not empty */
    if ( list->head != NULL && list->tail != NULL )
    {
        delNd = list->tail; /* Remove last is removing from tail */

        travelNd = list->head; /* Traversal starts from head */

        /* Loop stops at the node before the tail */
        while( travelNd->next != delNd )
            travelNd = travelNd->next;  /* Move to next pointer */

        travelNd->next = NULL;
        list->tail = travelNd;

        delData = delNd->data;
        free(delNd); delNd = NULL;
        list->count--;
    }
    return delData;
}

LinkedList.h

typedef struct LinkedListNode
{
    struct LinkedListNode *next;
    void *data;
    char type;
} LinkedListNode;

typedef struct LinkedList
{
    struct LinkedListNode *head;
    struct LinkedListNode *tail;
    int count;
} LinkedList;

header.h

#ifndef BOOLEAN
#define BOOLEAN
    #define FALSE 0
    #define TRUE !FALSE
#endif

question from:https://stackoverflow.com/questions/65885158/issue-with-detecting-null-in-head-node-pointer-of-queue-data-structure-in-isempt

Answer 1

isEmptyQueue only checks queue->head, enqueue uses insertLast which checks both queue->head and queue->tail to check for an empty queue.

and then the real error: removeStart never updates queue->tail and removeLast never updates queue->head when removing the last element in the queue.

In short you are not preserving your invariants correctly.