Singly Linked List Implementation in C using 3 different typedefs

Question

So, my task is to to write a full implementation of a Singly Linked List in C.

I wrote before implementations of a stack and a dynamic vector, but this time, the linked list confuses me a little because of the use of 3 different typedef.

I'll be glad to get your review and tips on my code.

I would make a test file as I always do, but I am having a hard time of writing one because of all the void * casts .

I won't add all the 14 functions, i'll add just the functions that I'm least sure of.

So we must follow the following typedefs and the given prototypes. So neither of them can be changed.

I also had to add a "dummy node" as the last node, which means there will be always a "dummy node" that will indicate that the one before it, is the "real" last node in the list. This is part of the instructions.

typedef struct slist slist_ty;

typedef struct slist_node slist_node_ty;

typedef slist_node_ty *slist_iter_ty;

This is my implementation of the structs: They asked us to allow in theory any type of data in our nodes, that's why I wrote void *.

struct slist
{
    slist_iter_ty head;
    slist_iter_ty end;
};

struct slist_node
{
    void *data;
    slist_iter_ty next;
};

And these are the functions:

/* Creates an empty single-linked list and returns pointer to the head */
/* returns NULL on failure*/
/* Complexity: O(1) */
slist_ty *SlistCreate(void)
{
    slist_ty *new_list = (slist_ty *)malloc(sizeof(slist_ty));
    if (NULL == new_list)
    {
        fprintf(stderr, "Failed to allocate memory\n");
        return(NULL);
    }
    
    new_list->head = NULL;
    /* create a dummy node that will represent the end of the list */
    new_list->end = (slist_node *)malloc(sizeof(slist_node));
    if (NULL == new_list->end)
    {
        fprintf(stderr, "Failed to allocate memory\n");
        free(new_list);
        return(NULL);
    }
    
    new_list->end->data = NULL;
    new_list->end->next = NULL;
    
    return(new_list->head);
}

/* Deletes entire List */
/* Complexity: O(n) */
void SlistDestroy(slist_ty *slist)
{
    slist_iter_ty temp = NULL;
    
    assert(slist);
    
    while(NULL != slist->head)
    {
        tmp = slist->head;
        slist->head = temp;
        free(temp);
    }
    
    free(slist->end);
    slist->end = NULL;
    
    free(slist);
    slist = NULL;
}

/* Insters the element after the iterator, returns iterator to the new node */
/* TODO Undefined behaviour if iter is slist_END */
/* Complexity: O(1) */
slist_iter_ty SlistInsert(slist_iter_ty iter, void *data)
{
    slist_iter_ty new_node = NULL;
    
    assert(iter);
    assert(iter->next);
    assert(data);
    
    new_node->data = data;
    new_node->next = iter->next;
    iter->next = new_node;
    
    return(new_node);
}
    
    
    /* Returns iterator to end of the list */
    /* Complexity: O(1) */
    slist_iter_ty SlistIteratorEnd(const slist_ty *slist)
    {
        slist_iter_ty iterator = slist->head;
        
        assert (slist);
        
        if (NULL == slist->head)
        {
            return(NULL);
        }
        
        while (NULL != iterator->next->data)
        {
            iterator = iterator->next;
        }
        
        return(iterator);
    }

My question along the request to get a feedback is:

Should I free any new slist_iter_ty that I make ? For example, I made an iterator of type slist_iter_ty in the last function, in order to help me to traverse the list. But I can't free the iterator because I need to return it as the return value.

I also made a new_node in the SlistInsertfunction.

Will it be freed as part of the SlistDestroy function?

Thanks.

Answer 1

slist - is the list. when you create this list you use malloc so when you want to destroy it you need to free the list.

also - you used malloc every time you used insert. so when you want to destroy the list, you need to empty it from all the nodes - so you will need to free node by node

i can see you doesn't use mallloc in slist insert - how can you keep the data without use malloc?

In destroy function

 while(NULL != slist->head)
{
    tmp = slist->head;
    slist->head = temp;
    free(temp);
}

I think what you meant is:

while(NULL != slist->head)
{
    tmp = slist->head;
    slist->head = slist->head->next;
    free(tmp);
}

In insert function

slist_iter_ty new_node = NULL;

what you should write:

new_node = (slist_iter_ty) malloc(sizeof(slist_node));

in slist end function

slist_iter_ty SlistIteratorEnd(const slist_ty *slist)

you can just return (after you assert something :)) :

return (slist->end);

(otherwise it wouldent be O(1) it would be O(n))