4
\$\begingroup\$

I made a simple linked list in C with the following functionalities: Create(creates the list); Find(searches for an element in the list); Insert(inserts a value at the beginning of the list); Destroy(destroys the entire list). It only uses integers (for simplicity), and I want to know for possible errors and how to improve it in general.

The node structure:

typedef struct sllist
{
    int val;
    struct sllist* next;
}
sllnode;

The functions:

#include <stdio.h>
#include <stdlib.h>
#include "node.c"

/*
 *Creates the linked list with a single value
*/
sllnode *create(int value)
{
    sllnode *node;
    node = (sllnode *) malloc(sizeof(sllnode));

    if (node == NULL)
    {
        puts("Memory error");
        return NULL;
    }

    node->val = value;
    node->next = NULL;

    return node;
}

/*
 *Searches for an element in the list.
 *Returns 1 if its found or 0 if not
*/
int find(sllnode *head, int value)
{
    sllnode *trav = head;

    do
    {
        if (trav->val == value)
        {
            return 1;
        }
        else
        {
            trav = trav->next;
        }
    } while (trav != NULL);

    return 0;
}

/*
 *Inserts a value at the beginning of the list
*/
sllnode *insert(sllnode *head, int value)
{
    sllnode *new_node = (sllnode *) malloc(sizeof(sllnode));

    if (new_node == NULL)
    {
        puts("Memory error");
        return NULL;
    }

    new_node->val = value;
    new_node->next = head;
    head = new_node;

    return head;
}

/*
 *Destroys (i.e frees) the whole list
*/
void *destroy(sllnode *head)
{
    sllnode *temp = head;

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

int main(void)
{
    return 0;
}   
\$\endgroup\$
2
\$\begingroup\$

Including a C file

Convention is that all shared stuff is declared in .h files.

Minor 1

In destroy(), you have the return type void*. Remove the pointer star and it's fine.

Minor 2

sllnode *create(int value)
{
    sllnode *node;
    node = (sllnode *) malloc(sizeof(sllnode));

    if (node == NULL)
    {
        puts("Memory error");
        return NULL;
    }
    ...

It's a bad idea to abuse standard output from within algorithms/data structures. After all, everything that may go wrong is that there is no memory enough for the new node; returning NULL may well indicate that situation.

Minor 3

node = (sllnode *) malloc(sizeof(sllnode));

More idiomatic C is

node = malloc(sizeof *node);

Minor 4

You "append" the new nodes in reversed direction. Basically this is a (linked) stack and not a list.

Minor 5

while (temp != NULL)
{
    free(temp);
    temp = temp->next;
}

Don't do this. Instead have something like

while (temp) 
{
    next_node = temp->next;
    free(temp);
    temp = next_node;
}

Summa summarum

For a starter, I had this in mind:

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

typedef struct linked_list_node {
    int value;
    struct linked_list_node* next;
} linked_list_node;

typedef struct {
    linked_list_node* head;
    linked_list_node* tail;
} linked_list;

void linked_list_init(linked_list* list)
{
    if (!list)
    {
        return;
    }

    list->head = NULL;
    list->tail = NULL;
}

void linked_list_free(linked_list* list)
{
    linked_list_node* current_node;
    linked_list_node* next_node;

    if (!list)
    {
        return;
    }

    current_node = list->head;

    while (current_node)
    {
        next_node = current_node->next;
        free(current_node);
        current_node = next_node;
    }
}

int linked_list_append(linked_list* list, int value)
{
    linked_list_node* new_node;

    if (!list)
    {
        return 1;
    }

    new_node = malloc(sizeof *new_node);

    if (!new_node)
    {
        return 1;
    }

    new_node->value = value;

    if (list->head)
    {
        list->tail->next = new_node;
    }
    else
    {
        list->head = new_node;
    }

    list->tail = new_node;
    return 0;
}

int linked_list_index_of(linked_list* list, int value)
{
    int index;
    linked_list_node* node;

    if (!list)
    {
        return -2;
    }

    for (node = list->head, index = 0; node; node = node->next, index++)
    {
        if (node->value == value)
        {
            return index;
        }
    }

    return -1;
}

int main() {
    int i;

    linked_list my_list;
    linked_list_init(&my_list);

    for (i = 0; i < 10; ++i)
    {
        linked_list_append(&my_list, i);
    }

    printf("%d %d\n",
           linked_list_index_of(&my_list, 4),
           linked_list_index_of(&my_list, 100));

    linked_list_free(&my_list);
    return 0;
}

Hope that helps.

\$\endgroup\$
  • \$\begingroup\$ Thanks! I added the elements in the beginning of the list because that's how my CS course told me it's done. Is there any practical difference in the approach? \$\endgroup\$ – Lúcio Cardoso Sep 30 '16 at 19:52
  • \$\begingroup\$ @LúcioCardoso For list data structures (singly/doubly linked, array-based) insertion order is important in some algorithms/settings. Plus I added a tiny "reference" implementation + 1 more minor point. \$\endgroup\$ – coderodde Sep 30 '16 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.