How to implement a linked list in C?

Question

I am creating a linked list , as in the previous question I asked. I found that the best way to develop a linked list is to have a head and tail in a different structure. My product structure will be nested inside this structure. And I have to pass a list of functions to add and remove. I find this concept confusing.

I implemented initialization, add and clean_up. However, I am not sure that I did it right.

When I add a product to the list, I declare some memory using calloc. But I think I should not declare a memory for a product. I am really confused by this addition.

Thanks so much 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

In your case, the head and tail can simply point to the beginning and end of the linked list. With a single linked list, only a head is really needed. It has the simplest, linked list, you can make using only such a structure as:

 typedef struct listnode { //some data struct listnode *next; }listnodeT; listnodeT *list; listnodeT *current_node; list = (listnodeT*)malloc(sizeof(listnodeT)); current_node = list; 

and as long as the list always points to the beginning of the list and the last element has the next NULL, you are fine and you can use current_node to move around the list. But sometimes, to simplify moving the list and store any other data about the list, a head and tail token is used and wrapped in their own structure, as you did. So, your add and initialize functions will be something like (minus error detection)

  // Initialize linked list void initialize(list_t *list) { list->head = NULL; list->tail = NULL; } void add(list_t *list, int code, char name[], int cost) { // set up the new node product_data_t *node = (product_data_t*)malloc(sizeof(product_data_t)); node->code = code; node->cost = cost; strncpy(node->product_name, name, sizeof(node->product_name)); node->next = NULL; if(list->head == NULL){ // if this is the first node, gotta point head to it list->head = node; list->tail = node; // for the first node, head and tail point to the same node }else{ tail->next = node; // append the node tail = node; // point the tail at the end } } 

In this case, since it is the only linked list, the tail is really only useful for adding items to the list. To insert an item, you will need to go through the list starting at the head. Where the tail really comes in handy, there is a doubly linked list; it allows you to navigate through the list starting at both ends. You can go through this list, for example

 // return a pointer to element with product code product_data_t* seek(list_t *list, int code){ product_data_t* iter = list->head; while(iter != NULL) if(iter->code == code) return iter; iter = iter->next; } return NULL; // element with code doesn't exist } 

Often, the head and tail are fully engineered nodes that are used as sentinels to indicate the beginning and end of a list. They themselves do not store data (more precisely, their data is a watch marker), they are just holders of space for the front and rear. This can facilitate the coding of some algorithms associated with linked lists, due to the presence of two additional elements. In general, linked lists are flexible data structures with several ways to implement them.

Oh yes, and nik is right, playing with linked lists is a great way to get good directions with pointers and indirection. And they are also a great way to practice recursion! After you get good results with a linked list, try building a tree and use recursion to jump to the tree.

Answer 2

Perhaps you want the list data structure to be external to the stored data.

Say what you have:

  struct whatever
 {
    int x_;
 }

Then your list structure will look like this:

  struct Whatever_Node
 {
    Whatever_Node * next_
    Whatever * data_
 }

Ryan Oberoi commented on this, but without an example.

Answer 3

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

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

Answer 4

If you study the theory of C-pointers, this is a good exercise. Otherwise, this seems like too much indirection for code that is not shared (like in a library).

Instead of highlighting a static 128-byte string of characters, you may need to do a few more exercises with a pointer and use a highlighted string of the exact length that you clear on exit.

Academically, kungfucraig structure looks more general than the one you defined.

Answer 5

In memory, your items are linked by pointers in the list structure

item1 → item2

Why not make the list structure part of your item?

Then you highlight the product item, and the list structure is inside it.

 typedef struct product_data { int product_code; char product_name[PRODUCT_NAME_LEN]; int product_cost; struct list_t list; // contains the pointers to other product data in the list }product_data_t; 

Answer 6

You use calloc'ing for your list_t structure, just pointers to a list of goals and a tail, which you don't want to do.

When adding to a linked list, allocate space for the actual node in the list, which is your product_data_t structure.

Answer 7

You are allocating the wrong piece of memory. Instead of allocating memory for each element of the list, you allocate for the title and tail of the list.

For simplicity, get rid of the separate structure for the head and tail. Make them global variables (the same area they are currently in) and change them as listhead and listtail. This will make the code more readable (you will not uselessly go through a separate structure), and you will not make a distribution error for the wrong structure.

You do not need a tail pointer unless you make a double list. This is not an important item to add as soon as you create a linked list, but not required.

Answer 8

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

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

Answer 9

I think you need to create an Imagin back-end first. The code has nothing to do. Go here and visualize the base code from all the inserts. 1) Insert at the beginning Visit and scroll to get each command running in the background And you need a front and imagine Go here Back end imagin

And all the other possible inserts are here.

And it’s important that you can use this method.

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

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

or short cut

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

AND

<< Click > To visualize a problem with another linked list.

Thank you

Answer 10

Demo for a separate list . If you prefer, try checking out the Circular Linked List and the 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 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/ 

Answer 11

A linked list implementation inspired by the implementation used in the Linux kernel:

 // for 'offsetof', see: https://stackoverflow.com/q/6433339/5447906. #include <stddef.h> // See: https://stackoverflow.com/q/10269685/5447906. #define CONTAINER_OF(ptr, type, member) \ ( (type *) ((char *)(ptr) - offsetof(type, member)) ) // The macro can't be used for list head. #define LIST_DATA(ptr, type, member) \ CONTAINER_OF(ptr, type, member); // The struct is used for both: list head and list nodes. typedef struct list_node { struct list_node *prev, *next; } list_node; // List heads must be initialized by this function. // Using the function for list nodes is not required. static inline void list_head_init(list_node *node) { node->prev = node->next = node; } // The helper function, mustn't be used directly. static inline void list_add_helper(list_node *prev, list_node *next, list_node *nnew) { next->prev = nnew; nnew->next = next; nnew->prev = prev; prev->next = nnew; } // 'node' must be a list head or a part of a list. // 'nnew' must not be a list head or a part of a list. It may // be uninitialized or contain any data (even garbage). static inline void list_add_after(list_node *node, list_node *nnew) { list_add_helper(node, node->next, nnew); } // 'node' must be a list head or a part of a list. // 'nnew' must not be a list head or a part of a list. It may // be uninitialized or contain any data (even garbage). static inline void list_add_before(list_node *node, list_node *nnew) { list_add_helper(node->prev, node, nnew); } // 'node' must be part of a list. static inline list_node *list_del(list_node *node) { node->prev->next = node->next; node->next->prev = node->prev; return node->prev; } 

Usage example:

 #include <stdio.h> // The struct must contain 'list_node' to be able to be inserted to a list typedef struct { int data; list_node node; } my_struct; // Convert 'list_node *' to 'my_struct*' that contains this 'list_node' static inline my_struct* get_my_struct(list_node *node_ptr) { return LIST_DATA(node_ptr, my_struct, node); } void print_my_list(list_node *head) { printf("list: {"); for (list_node *cur = head->next; cur != head; cur = cur->next) { my_struct *my = get_my_struct(cur); printf(" %d", my->data); } printf(" }\n"); } // Print 'cmd' and run it. Note: newline is not printed. #define TRACE(cmd) \ (printf("%s -> ", #cmd), (cmd)) int main() { // The head of the list and the list itself. It doesn't contain any data. list_node head; list_head_init(&head); // The list nodes, contain 'int' data in 'data' member of 'my_struct' my_struct el1 = {1}; my_struct el2 = {2}; my_struct el3 = {3}; print_my_list(&head); // print initial state of the list (that is an empty list) // Run commands and print their result. TRACE( list_add_after (&head , &el1.node) ); print_my_list(&head); TRACE( list_add_after (&head , &el2.node) ); print_my_list(&head); TRACE( list_add_before(&el1.node, &el3.node) ); print_my_list(&head); TRACE( list_del (head.prev) ); print_my_list(&head); TRACE( list_add_before(&head , &el1.node) ); print_my_list(&head); TRACE( list_del (&el3.node) ); print_my_list(&head); return 0; } 

The result of executing the above code:

 list: { } list_add_after (&head , &el1.node) -> list: { 1 } list_add_after (&head , &el2.node) -> list: { 2 1 } list_add_before(&el1.node, &el3.node) -> list: { 2 3 1 } list_del (head.prev) -> list: { 2 3 } list_add_before(&head , &el1.node) -> list: { 2 3 1 } list_del (&el3.node) -> list: { 2 1 } 

http://coliru.stacked-crooked.com/a/6e852a996fb42dc2

Of course, in real life, you will most likely use malloc for list items.

Answer 12

In C, we need to define a Node to store integer data and a pointer to the next value.

 struct Node{ int data; struct Node *next; }; 

To add a new node, we will add a function that has data as an int parameter. First we create a new Node n. If the program does not create n, we display an error message and return with a value of -1. If we create n, we will set the data from n to have the data for this parameter, and the next one will contain the root, since it has the top of the stack. After that, we set the root for the link to the new Node n.

Answer 13

 #include <stdio.h> struct node { int data; struct node* next; }; int main() { //create pointer node for every new element struct node* head = NULL; struct node* second = NULL; struct node* third = NULL; //initialize every new pointer with same structure memory head = malloc(sizeof(struct node)); second = malloc(sizeof(struct node)); third = malloc(sizeof(struct node)); head->data = 18; head->next = second; second->data = 20; second->next = third; third->data = 31; third->next = NULL; //print the linked list just increment by address for (int i = 0; i < 3; ++i) { printf("%d\n",head->data++); return 0; } } 

This is an easy way to understand how a pointer works with a pointer. Here you just need to create a pointer with a new node so that we can make it as automatic.

Answer 14

Go STL route. Declaring linked lists should be agnostic for the data. If you really need to write it yourself, see how it is implemented in STL or Boost.

You should not even keep * the next pointer with your data structure. This allows you to use the data structure of your product in various data structures - trees, arrays and queues.

We hope that this information will help in your design decision.

Edit:

Since the message is labeled C, you have equivalent implementations using void * pointers that follow the basic design principle. For example, check:

Documentation | list.c | list.h