sorting names in a linked list

Question

Hi there, I'm trying to sort names into alphabetical order inside a linked list but am getting a run time error. what have I done wrong here?

#include <iostream>
#include <string>
using namespace std;

struct node{
    string name;
    node *next;
};

node *A;

void addnode(node *&listpointer,string newname){
    node *temp;
    temp = new node;
    if (listpointer == NULL){
        temp->name = newname;
        temp->next = listpointer;
        listpointer = temp;
    }else{
        node *add;
        add = new node;
        while (true){
            if(listpointer->name > newname){
                add->name = newname;
                add->next = listpointer->next;
                break;
            }
            listpointer = listpointer->next;
        }
    }
}

int main(){

    A = NULL;
    string name1 = "bob";
    string name2 = "tod";
    string name3 = "thomas";
    string name4 = "kate";
    string name5 = "alex";
    string name6 = "jimmy";
    addnode(A,name1);
    addnode(A,name2);
    addnode(A,name3);
    addnode(A,name4);
    addnode(A,name5);
    addnode(A,name6);

    while(true){
        if(A == NULL){break;}
        cout<< "name is: " << A->name << endl;
        A = A->next;
    }

    return 0;

}

Answer 1

You're trying to dereference a null pointer in addnode. In the case where listpointer->name > newname is never true, listpointer will eventually get set to NULL, and then attempt to be dereferenced again in the next listpointer->name > newname comparison.

...among other possible logic errors in your code, that is.

Answer 2

I believe the mistake is that you think:

if (listpointer == NULL){
    temp->name = newname;
    temp->next = listpointer;
    listpointer = temp;
}

guarantees that listpointer won't ever be NULL later. However this isn't the case, for example:

void addnode(node *&listpointer,string newname){
   node *temp;
    temp = new node;
    if (listpointer == NULL){
        temp->name = newname;
        temp->next = listpointer;
        listpointer = temp;
    }else{
        node *add;
        add = new node;
        while (true){
            if( (listpointer) == NULL){
            std:cout << "oops (listpointer) == NULL)";
            }

            if(listpointer->name > newname){
                add->name = newname;
                add->next = listpointer->next;
                break;
            }
            listpointer = listpointer->next;
        }
    }
}

Will print out "oops" then segfault as lispointer is NULL and using -> on a NULL will cause a segfault. This is because in the while (true) loop listpointer eventually reaches the end and gets set to NULL. You then get the segfault.

I think a better idea would be to do something like:

bool has_inserted;
while ( listpointer != NULL){
  if(listpointer->name > newname){
     add->name = newname;
     add->next = listpointer->next;
     has_inserted = true;
     break;
  }
  listpointer = listpointer->next;
}
if(has_inserted == false){
//insert at end of list
}

Also this code leaks memory as you don't delete the things you created with new. You may want to run this (and other code) with valgrind to see what I mean.

Answer 3

I did some modifications on your code :

1 - Prevents from memory leak by removing temp from your code.

2 - You have to keep the pointer of 1st element of list. If you lose it you will not be able anymore to add more items nor to print list contents.

3 - The code must analyse if the new item will have to be inserted on the top, middle or end of the list. If at top, the list pointer must be changed to it.

So i fixed that bugs and your code is fine now.

Remember that your main() should be adjusted to not change the list pointer (A) while printing its items. If so, you will lose the control of your list after printing it, and will not be able to access or delete its nodes anymore. If you don't care about it in this test, just forget it.

void addnode(node *&listpointer,string newname){
    node *add,
         *last,
         *current;

    add = new node;
    add->name = newname;

    if (listpointer == NULL){
        add->next = listpointer;
        listpointer = add;
    }else{
        current = listpointer;
        last    = listpointer;
        while (current && current->name < newname){
            last = current;
            current = current->next;
        }

        if (current == listpointer){
            /* Insert before 1st node */
            add->next = listpointer;
            listpointer = add;
        }
        else{
            /* Insert between last and current 
               or at the end of the list */
            last->next = add;
            add->next = current;
        }
    }
}