Insert a new node in an ordered linked list in C++

Question

I am writing some code in visual studio with c++, it's an ordered linked list but I am having a bit of trouble with the pointers.

I have three different methods / functions that carry out this task.

/*
 * insert_head: Insert a node at the beginning of the list.
*/
book *inserta_head(book *head, book *newNode){
    newNode->next = head; 
    return newNode;
} 

/*
 * insert_after: Insert a new node after another one.
*/
void insert_after(book *node, book *newNode){
    newNode->next = node->next;
    node->next = newNode;
} 

/*
 * insert: Adds a new node (ordered by code) to the list.         
*/
void insert(book* head, int code, char name[40], char lastName[40], char title[40], int year, int lend) {
    book* newNode = crear_libro(code, name, lastName, title, year, lend);
    book* aux = head;

    // If the list is empty.
    if (head == NULL){
       head = insert_head(head, newNode); 
    } else {
        // If the new node goes before the head.
        if (aux->code > newNode->code){
            head = insert_head(head,newNode);
        } else { 
            while (aux != nullptr && aux->code < newNode->code)
                aux = aux->next;
            // Verify the code isn't repeated
            if (aux != nullptr && aux->code == newNode->code){
                printf("Error: Verify the code. \n");
            } else {
                insert_after(aux,newNode);
            } 
        } 
    } 
}

I've tried running the code. Every time I try to print the list it says it's empty. I've checked my printing method and the method that creates nodes, both of them are working so I'm pretty sure it is related to the pointers but I can't find the error.

As an alternative to what you are doing, [see if this answer helps you out any](https://stackoverflow.com/a/59779376/4581301). It will reduce insert to one very short function. — user4581301, Aug 20 '20 at 21:04

score 4 · Accepted Answer · answered Aug 20 '20 at 21:03

Your insert function changes the head pointer. But that pointer is a copy of the head pointer you called the function with. So the head pointer outside the insert function is unchanged. That's why nothing gets added to the list.

One simple fix is to make the head parameter a reference.

void insert(book*& head, int code, ...

score 1 · Answer 2 · answered Aug 20 '20 at 21:05

The problem is how you handle the head.

After this line:

head = insert_head(head, newNode);

head in the function should be correct (double check with a debugger). However, the head in the caller will remain unchanged. This is because you don't change the data in the existing head, but you create a new one.

A simple fix is to take the pointer to the pointer to head. book** head This way you can change the pointer in the caller as well (after fixing all the compilation errors).

Insert a new node in an ordered linked list in C++

2 Answers2