Linked list insertion doesn't work as expected

Question

I'm writing a function that places new nodes alphabetically into a linked list structure by sorting them by the name field. Here is my program, intended to test that it can successfully insert a new node into an existing structure:

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

#define MAX_NAME_LENGTH 100
#define MAX_JOB_LENGTH 100

struct Employee
{
    /* Employee details */
    char name[MAX_NAME_LENGTH+1]; /* name string */
    char sex; /* sex identifier, either ’M’ or ’F’ */
    int age; /* age */
    char job[MAX_JOB_LENGTH+1]; /* job string */
    /* pointers to previous and next employee structures in the linked list
     (for if you use a linked list instead of an array) */
    struct Employee *prev, *next;
};

void place_alpha(struct Employee *new, struct Employee **root);

int main(){
    struct Employee *a;
    struct Employee *c;
    struct Employee *b;
    a = malloc(sizeof(struct Employee));
    c = malloc(sizeof(struct Employee));
    b = malloc(sizeof(struct Employee));

    strcpy(a->name, "A");
    a->sex = 'F';
    a->age = 42;
    strcpy(a->job, "Optician");
    a->prev = NULL;
    a->next = c;

    strcpy(c->name, "C");
    c->sex = 'F';
    c->age = 22;
    strcpy(c->job, "Nurse");
    c->prev = a;
    c->next = NULL;

    strcpy(b->name, "B");
    b->sex = 'M';
    b->age = 34;
    strcpy(b->job, "Rockstar");
    b->prev = NULL;
    b->next = NULL;

    place_alpha(b, &a);

    if(a->prev == NULL)
    {
        printf("a->prev is correct\n");
    }else{
        printf("a->prev is INCORRECT\n");
    }

    if(a->next == b)
    {
        printf("a->next is correct\n");
    }else{
        printf("a->next is INCORRECT");
    }

    if(b->prev == a)
    {
        printf("b->prev is correct\n");
    }else{
        printf("b->prev is INCORRECT\n");
    }

    if(b->next == c)
    {
        printf("b->next is correct\n");
    }else{
        printf("b->next is INCORRECT\n");
    }

    if(c->prev == b)
    {
        printf("c->prev is correct\n");
    }else{
        printf("c->prev is INCORRECT\n");
    }

    if(c->next == NULL)
    {
        printf("c->next is correct\n");
    }else{
        printf("c->next is INCORRECT\n");
    }
}

void place_alpha(struct Employee *new, struct Employee **root) //Places a new node new into the database structure whose root is root.
{
    if(*root==NULL) //If there is no database yet.
    {
        *root = new;
        (*root)->prev = NULL;
        (*root)->next = NULL;
    }
    else
    {
        if(strcmp(new->name, (*root)->name)<=0) // if the new node comes before root alphabetically
        {
            new->next = *root;
            new->prev = (*root)->prev;
            if((*root)->prev != NULL)
            {
                (*root)->prev->next = new;
            }
            (*root)->prev = new;

            *root = new;
            return;
        }
        else if((*root)->next == NULL) // If the next node is NULL (we've reached the end of the database so new has to go here.
        {
            new->prev = *root;
            new->next = NULL;
            (*root)->next = new;
            return;
        }
        else if(strcmp(new->name, (*root)->name)>0) // If the new node comes after root alphabetically
        {
            place_alpha(new, &(*root)->next);
            return;
        }
    }
}

Sadly, the program is unsuccessful, as showcased by the output:

a->prev is correct
a->next is correct
b->prev is INCORRECT
b->next is correct
c->prev is INCORRECT
c->next is correct
Program ended with exit code: 0

I can't figure out why, as I've clearly set b->next to c and c->prev to b.

Answer 1

This was tricky: there is a subtile bug in your place_alpha() function: you update *root even if it is not the root node of the list. This causes the pointer b to be updated erroneously. place_alpha() should only be called with a pointer to the actual root node.

I modified your code to make it more readable and reliable:

• I wrote a function to create a new node
• I protected the string copies from overflow using calloc() and strncat(). Read about these functions in the manual.
• I use place_alpha() to insert all 3 nodes into the list in the same order you do.
• I use newp instead of new to avoid C++ keywords in C code.

Note that place_alpha() must be called with a pointer to the head pointer of the list, if you pass a pointer to an intermediary node, chaining back along the prev links would locate the first node, but if the new employee should be inserted at the head of the list, you would not have the address of the root node to update in the caller's scope. This is the reason many programmers prefer to use a specific structure for the list head.

Here is the updated code:

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

#define MAX_NAME_LENGTH 100
#define MAX_JOB_LENGTH  100

struct Employee {
    /* Employee details */
    char name[MAX_NAME_LENGTH + 1]; /* name string */
    char sex; /* sex identifier, either 'M' or 'F' */
    int age; /* age */
    char job[MAX_JOB_LENGTH + 1]; /* job string */
    /* pointers to previous and next employee structures in the linked list
       (for if you use a linked list instead of an array) */
    struct Employee *prev, *next;
};

void place_alpha(struct Employee *new, struct Employee **root);

struct Employee *new_employee(const char *name, char sex, int age, const char *job) {
    struct Employee *newp = calloc(1, sizeof(*newp));
    if (!newp) {
        fprintf(stderr, "cannot allocate employee\n");
        exit(1);
    }
    strncat(newp->name, name, MAX_NAME_LENGTH);
    newp->sex = sex;
    newp->age = age;
    strncat(newp->job, job, MAX_JOB_LENGTH);
    newp->next = newp->prev = NULL;
    return newp;
}

int main(void) {
    struct Employee *list = NULL;
    struct Employee *a = new_employee("A", 'F', 42, "Optician");
    struct Employee *b = new_employee("B", 'M', 34, "Rockstar");
    struct Employee *c = new_employee("C", 'F', 22, "Nurse");

    place_alpha(a, &list);
    place_alpha(c, &list);
    place_alpha(b, &list);

    if (a->prev == NULL) {
        printf("a->prev is correct\n");
    } else {
        printf("a->prev is INCORRECT\n");
    }
    if (a->next == b) {
        printf("a->next is correct\n");
    } else {
        printf("a->next is INCORRECT");
    }
    if (b->prev == a) {
        printf("b->prev is correct\n");
    } else {
        printf("b->prev is INCORRECT\n");
    }
    if (b->next == c) {
        printf("b->next is correct\n");
    } else {
        printf("b->next is INCORRECT\n");
    }
    if (c->prev == b) {
        printf("c->prev is correct\n");
    } else {
        printf("c->prev is INCORRECT\n");
    }
    if (c->next == NULL) {
        printf("c->next is correct\n");
    } else {
        printf("c->next is INCORRECT\n");
    }
    return 0;
}

void place_alpha(struct Employee *newp, struct Employee **root) {
    // Insert a new node newp into the database structure whose root is root.
    struct Employee *ep;

    if (*root == NULL) { // if there is no database yet.
        newp->next = newp->prev = NULL;
        *root = newp;
        return;
    }
    if ((*root)->prev) {
        // invalid call, should only pass the root node address
        fprintf(stderr, "invalid call: place_alpha must take a pointer to the root node\n");
        return;
    }
    if (strcmp(newp->name, (*root)->name) <= 0) {
        // if the new node comes before root alphabetically
        newp->next = *root;
        newp->prev = NULL;
        newp->next->prev = newp;
        *root = newp;
        return;
    }
    for (ep = *root;; ep = ep->next) {
        if (ep->next == NULL) {
            // If the next node is NULL, we've reached the end of the list
            // so newp has to go here.
            newp->prev = ep;
            newp->next = NULL;
            newp->prev->next = newp;
            return;
        }
        if (strcmp(newp->name, ep->next->name) <= 0) {
            // The new node comes between ep and ep->next alphabetically
            newp->prev = ep;
            newp->next = ep->next;
            newp->prev->next = newp->next->prev = newp;
            return;
        }
    }
}

EDIT: place_alpha was a bit redundant, so I cleaned it and got a much simpler version:

void place_alpha(struct Employee *newp, struct Employee **root) {
    //Places a new node newp into the database structure whose root is root.
    struct Employee **link = root;
    struct Employee *last = NULL;

    while (*link && strcmp(newp->name, (*link)->name) > 0) {
        last = *link;
        link = &last->next;
    }
    newp->prev = last;
    newp->next = *link;
    if (newp->next) {
        newp->next->prev = newp;
    }
    *link = newp;
}