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;
}

Is there a reason why you are not using the standard std::list container for this? It implements a double-linked list for you. — Remy Lebeau
– Remy Lebeau, Commented Feb 19, 2021 at 16:49

orlp · Accepted Answer · 2021-02-19 16:53:21Z

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;

answered Feb 19, 2021 at 16:53

orlp

119k39 gold badges226 silver badges324 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

TheWinterSnow Over a year ago

That was it thanks! I knew it had to be something I was glossing over.

Remy Lebeau · Accepted Answer · 2021-02-19 16:59:54Z

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 */ 
    }
}

Collectives™ on Stack Overflow

C++ Inserting elements in doubly linked list logic error

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related