C++ singly linked list using a classes

Question

I want to create singly linked list (using classes), where in each list there will be: pointer to text,int number, pointer to next list.

I need to implement 3 functions: inserts(which inserts a list into singly linked list and sorts elements with strcmp according to text which is pointed by pointer) removes(int num) which removes first list in which number occurs. print() which prints the whole singly linked list.

I have problem with removes function which gives error in runtime and I have a conjecture where is the problem if ( tmp->next == NULL && tmp->number==num ) { delete tmp; first = NULL; }, but I have no idea why is it so .

Also I am not sure how should I implement sorting into insert function, so if you have any ideas and if you could explain me where in my removes function the error is I would really appreciate it.

Here's the code:

    #include <iostream>
#include <cstdlib>
#include <cstring>

using namespace std;

class list
{
private:
    int number;

    char* word;
    list* next;
public:
    void inserts(int num, char* text);
    void removes(int num);
    void print();
};
list* first;

void list::print() {
    cout <<"This is our list:"<<endl;

    // Temp pointer
    list *tmp = first;

    // No nodes
    if ( tmp == NULL ) {
    cout << "EMPTY list" << endl;
    return;
    }

    // One node in the list
    if ( tmp->next == NULL ) {
    cout <<"NUMBER:\t"<< tmp->number;
    cout <<"\tWORD:\t"<< tmp->word << endl;
    cout <<"--------------------------------"<<endl;

    }
    else {
    // Parse and print the list
    while ( tmp != NULL ){
         cout <<"NUMBER:\t"<< tmp->number;
         cout <<"\tWORD:\t"<< tmp->word << endl;
         cout <<"--------------------------------"<<endl;

        tmp = tmp->next;
    }
}
}

void list::inserts(int num, char* word){
    // Create a new list
    list* newlist = new list; 
    newlist->number=num;

    newlist->word=word;
    newlist->next=NULL;

    // Create a temp pointer
    list *tmp = first;

    if ( tmp != NULL ) {
    // Nodes already present in the list
    // Parse to end of list
    while ( tmp->next != NULL ) {
        tmp = tmp->next;
    }

    // Point the last node to the new node
    tmp->next=newlist;
    }
    else {
    // First node in the list
    first = newlist;
    }
}

void list::removes(int num){
int k = 0;
    list* tmp=first;
    if(tmp==NULL)
        return;
       //Last node of the list

   if ( tmp->next == NULL && tmp->number==num ) {
    delete tmp;
    first = NULL;
    }
    else {
    //Parse thru the nodes
    list* prev;
    prev = new list;
    while ( tmp != NULL )
    {
        if ( tmp->number == num && k == 0)
            first = first->next;
if ( tmp->number == num)
break;
        prev = tmp;

        tmp = tmp->next;
k++;
    } 

    //Adjust the pointers
    prev->next=(tmp->next);
    //Delete the current node
delete tmp;
delete prev;

}
}


int main ()
{
    first->print();
    first->inserts(1200,"endian");
    first->print();
   /* first->inserts(10,"endianness");
    first->inserts(1200,"PEEK");
    first->inserts(1200,"POKE");
    first->inserts(1200,".MIL");
    first->print();*/
first->removes(100);
first->print();
getchar();
}

Answer 1

Get rid of the delete prev; in the last line of the removes() function.

I'm no expert, but by deleting prev you are losing the reference to your first node in the list.

By the way, good comments, made it very easy to read!

Answer 2

When this loop executes:

while ( tmp != NULL )

your tmp pointer will reach the end of the list, and will be NULL when the loop breaks.

So, when you execute :

prev->next=(tmp->next);

your temp pointer does not have a "next" value. Maybe you should maintain another pointer outside of the loop.

Answer 3

In removes, after the loop while ( tmp != NULL ) { … }, tmp is possibly NULL.

But, after that loop, you have these lines:

//Adjust the pointers
prev->next=(tmp->next);

You are dereferencing a NULL pointer, which causes your program to crash.

Replace those lines with these:

//Adjust the pointers
if(tmp)
    prev->next=(tmp->next);

---

Also note: you still have a bug in memory management in the removes routine. You never call delete on the initial value of prev, and you delete a list node that you should keep in certain cases. Instead of what you are doing, initialize it thusly: list* prev=0;, and get rid of delete prev.