C++ Inserting elements in doubly linked list logic error

Question

I am working on code that takes a list of unsorted elements and sorts them into a doubly linked list. The code works for the most part, elements can be added to both the beginning and end of the list however for some reason that is beyond me if the first element added will stay on the head (the highest in alphabetical order) the address for head and head->next will be the same. This happens for the tail too if the order is reversed. This has something to do with the logic from lines 28 to 50.

The code below is compilable and runable. Any help as to where I am going wrong would be greatly appreciated.

NOTE: No C++ libraries or classes are to be used, this is a roll your own exercise.

#include <iostream>
#include <cstring>

using namespace std;

struct node
{
    char value[15];
    node *next;
    node *prev;
};

void insert(node *&head, node *&tail, char *value){

    if(!head){
        // empty list create new node
        node* nn = new node;
        
        strcpy(nn->value, value);
        
        nn->next = NULL;
        nn->prev = NULL;
        
        head = nn;
        tail = nn;
    }
    else if(strcmp(value, head->value) < 0){
        // smaller than head.  Update head
        node* nn = new node;
        
        strcpy(nn->value, value);
        
        nn->next = head;
        nn->prev = NULL;
        nn->next->prev = head;
        
        head = nn;
    }
    else if(strcmp(value, tail->value) > 0){
        // larger than tail.  Update tail
        node* nn = new node;
        
        strcpy(nn->value, value);
        
        nn->next = NULL;
        nn->prev = tail;
        nn->prev->next = tail;
        
        tail = nn;
    }
    else{ 
        /* TODO: insert in the middle of the list */ 
    }
}

void printlinkedList(node *ll){
    node *curr = ll;

    while(curr){
        cout << "Value: " << curr->value << "\t";
        cout << "curr: " << curr << "\t";
        cout << "curr->prev " << curr->prev << "\n";
        curr = curr->prev;
    }
}

int main(){

    // Test code
    node *head = NULL;
    node *tail = NULL;

    insert(head, tail, (char*)"aa");
    insert(head, tail, (char*)"bb");
    insert(head, tail, (char*)"cc");
    insert(head, tail, (char*)"dd");

    cout << "\nhead:\t\t" << head << "\n";
    cout << "head->prev:\t" << head->prev << "\n";
    cout << "head->next:\t" << head->next << "\n\n";

    cout << "tail:\t\t" << tail << "\n";
    cout << "tail->prev:\t" << tail->prev << "\n";
    cout << "tail->next:\t" << tail->next << "\n\n\n";

    cout << "Linked List printed in reverse order: \n";
    printlinkedList(tail);

    return 0;
}

Answer 1

Your insert() logic is flawed.

When the list is empty, you are fine.

But when inserting in front of head, you are setting nn->next correctly to point at the old head, but you are then setting the old head's prev to point at the old head (ie, to itself) rather then at the new nn.

And when inserting after tail, you are setting nn->prev correctly to point at the old tail, but you are then setting the old tail's next to point at the old tail (ie, to itself) rather than at the new nn.

This should fix it:

void insert(node *&head, node *&tail, char *value) {

    node* nn = new node;
    strncpy(nn->value, value, 15);
    nn->next = NULL;
    nn->prev = NULL;

    if (!head) {
        // empty list create new node
        
        head = tail = nn;
    }
    else if (strcmp(value, head->value) < 0) {
        // smaller than head.  Update head

        nn->next = head;
        head->prev = nn;
        head = nn;
    }
    else if (strcmp(value, tail->value) > 0) {
        // larger than tail.  Update tail
        
        nn->prev = tail;
        tail->next = nn;        
        tail = nn;
    }
    else { 
        /* TODO: insert in the middle of the list */ 
    }
}

Answer 2

This:

    nn->next = head;
    nn->prev = NULL;
    nn->next->prev = head;

should be:

    nn->next = head;
    nn->prev = NULL;
    nn->next->prev = nn;

And similarly this:

    nn->next = NULL;
    nn->prev = tail;
    nn->prev->next = tail;

should be:

    nn->next = NULL;
    nn->prev = tail;
    nn->prev->next = nn;