Do I have too many cases when implementing circular linked list in c

Question

I'm implementing circular linked list in C of which the central part is the add2list() function which adds nodes based on the int data field in ascending order. I have 5 different scenarios of when to add the node in the function which makes me think that it's kind of too much. Most of the implementations I've seen in google have 2 or 3 cases. However most of those implementations also use multiple functions for adding a node (separate function for adding a node to the beginning/end of the list). I would appreciate your feedback whether I have cases that can be merged (for example case 2 and 4 are quite similar). I added printList() function if you would like to print the list.

This is my code:

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

typedef struct node * ptr;
typedef struct node {
    int data;
    ptr next;
}item;

void add2list(ptr *head, int num);
void printList(ptr p);

int main() {
    ptr head = NULL;

    add2list(&head, 1);
    add2list(&head, 2);
    add2list(&head, 5);
    add2list(&head, 3);
    add2list(&head, 0);
    add2list(&head, 4);
    add2list(&head, -2);
    printList(head);

    return 0;
}


void add2list(ptr *head, int num) {
    ptr p1, p2, t;

    t = (ptr) malloc(sizeof(item));

    if(!t) {
        printf("not enough memory\n");
        exit(0);
    }

    t -> data = num;
    p1 = *head;

    while(p1 != NULL && p1 -> next != *head && p1 -> data < num) {
        p2 = p1;
        p1 = p1 -> next;
    }

    if(!p1) { 
        //case 1 - if the list is empty
        *head = t;
        t -> next = *head;
    } else if(p1 == *head) {
        if(p1 -> data < t -> data) {
            //case 2 - if we need to add a node to the end of the list if there was only one node before
            (*head) -> next = t;
            t -> next = *head;
        } else {
            //case 3 - if we need to add a node to the beginning of the list
            while(p1 -> next != *head) {
                p1 = p1 -> next;
            }
            p1 -> next = t;
            t -> next = *head;
            *head = t;
        }
    } else if(p1 -> data < t -> data){
        //case 4 - need to add a node at the end of the list if there's more than one node
        p1 -> next = t;
        t -> next = *head;
    } else {
        //case 5 - need to add a node in the middle
        p2 -> next = t;
        t -> next = p1;
    }
}

void printList(ptr head) {
    ptr tmp;

    tmp = head;
    while(tmp -> next != head) {
        printf("%d ->\n", tmp -> data);
        tmp = tmp -> next;
    }
    printf("%d ->\n", tmp -> data);
}

Answer 1

Here's my attempt (warning, code is untested):

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

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

void add2list(Node **proot, int value) {
    Node **pcur;
    Node *new;

    if (!(new = malloc(sizeof *new))) {
        fprintf(stderr, "malloc(%zu): %s\n", sizeof *new, strerror(errno));
        exit(EXIT_FAILURE);
    }
    new->data = value;

    if (!*proot) {
        // case 1: insert into empty list
        new->next = new;
        *proot = new;
        return;
    }

    if ((*proot)->data >= value) {
        // case 2: insert at beginning of list
        pcur = &(*proot)->next;
        while (*pcur != *proot) {
            pcur = &(*pcur)->next;
        }
        new->next = *proot;
        *proot = *pcur = new;
        return;
    }

    // case 3: insert elsewhere
    pcur = &(*proot)->next;
    while (*pcur != *proot && (*pcur)->data < value) {
        pcur = &(*pcur)->next;
    }
    new->next = *pcur;
    *pcur = new;
}

The function first allocates a new node and sets its data member. This is common to all three cases, as in your code.

Case 1 is insertion into an empty list. This is pretty trivial.

Case 3 is the "normal" case and almost identical to insertion into a non-circular list (the only difference being the test for end-of-list, which involves NULL for a non-circular list). (This subsumes your cases 2, 4, 5.)

Case 2 (insertion at the beginning) is where it gets tricky. This case is special because here we have to update two variables, not just one: The variable in the caller, *proot (because it has to be updated to the new head of the list), as well as the next pointer of the last node in the list (to keep it properly circular). In this case we have an extra loop that walks through the whole list just to find the address of the last next pointer in the list (stored in pcur). At the end we update *proot and *pcur together. (This is your case 3.)

Answer 2

Yes, there are definitely too many cases. You should avoid situations like these one and use a top-down approach whenever possible. Doing so your code will be cleaner and more maintainable. Moreover you can reuse functions whenever you need them and if you find a bug inside a function it's a matter of correcting the function to make everything works fine.