CODEWITHSUNDEEP
c++
vadim_v
vadim_v

Reputation: 113

Doubly linked list issue - Items are included but do not appear

I am trying to make a doubly linked list as an exercise and I have come across some strange behavior - if I try to use insert_before in the middle of the list, as can be seen with trooper3 and trooper4, trooper4 does not show up when I try and go through all the elements from the beginning to the end. Iterating in reverse order displays that all of the elements are indeed there. I should note that I am only learning c++ and likely miss something.

I ran the code through gdb several times and observed the following: the next and previous pointers are only updated during the second for loop. When I try and iterate from the beginning to the end the next pointer of trooper2 points straight to trooper3.

#include<cstdio>

struct Element{
    Element* next{};
    Element* previous{};
    void insert_after(Element* new_element) {
        new_element->previous = this;
        new_element->next = this->next;
        this->next = new_element;   
    }
    void insert_before(Element* new_element) {
        new_element->previous = this->previous;
        new_element->next = this;
        this->previous = new_element;
    }
    char prefix[2];
    short operating_number;
};

int main() {
    Element trooper1, trooper2, trooper3, trooper4, trooper5;
    trooper1.prefix[0] = 'T';
    trooper1.prefix[1] = 'K';
    trooper1.operating_number = 421;
    trooper1.insert_before(&trooper5);
    trooper5.prefix[0] = 'X';
    trooper5.prefix[1] = 'X';
    trooper5.operating_number = 6767;
    trooper1.insert_after(&trooper2);
    trooper2.prefix[0] = 'F';
    trooper2.prefix[1] = 'N';
    trooper2.operating_number = 2187;
    trooper2.insert_after(&trooper3);
    trooper3.prefix[0] = 'L';
    trooper3.prefix[1] = 'S';
    trooper3.operating_number = 005;
    trooper3.insert_before(&trooper4);
    trooper4.prefix[0] = 'Y';
    trooper4.prefix[1] = 'Q';
    trooper4.operating_number = 768;

    printf("going forward\n");
    for (Element *cursor = &trooper5; cursor; cursor = cursor->next) {
        printf("stormtrooper %c%c-%d\n",
                cursor->prefix[0],
                cursor->prefix[1],
                cursor->operating_number);
    }
    printf("going back\n");
    for (Element *cursor = &trooper3; cursor; cursor = cursor->previous) {
        printf("stormtrooper %c%c-%d\n",
                cursor->prefix[0],
                cursor->prefix[1],
                cursor->operating_number);
    }
}

So, the actual output is

going forward
stormtrooper XX-6767
stormtrooper TK-421
stormtrooper FN-2187
stormtrooper LS-5
going back
stormtrooper LS-5
stormtrooper YQ-768
stormtrooper FN-2187
stormtrooper TK-421
stormtrooper XX-6767

While the section right after going forward should be

stormtrooper XX-6767
stormtrooper TK-421
stormtrooper FN-2187
stormtrooper YQ-768
stormtrooper LS-5

UPDATE I modified my code according to the suggestion and now the methods look like:

    void insert_after(Element* new_element) {
        new_element->previous = this;
        new_element->next = this->next;
        this->next->previous = new_element;
        this->next = new_element;   
    }
    void insert_before(Element* new_element) {
        new_element->previous = this->previous;
        new_element->next = this;
        this->previous->next = new_element;
        this->previous = new_element;
    }

which completely solved the problem.

Upvotes: 0

Views: 55

Answers (1)

Fareanor
Fareanor

Reputation: 6805

This is because you forgot one link, you make only 3 links when you have to make 4.

See below what you missed:

void insert_after(Element* new_element) {
    new_element->previous = this;
    new_element->next = this->next;
    this->next->previous = new_element; // You missed it
    this->next = new_element;   
}
void insert_before(Element* new_element) {
    new_element->previous = this->previous;
    new_element->next = this;
    this->previous->next = new_element; // You missed it
    this->previous = new_element;
}

EDIT:

I forgot to mention that this solves the issue about elements that "disappeared".
But... Your functions don't handle the special cases where the list is empty or where it contains only one element. Accessing an unallocated element (or an out-of-range element) is Undefined Behaviour and you will probably get a segmentation fault at some point.

Upvotes: 4

Related Questions