Circular linked list in C

Question

Let me know if it seems right to you and if anything can be optimized. My concern is that I'm unsure if circular linked lists are supposed to have a tail. I've implemented it just using a head. Is that wrong? If so, how would you change it to make it proper?

/* 
 * Circular Linked List
 *
 */
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
 int data;
 struct Node *next;
} Node;
void insert_beg_of_list(Node *current, int data);
void delete(Node *current, int data);
void print_list(Node *current);
int find_in_a_list(Node *current, int data);
void insert_beg_of_list(Node *current, int data) {
 //keep track of first node
 Node *head = current;
 while(current->next != head) {
 current = current->next;
 }
 current->next = (Node*)malloc(sizeof(Node));
 current = current->next;
 current->data = data;
 current->next = head;
}
void delete_from_list(Node *current, int data) {
 Node *head = current;
 while(current->next != head && (current->next)->data != data) {
 current = current->next;
 }
 if(current->next == head) {
 printf("%d element is not found\n\n", data);
 return;
 }
 Node *tmp;
 tmp = current->next;
 current->next = tmp->next;
 free(tmp); 
 return;
}
void print_list(Node *current) {
 Node *head = current;
 current = current->next;
 while(current != head){
 printf(" %d ", current->data);
 current = current->next;
 }
}
int find_in_a_list(Node *current, int data) {
 Node *head = current;
 current = current->next;
 while(current != head) {
 if(current->data == data) {
 // Key found
 return 1;
 }
 current = current->next;
 }
 // Key is not found
 return 0;
}
int main() {
 Node *head = (Node *)malloc(sizeof(Node));
 head->next = head; 
 int data = 0;
 int usr_input = 0;
 while(1){
 printf("0. Exit\n");
 printf("1. Insert\n");
 printf("2. Delete\n");
 printf("3. Print\n");
 printf("4. Find\n");
 scanf("%d", &usr_input);
 // can also use a switch instead
 if( usr_input == 0) {
 exit(0);
 } else if(usr_input == 1) {
 printf("\nEnter an element you want to insert: ");
 scanf("%d", &data);
 insert_beg_of_list(head, data);
 } else if(usr_input == 2) {
 printf("\nEnter an element you want to delete: ");
 scanf("%d", &data);
 delete_from_list(head, data);
 } else if( usr_input == 3) {
 printf("The list is ");
 print_list(head);
 printf("\n\n");
 } else if( usr_input == 4) {
 printf("\nEnter an element you want to find: ");
 scanf("%d", &data);
 int is_found = find_in_a_list(head, data);
 if (is_found) {
 printf("\nElement is found\n\n");
 } else {
 printf("\nElement is NOT found\n\n");
 }
 }
 }
 return 0;
}

• user3629249: a circular linked list should always have both a head and a tail. The head is where to add/write next, the tail is where to delete/read next. This means there should be a separate head pointer and a separate tail pointer. those pointers keep track of the end of the circular linked list

Answer 1

1. When making a collection of routines to handle a type, strongly advise to create a create and destroy function. Rather then the below, consider some initialization function.

   // Replace this code
   Node *head = (Node *)malloc(sizeof(Node));
   head->next = head; 
   // with this
   Node *new_list(void ) {
    Node *head = malloc(sizeof *head);
    if (head) {
    head->next = head;
    } 
    return head;
   } 
   ...
   Node *head = new_list();
   

2. The names on the functions benefit by having the leading text indicate the grouping. Avoid function delete() - too generic.

   void clist_insert_beg(Node *current, int data);
   void clist_delete(Node *current, int data);
   void clist_print(Node *current);
   int clist_find(Node *current, int data);
   

3. Consider 4 operations: Add_Before_First(), Remove_First(), Append(), Remove_End(). A circular list means it is relatively easy (O(1)) to do something at both ends of the list. This code's delete_from_list() is nothing more that a typical linked list would do and take O(n) time. Sadly even the insert_beg_of_list() also takes O(n) time. Recommend to re-work this code so at least 1 of 2 "head" functions and at least 1 of the "tail" functions can operate in O(1) time (no while loops).

4. Having a circular list with only a single pointer is do-able and perform 3 of the above 4 in O(1) time. Consider a list that points to the tail. No need for a head pointer as tail->next is the head.

5. Recommend a simpler to code and maintain allocation style. The cast is not needed and the sizeof works even is the type of *(current->next) changes.

   // current->next = (Node*)malloc(sizeof(Node));
   current->next = malloc(sizeof *(current->next));
   

6. Though posted as 1 file, better to post as a circular_list.c, circular_list.h, main_sample_usage.c files to clearly identify that which is public and private.

7. I have doubts delete_from_list() works when the last element is deleted. I think that is because of the overall design. IMO, when a list contains no data, it should consume minimal space. IOW, a NULL pointer is an empty list. When a list type is used heavily, there are often many empty lists. So an empty list of a pointer to a node pointing to itself seems wasteful.

8. Functions that do not modify the list should use const.

   // int find_in_a_list(Node *current, int data) {
   int find_in_a_list(const Node *current, int data) {
   // void print_list(Node *current) {
   void print_list(const Node *current) {
   

9. Hoping to find functions like

   unsigned count_list(const Node *current);
   bool empty_list(const Node *current);
   

10. Minor Use int main(void) {