Linked list implementation for a beginner in C

Question

So I've decided to dabble a bit into C, and while it's trippy as heck I've finished an implementation of a linked list for practice. I've pretty sure there's some type of obscure bug or memory leak in here some where since I really don't have a solid understanding of this language yet, so yeah, please review my code and thanks in advance!

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
 int val;
 struct node* next;
} node_t;
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 beginning of the list (pushing to the list)
node_t* push(node_t* head, int val){
 node_t* new_node = malloc(sizeof(*new_node));
 new_node->val = val;
 new_node->next = head;
 return new_node;
}
//Adding an item to the end of the list, returns new node
node_t* add(node_t* head, int val){
 node_t* current = head;
 while(current != NULL && current->next != NULL){
 current = current->next;
 }
 current->next = malloc(sizeof(*current->next));
 current->next->val = val;
 current->next->next = NULL;
 return current->next;
}
//Removing the first item (popping from the list)
//returns the value of the pop and removes the head
int pop(node_t** head){
 if(*head == NULL){
 return -1; //idk how to make some kind of error
 }
 node_t* next_node = (*head)->next;
 int retval = (*head)->val;
 free(*head);
 *head = next_node; //so *head is the node_t* head, but we can still assign after freeing?
 return retval;
}
int remove_last(node_t* head){
 int retval;
 if(head == NULL){
 return -1;//once again, how to make error wtf
 }
 if(head->next == NULL){
 retval = head->val;
 free(head);
 return retval;
 }
 //so at least 2 nodes in linked list
 node_t* second_last = head;
 while(second_last->next->next != NULL){
 second_last = second_last->next;
 }
 retval = second_last->next->val;
 free(second_last->next);
 second_last->next = NULL;
 return retval;
}
int main(){
 node_t* head = NULL;
 head = malloc(sizeof(*head));
 head->val = 1;
 head->next = malloc(sizeof(*head->next));
 head->next->val = 2;
 head->next->next = NULL;
 printf("Starting list with 1, 2\n");
 print_list(head);
 head = push(head, 5);
 printf("List with 5 pushed to the front\n");
 print_list(head);
 add(head, 9);
 printf("List with 9 added to end\n");
 print_list(head);
 pop(&head);
 printf("List with first removed\n");
 print_list(head);
 remove_last(head);
 printf("List with last removed\n");
 print_list(head);
 return 0;
}

• chux: Good use of sizeof ref_object in malloc().

Answer 1

• Bug When the list has only one node, remove_last shall change head to NULL.

• Bug add to an empty list does not update head.

• It is very beneficial to keep a tail pointer. This way appending, and removing the last one, become of a constant time complexity.

• add and remove_last share the list traversal loop. It should be factor out into a function.

• push and add share the code for a node creation. Consider a

  node_t * create_node(int val);
  

• malloc may fail. Always test its return value.

• Returning -1 on a failure effectively prohibits you from having nodes with the value of -1. Consider some other way of reporting an error. There are many possibilities.

• k huang: Hi thanks so much for the feedback! I have some questions though. In the case that remove_last is applied on a one node list, what better alternative would there be than changing it to NULL? I'm confused on why you say add doesn't update the head, since the test to add 9 to the list in the main function seems to work. Also, what exactly do you mean by malloc may fail?
• chux: Re: "beneficial to keep a tail pointer. This way appending, ... become of a constant time complexity." By keeping track of the end of the list and end->next point to the beginning, add() can be done in constant time like push() and pop() without tail pointer.

Answer 2

No need to go into things that others have brought up.

Half of your operations operate on the end of the list. Currently, finding that node is pessimal: you must traverse the entire list from front to back. The data structure you really want for this is a doubly-linked list.

Your naming convention is to have very generic names, like node, add, push, pop, etc. You can’t use multiple data structures with that naming convention in the same program. Consider naming all your doubly-linked integer list functions something like, dllist_int_push, dllist_int_pop, etc.

A common convention is for operations at the end of the list to have names like push_back and pop_back.

If you want one kind of data structure that can hold arbitrary types of data, the least-bad way to do that in C is to store in your nodes void* to data allocated by malloc. Then, client code that takes ownership of the data becomes responsible for freeing it, once and only once, with free. This is far from ideal in many ways, but it’s the closest thing C has to generic programming.

This looks like a great start. Some further directions you might explore include:

• Operations to extract or query elements in the middle of the list, insert at a specific position in the list, search it, etc. If you’re not making use of the constant-time insertion or deletion of elements in the middle, you’re better off using a vector (and typically, even if you are).
• An API with functions that take const pointers to a list and return const views of it, so you can do useful things with const lists.
• A function to splice two lists in constant time.
• Higher-order functions from functional programming, such as map, filter and fold (although in practice, you will find it more useful to run these on arrays or vectors).
• A list that keeps itself sorted by inserting new elements at the correct position. This can perform better for many operations.
• A list of bounded size that allocates its nodes from a contiguous pool, or permutes a fixed set of elements, perhaps representing a path through a graph. The next and prev pointers can then be unsigned 16-bit or 32-bit indices into the pool, instead of 64-bit pointers, and the data will have much better locality of reference, which makes for much fewer cache misses and better performance. (The poor man’s version of this is to allocate the nodes of a temporary local data structure with alloca rather than malloc.)