C++ Doubly linked list adding node in alphabetical order and value

Question

My task is a create doubly linked list and sort them according to their data, if new written node's data is equal to the one of the nodes' data in my doubly linked list, i should sort them in a alphabetical order but I am stuck in the function strcmp(temp->name, newnode->name), For example, I am trying to check if these values entered in order

Christian 250
Tom 200
Alex 250

My sorted doubly linked list give the output as

Alex 250
Christian 250
Tom 200

Here is example of my code

   struct node {
    int data;
    string name;
    node* left;
    node* right;

    node(int i = 0, string s = "", node* l = nullptr, node* r = nullptr) : data(i), name(s), left(l), right(r) {}
};

struct node* head = NULL;
struct node* tail = NULL;

at the top of the program

void insert(int newdata, string name)  // Used for insertion at the end of the linked list and make 
{                                      // the connection for each of the node
    node* newnode = new node();
    node* nodehead = head;
    newnode->data = newdata;
    newnode->name = name;
    newnode->right = NULL;

    if( head == NULL)
    {
        newnode -> left = NULL;
        head = tail = newnode;
    }
    else 
    {
        while (nodehead->right != NULL)
        {
            nodehead = nodehead->right;     
        }
            nodehead->right = newnode; // make the connection for each of them
            newnode->left = nodehead;
            tail = newnode; // and newly created node is our tail

            sorting(newnode); // then go the function to sort them 
    }
   
    cout << "New node is added " << newnode->name << " " << newnode->data << endl;
}

then sort them based on their comparison of their data and if they are equal i should check based on their alphabetical order

 void sorting( node *  &newnode) // ı call sorting function in the insertion function
    {
        node* temp = head;
        node* temp2 = newnode;
    
        int numtemp;
    
        while (temp != nullptr)
        {
            node* temp2 = temp->right;
            while (temp2 != nullptr)
            {       
                if (temp2->data > temp->data) // comparison of their data if newnode's data is larger 
                {
                    string strtemp = "";
                    numtemp = temp->data; // Change their number
                    temp->data = temp2->data;
                    temp2->data = numtemp;
    
                    strtemp = temp->name; // Change their name
                    temp->name = temp2->name;
                    temp2->name = strtemp;
                }
                else if (temp2->data = temp->data) // if newly data is equal to linked list data
                {
                    int ret;
                    ret =  strcmp(temp2->name, temp->name); // i tried to check their string comparison but it did not work
                }
                temp2 = temp2->right;
            }
            temp = temp->right;
        }        
    }

`ret = strcmp(temp2->name, temp->name);` since you are using std::string you compare with `==` or `!=` ... [https://en.cppreference.com/w/cpp/string/basic_string/operator_cmp](https://en.cppreference.com/w/cpp/string/basic_string/operator_cmp) — drescherjm, Jul 16 '20 at 18:29
It isn't clear to me why there are two functions here. You have the tuple of data (number and string). Find where those belong in the list, allocate a new node, wedge it into that position, and be done with it. The list will always be "sorted" because that's how it was built in the first place. — WhozCraig, Jul 16 '20 at 18:34
@drescherjm sorry ı dont get your point, firstly what std::string means and second how can i use strcmp in this case — Razbolt, Jul 16 '20 at 18:35
@Razbolt If you do not know what std::string is then why are you using it?! — Vlad from Moscow, Jul 16 '20 at 18:37
`strcmp()` is for c-strings (char* ) not `std::string`. There is more information here: [https://stackoverflow.com/questions/5492485/strcmp-or-stringcompare](https://stackoverflow.com/questions/5492485/strcmp-or-stringcompare) — drescherjm, Jul 16 '20 at 18:37
@WhozCraig i can not find any other find to sort the datas based on their values, and then their names — Razbolt, Jul 16 '20 at 18:37
@drescherjm okay ı see so how can ı compare each of them char ? — Razbolt, Jul 16 '20 at 18:41
`if (temp2->name > temp->name) { // do something when temp2->name is greater } else { // do something when temp->name is greater or equal }` — drescherjm, Jul 16 '20 at 18:43
@drescherjm ı tried like u say but aprreantly something goes wrong, it changes the whole linked list as same value 'code 'else if (temp2->data = temp->data) { if(temp2->name > temp->name ) { string strtemp = ""; strtemp = temp->name; // name change temp->name = temp2->name; temp2->name = strtemp; } } 'code' — Razbolt, Jul 16 '20 at 19:03
`else if (temp2->data = temp->data) ` assigns data, is doesn't compares: use `==`. — Manuel, Jul 16 '20 at 19:17

Kenny Ostrom · Answer 1 · 2020-07-17T01:45:08.143

I'd recommend that you define a comparison on the node itself, and use that in sorting. Keep in mind that if you are comparing through pointers, you'll need to dereference (compare the nodes, not the pointers).

The standard library already has a way to do comparison based on multiple terms. https://en.cppreference.com/w/cpp/utility/tuple/tie

using std::tie ensures that you meet https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings

I am, of course, assuming that std::string's comparison meets your need for alphabetical. If that's not the case, this may need a minor tweek.

#include <string>
#include <iostream>

struct node {
    int data;
    std::string name;
    node* left;
    node* right;

    node(int i = 0, std::string s = "", node* l = nullptr, node* r = nullptr) 
        : data(i), name(s), left(l), right(r) 
    {}

    bool operator< (const node & rhs) {
        return std::tie(data, name) < std::tie(rhs.data, rhs.name);
    }
};

int main(){
    // simplistic demo
    node a { 21, "green" };
    node b { 21, "yellow" };
    node * p1 = &a;
    node * p2 = &b;
    bool less = (*p1) < (*p2);
    if (p1->data == p2->data) {
        if (*p1 < *p2) {
            std::cout << p1->name << " < " << p2->name << std::endl;
        } else {
            std::cout << p1->name << " >= " << p2->name << std::endl;
        }
    }
}

Pretty sure this is a homework assignment and the student is not allowed to use those standard library utility to complete this assignment easily. — MPops, Jul 16 '20 at 19:07
If someone isn't allowed to use the right library features, they are ALWAYS better off using the right library features, then retrofitting their own versions on the working code. Trying to fix bugs in your comparison is a lot easier when you already know everything else works. — Kenny Ostrom, Jul 16 '20 at 19:08
Thanks for your reply, ı should make the comparsion in a lots of nodes so ı can not figure out how to manipulate these example as huge link list — Razbolt, Jul 16 '20 at 19:09
@MPops yes this is assigment and ı should find another way of comparing strings — Razbolt, Jul 16 '20 at 19:10

Razbolt · Answer 2 · 2020-07-16T19:19:13.423

ı basically add in the else if part if the values are same and change names but appreantly it changes whole list of numbers

void sorting( node *  &newnode) 
{

    node* temp = head;
    node* temp2 = newnode;

    int numtemp;


    while (temp != nullptr)
    {
        node* temp2 = temp->right;
        while (temp2 != nullptr)
        {

            if (temp2->data > temp->data)
            {
                string strtemp = "";
                numtemp = temp->data; // num change
                temp->data = temp2->data;
                temp2->data = numtemp;

                strtemp = temp->name; // name change
                temp->name = temp2->name;
                temp2->name = strtemp;

            }
            else if (temp2->data == temp->data) // here is the change 
            {
               if(temp2->name > temp->name ) // make comparison but im not sure wheteris logical or not 
               {
                   string strtemp = "";
                   strtemp = temp->name; // name change
                   temp->name = temp2->name;
                   temp2->name = strtemp;
               
               }
                
                 
                
            }

            temp2 = temp2->right;
        }

        temp = temp->right;
    }

   

}

`else if (temp2->data = temp->data)` assigns data, is doesn't compares: use `==`. `else if (temp2->data == temp->data)` — Manuel, Jul 16 '20 at 19:18
@Manuel yes ı accidently wrote like this i changed it thanks but it still did not make any list of alphabetical order — Razbolt, Jul 16 '20 at 19:20

score 0 · Accepted Answer · answered Jul 16 '20 at 19:55

0

Your comparison operator is bad:

              if(temp2->name < temp->name ) // make comparison but im not sure wheteris logical or not 
               {
                   string strtemp = "";
                   strtemp = temp->name; // name change
                   temp->name = temp2->name;
                   temp2->name = strtemp;
               
               }

Should be <.

answered Jul 16 '20 at 19:55

Manuel

2,526
1
13
17

Thanks buddy, the reason is you add < is reason of when checking these condition it takes the ASCII table values ? – Razbolt Jul 16 '20 at 21:49
@Razbolt the ordering is done [lexicographically](https://en.cppreference.com/w/cpp/string/basic_string/compare). – Manuel Jul 16 '20 at 21:56

C++ Doubly linked list adding node in alphabetical order and value

3 Answers3