How to implement a linked list in C?

Question

I am creating a linked list as in the previous question I asked. I have found that the best way to develop the linked list is to have the head and tail in another structure. My products struct will be nested inside this structure. And I should be passing the list to the function for adding and deleting. I find this concept confusing.

I have implemented the initialize, add, and clean_up. However, I am not sure that I have done that correctly.

When I add a product to the list I declare some memory using calloc. But I am thinking shouldn't I be declaring the memory for the product instead. I am really confused about this adding.

Many thanks for any suggestions,

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

#define PRODUCT_NAME_LEN 128

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

typedef struct list 
{
    product_data_t *head;
    product_data_t *tail;
}list_t;

void add(list_t *list, int code, char name[], int cost); 
void initialize(list_t *list);
void clean_up(list_t *list);

int main(void)
{
    list_t *list = NULL;

    initialize(list);
    add(list, 10, "Dell Inspiron", 1500);
    clean_up(list);

    getchar();

    return 0;
}

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

    if(list)
    {
        // First item to add to the list
        list->head->product_code = code;
        list->head->product_cost = cost;
        strncpy(list->head->product_name, name, sizeof(list->head->product_name));
        // Terminate the string
        list->head->product_name[127] = '/0';
    } 
}

// Initialize linked list
void initialize(list_t *list)
{
    // Set list node to null
    list = NULL;
    list = NULL;
}

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

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

============================== Edited ============================

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

#define PRODUCT_NAME_LEN 64

// typedef struct product_data product_data_t;
typedef struct product_data 
{
    int product_code;
    char product_name[PRODUCT_NAME_LEN];
    int product_cost;
}product_data_t;

typedef struct list
{
    struct list *head;
    struct list *tail;
    struct list *next;
    struct list *current_node;
    product_data_t *data;

}list_t;

void add(list_t *list, int code, char name[], int cost); 

int main(void)
{
    list_t *list = NULL;
    list = initialize(list);
    add(list, 1001, "Dell Inspiron 2.66", 1299);

    add(list, 1002, "Macbook Pro 2.66", 1499);

    clean_up(list);

    getchar();

    return 0;
}

void add(list_t *list, int code, char name[], int cost)
{
    /* Allocate memory for the new product */
    product_data_t *product = (product_data_t*) calloc(1, sizeof(*product));
    if(!product)
    {
        fprintf(stderr, "Cannot allocate memory.");
        exit(1);
    }

    /* This is the first item in the list */
    product->product_code = code;
    product->product_cost = cost;
    strncpy(product->product_name, name, sizeof(product->product_name));
    product->product_name[PRODUCT_NAME_LEN - 1] = '\0';

    if(!list->head)
    {
        /* Assign the address of the product. */
        list = (list_t*) product;   
        /* Set the head and tail to this product */
        list->head = (list_t*) product;
        list->tail = (list_t*) product;
    }
    else
    {
        /* Append to the tail of the list. */
        list->tail->next = (list_t*) product;
        list->tail = (list_t*) product;
    }

    /* Assign the address of the product to the data on the list. */
    list->data = (list_t*) product;
}

Answer 1

If you are looking to better understand the basics of linked lists, take a look at the following document:

http://cslibrary.stanford.edu/103/LinkedListBasics.pdf

Answer 2

I am not writing the code here but you need to do the following:

• Create and object of list, this will remain global for the length of program.
• Malloc the size of product _ data _ t.
• For first element (head is NULL), point head to the malloced' address.
• To add next element, move to the end of list and then add the pointer of malloced address to next of last element. (The next of the last element will always be NULL, so thats how you traverse to end.)
• Forget tail for a while.

Answer 3

I think u first need to Imagin back-end. Code are nothing to important. Go here and visualize back-end basic c code of all insertion. 1) Insertion at beginning Visit and scroll to get every instruction execution on back- end And u need front and imagin Go here Back end imagin

And All other possible insertion here.

And important thing u can use this way.

struct Node{
int data;//data field
struct Node*next;//pointer field
};

struct Node*head,*tail; // try this way

or short cut

struct Node{
int data;//data field
struct Node*next;//pointer field
}*head,*tail; //global root pointer

And

<< Click >> To visualize other linked list problem.

Thanks.

Answer 4

A demo for Singly Linked List. If you prefer, try to check Circular Linked List and Doubly Linked List.

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


typedef struct node {
    int val;
    struct node * next;
} node_t;


// Iterating over a list
void
print_list(node_t *head)
{
    node_t *current = head;

    while(current != NULL)
    {
        printf("%d\n", current->val);
        current = current->next;
    }
}


// Adding an item to the end of the list
void
push_end(node_t *head, int val)
{
    node_t *current = head;
    while (current->next != NULL)
    {
        current = current->next;
    }

    current->next = malloc(sizeof(node_t));
    current->next->val = val;
    current->next->next = NULL;
}

// Adding an item to the head of the list
void
push_head(node_t **head, int val)
{
    node_t *new_node = NULL;

    new_node = malloc(sizeof(node_t));
    new_node->val = val;
    new_node->next = *head;

    *head = new_node;
}

// Removing the head item of the list
int
pop_head(node_t **head)
{
    int retval = -1;
    node_t *next_node = NULL;

    if (*head == NULL) {
        return -1;
    }

    next_node = (*head)->next;
    retval = (*head)->val;
    free(*head);
    *head = next_node;

    return retval;
}

// Removing the last item of the list
int
pop_last(node_t *head)
{
    int retval = 0;
    node_t *current = NULL;

    if (head->next == NULL) {
        retval = head->val;
        free(head);
        return retval;
    }

    /* get to the second to last node in the list */
    current = head;
    while (current->next->next != NULL) {
        current = current->next;
    }

    /* now current points to the second to last item of the list.
       so let's remove current->next */
    retval = current->next->val;
    free(current->next);
    current->next = NULL;

    return retval;
}

// Removing a specific item
int
remove_by_index(node_t **head, int n)
{
    int i = 0;
    int retval = -1;
    node_t *current = *head;
    node_t *temp_node = NULL;

    if (n == 0) {
        return pop_head(head);
    }

    for (i = 0; i < n - 1; i++) {
        if (current->next == NULL) {
            return -1;
        }
        current = current->next;
    }

    temp_node = current->next;
    retval = temp_node->val;
    current->next = temp_node->next;
    free(temp_node);

    return retval;
}


int
main(int argc, const char *argv[])
{
    int i;
    node_t * testnode;

    for (i = 0; i < argc; i++)
    {
        push_head(&testnode, atoi(argv[i]));
    }

    print_list(testnode);

    return 0;
}

// http://www.learn-c.org/en/Linked_lists
// https://www.geeksforgeeks.org/data-structures/linked-list/