Single linked list

Question

Hello,

I have created a single linked list. Everything works fine.

I just want to know if I have done anything potentially dangerous in my code. The code snippets I am concerned about is my push, pop, and clean-up. The parts of the code is just for user interaction so not really important (I posted anyway so that it was more clear in what I was doing). Just the linked list application.

Many thanks for any suggestions, as this is my fist attempt.

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

typedef struct product_data product_data_t;
struct product_data
{
    int product_code;
    char product_name[128];
    int product_cost;
    product_data_t *next;
};

static product_data_t *head = NULL;
static product_data_t *tail = NULL;
static product_data_t *new_product = NULL;

// Push a product on to the list.
void push(int code, char name[], int cost); 
// Pop (delete) a product from the list.
void pop(int code);
// Display all product in the list.
void display_list();
// Delete all memory allocated on the list
void clean_up();
// Display menu
void menu();

int main(void)
{
    menu();

    getchar();

    return 0;
}

void push(int code, char name[], int cost)
{
    // Allocate memory for the new product
    new_product = calloc(1, sizeof(product_data_t));
    if(!new_product)
    {
        fprintf(stderr, "Cannot allocated memory");
        exit(1);
    }

    /* Populate new products elements fields */
    new_product->product_code = code;
    strncpy(new_product->product_name, name, sizeof(new_product->product_name));
    new_product->product_cost = cost;
    new_product->next = NULL;

    // Set the head and tail of the linked list
    if(head == NULL)
    {
        // First and only product
        head = new_product;
    }
    else
    {
        tail->next = new_product;
    }

    tail = new_product;
}

// Find the product by code and delete
void pop(int code)
{
    product_data_t *product = head;
    product_data_t *temp = NULL;
    product_data_t *previous = head;
    int found = 0; // 0 - Not Found, 1 - Found

    if(!head)
    {
        puts("The list is empty");
        return;
    }

    while(product)
    {
        if(product->product_code == code)
        {
      found = 1; // Found
      // Check if this is in the first node - deleting from head
      if(head->product_code == code)
      {
       temp = head;
       head = head->next;
       free(temp);

       // Finished Deleting product
       return;
      }

      // Check if this is the end node - deleting from the tail
      if(tail->product_code == code)
      {
       temp = tail;
       tail = previous;
       free(temp);

       // Finished deleting product
       return;
      }

            // delete from list if not a head or tail
            temp = product;
            previous->next = product->next;
            free(temp);

            // Finished deleting product
            return;
        }
        // Get the address of the previous pointer.
        previous = product;
        product = product->next;  
    }

    if(!found)
    {
        printf("code [ %d ] was not found\n", code);
    }

    // Set all to null after finished with them
    product = NULL;
    temp = NULL;
    previous = NULL;
}

// Traverse the linked list
void display_list()
{
    // Start at the beginning
    product_data_t *product = head;

    while(product)
    {
        printf("===================================\n");
        printf("Product code: \t\t%d\n", product->product_code);
        printf("Product name: \t\t%s\n", product->product_name);
        printf("product cost (USD): \t%d\n", product->product_cost);
        printf("===================================\n\n");

        // Point to the next product
        product = product->next;
    }
    // Finished set to null
    product = NULL;
}

// Release all resources
void clean_up()
{    
    product_data_t *temp = NULL;

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

    // End program - goodbye
    exit(0);
}

void menu()
{
    int choice = 0, code = 0, cost = 0;
    char name[128] = {0};

    do
    {
        fflush(stdin); // Flush the input buffer

        puts("========= Welecome to linked list ===============");
        puts("[1] Add new product to the list");
        puts("[2] Delete a product from the list");
        puts("[3] Display all products");
        puts("[4] Exit and clean up");
        printf("Enter your choice: ");
        scanf("%d", &choice);

        switch(choice)
        {
        case 1:
            printf("Enter product code: ");
            scanf("%d", &code);
            printf("Enter cost: ");
            scanf("%d", &cost);
            printf("Enter name: ");
            scanf("%s", name);
            push(code, name, cost);
            break;

        case 2:
            printf("Enter product code: ");
            scanf("%d", &code);
            pop(code);
            break;

        case 3:
            display_list();
            break;

        case 4:
            clean_up();
            break;

        default:
            puts("Incorrect choice");
            break;
        }
    }while(choice != 4);
}

Answer 1

strncpy(new_product->product_name, name, sizeof(new_product->product_name));

if the string is longer than the size you have it won't be terminated correctly.

Answer 2

From pop()

            if(head->product_code == code)
            {
                    temp = head;
                    head = head->next;
                    free(temp);

                    // Finished Deleting product
                    return;
            }

In the case of there only being one item, 'head' and 'tail' would be pointing to the same node. However, if you pop this one item, 'head' will be adjusted but 'tail' will still be pointing to the free'd node. This will leave a bad pointer, which may cause your computer to explode.

Addendum: Similarly, 'new_product' will be dangling if you ever pop the last node that was pushed, and clean_up() will leave the 'tail' pointer dangling as well. Even if the code sample provided will never dereference these after they're free'd, dangling pointers in C code should always be treated as "potentially dangerous".

Answer 3

Agree with the issues raised by goldPseudo and thaggie/Steven.

In push(), replace strncpy() with strlcpy() to ensure the destination string is always NUL terminated.

In cleanup(), I'd suggest that you remove the exit(0); statement -- you don't need it. Exiting a programme from within a subroutine is generally not the best thing to do.

You should take away one lesson from creating your first singly linked list, and that is, singly linked lists are generally not very useful in the real world because:

• They're too hard to manipulate. Just look at the complexity of your pop() subroutine.
• Relatively slow because you have to start at the beginning of the list each time you want to retrieve an element from the list.

You should now attempt to write your first doubly linked list. While doubly linked lists are more complex to implement, they are easier to manipulate (especially when deleting an element) than singly linked lists.

Answer 4

I see no reason why new_product should be global and every reason why it should not be.

Answer 5

Is there any reason you call exit(0) from clean_up function? I think this is potential dangerous, since you don't give a chance to the user to finish program correctly.

As well I would suggest you to use data encapsulation when you building up you data structure:

typedef struct
{
    int product_code;
    char product_name[128];
    int product_cost;
    list_node *next;
} list_node;

typedef struct
{
   list_node* head;
   list_node* tail;
   list_node* current;
   int        size;
} list;

Also it's a good practice to use trail dummy node at the head of your list to make your code more generic.

Answer 6

Following normal naming convensions, push and pop are related to stacks - i.e. push() should add an item to the top of the stack (you add to the tail of the list, which is fine!), and pop() should return and remove the item from the top of the stack (you search for a named item anywhere in the list and remove it.)
Function names aside, I would suggest a more generic (abstract) implementation of the list, where the content of a node is a pointer to arbitrary data (which in your special case will later be a product_data). This way your linked list can be re-used for any content, and is easier to debug, read and to maintain.
It would also be a better idea not to have stuff global, but rather permit multiple instances of a list. The normal C way is to keep the data in a struct, and then to pass an instance as first argument to each function.

Answer 7

It looks like you're on the right track, but there are issues. I would remove the global variables, and instead have a list_t struct (containing head and tail) that you pass into functions. As others have noted, you may also want to make the list generic by using (e.g.) a node_t type and void* data pointer.

Generally push and pop are used to refer to adding or removing an item at the beginning, not an arbitrary location (as you do); this is just a question of naming.

If you had product_name char *product_name instead, that would allow you to remove the length limitation as well as the need for strncpy. You would just have the caller allocate the string, and then free it in clean_up.

You could consider using a enum to improve your menu's readability. For "Check if this is in the first node - deleting from head" (same for tail), you should just compare head to product, not compare the codes.

After "tail = previous", you should set tail->next to NULL.