List implementation does not sum lists correctly

Question

I am trying to dig into data structures in C++. Therefore I am learning how to write a list. Everything seemed to be working just fine until it came to overloading sum operator +. For two given lists it sums two of the highest values of the lists.

Here is .h file:

typedef struct rob{
    int value;
    struct rob* next;
}element;

class list{
public:
    friend list& operator+(list&,list&);
    friend void merge(list& x,list& y);

    void show();
    bool search(int x);
    void append(int x);
    bool sortAppend(int x);
    list& operator--(int);

    bool empty() { return (inf.head==nullptr);}
    void clear() { inf.head = nullptr; }
    list() { inf.head = inf.tail = nullptr; }
    ~list() { while(!empty()) { (*this)--;}}

private:
    typedef struct{
        element* head;
        element* tail;
    }info;

    info inf;
};

I know that in an .h file the typedef may seem a bit C-like, but the header design is copied from the book that I am learning from. I am trying to crack the methods by my own though using authors ideas.

---

And relevant function definitions:

#include "list.h"
bool list::sortAppend(int x){

element* newElem = new element;
newElem->value = x;
if (empty()){
    inf.head=inf.tail=newElem;
    newElem->next=nullptr;
    return true;
}
else if ( (newElem->value) < (inf.head->value) ){ 
    newElem->next=inf.head;
    inf.head=newElem;
    return true;
}
else if ( (newElem->value) > (inf.tail->value) ) {
    newElem->next=nullptr;
    inf.tail->next=newElem;
    return true;
}
element* tempHead = inf.head;
while(tempHead!=inf.tail){

    if ( (newElem->value) < (tempHead->next)->value) {
           newElem->next = (tempHead->next);
           tempHead->next = newElem;
           return true;
    }
    else{
    tempHead = tempHead->next;
    }   
}
return false;
}

list& operator+(list& X, list& Y){
    list* tempListArr[2] = {&X, &Y};
    list* tempList = new list;
    for(const list* i: tempListArr)
    {
        element* tempHead = (i->inf).head;
        while(tempHead!= nullptr){
            tempList->sortAppend(tempHead->value);
            tempHead = tempHead->next;
            }   
            tempList->show();
            std::cout << "--\n";
    }
    return *tempList;
}

For given list containing values:

#include <iostream>
#include "list.cpp"

int main(){

    list myList;
    myList.sortAppend(5);
    myList.sortAppend(2);
    myList.sortAppend(4);
    list myList2;
    myList2.sortAppend(21);
    list myList3;

    myList3 = myList + myList2;

    return 0;

}

Could anyone point me where I made a mistake? I am stuck for a few hours now and I don't know what goes wrong.

Many thanks in advance!

---

FOLLOW UP:

The sortAppend method surely works. It does create a sorted list as desired. There must have been something wrong with the + operator definition itself though I have tried, instead of range loop, using for loop for one iteration and still I got a list of two values only.

Answer 1

You are simply not setting inf.tail to the new tail in

else if ((newElem->value) > (inf.tail->value)) {
    newElem->next = nullptr;
    inf.tail->next = newElem;
    inf.tail = newElem; // <-- missing!
    return true;
}

You should - at least - change the signature of operator+ to return a list instead of a list reference and return a local object instead of an unowned heap object (which is a memory leak). If you do so you will have to write a copy constructor and copy assignment operator too.

Answer 2

Given your code,

list myListWierd;
myListWierd.sortAppend(2);
myListWierd.sortAppend(4);
myListWierd.sortAppend(5);
myListWierd.show();

shows

2
5

so the sortAppend does not work.

The trouble is around updating either the tail, since operator + relies on using the tail.

I could sort the code out for you and make it work; indeed Andreas' answer does this. But for now, notice you have assumed a function works, but I found a case it doesn't work for by looking at the moving parts - a list we created, that we then try to re-create in a different order. As a general rule, try all the parts in a function that goes wrong, one at a time, maybe as a unit test.

Rather than fixing this, for now, let's make a couple of suggestions.

First, the destructor does nothing, other than walk pointers (using empty which uses head and not tail - so head needs setting as said before)

~list() { while (!empty()) { (*this)--; } }

If you don't want leaks you need to give this more thought.

Next,

list& operator+(list&, list&)

creates a pointer and returns its contents. This is a BAD IDEA. NEVER DO THIS.

For now, change the signature to

list operator+(list&, list&);

and just return a list:

list operator+(list& X, list& Y) {
    list* tempListArr[2] = { &X, &Y };
    list tempList;//copy it over to the calling vode otherwise DANGER
    for (const list* i : tempListArr)
    {
        element* tempHead = (i->inf).head;
        while (tempHead != nullptr) {
            tempList.sortAppend(tempHead->value);
            std::cout << "Adding " << tempHead->value << '\n';
            tempHead = tempHead->next;
        }
        tempList.show();
        std::cout << "--\n";
    }
    return tempList;
}