C: Creation of ordered list by checking 2 values

Question

Hello,

I'm new to C so be patient with me if you see some really newbie error in my code!

As part of a homework, I need to create an ordered list in order to store some data. What I've done so far is to create the struct which will represent each node of the list (firstNode is a global variable that points to the first node of the list):

typedef struct Node {
    struct Node *next;
    int id;
    int value;
}Node;

Node *firstNode = NULL;

After that I created a function that inserts a new node into the list by checking the values of the nodes. Nodes with smaller values should be before others. So what I did was this:

void addNewNode(int nodeId, int nodeValue) {
    Node *newNode = (Node*) malloc(sizeof(Node));
    Node *temp, *tempPrev;
    newNode->id = nodeId;
    newNode->value = nodeValue;

    if(firstNode == NULL) {
        newNode->next = firstNode;
        firstNode = newNode;
    }
    temp = firstNode;
    tempPrev = NULL;
    while(temp->value < newNode->value) {
        tempPrev = temp;
        temp = temp->next;
    }
    if(tempPrev == NULL) {
        newNode->next = firstNode;
        firstNode = newNode;
    } 
    else {
        tempPrev->next = newNode;
        newNode->next = temp;
    }
}

The problem with the code above is that sometimes the program crashes, but I can't find the error!

Also, what I'm trying to do next is, if some nodes have the same value, then they are ordered according to their id (nodes with smaller IDs come first). How can I do this? I'm really confused!

Answer 1

1.

if(firstNode == NULL) {
        newNode->next = firstNode;
        firstNode = newNode;
        return; // done with inserting the first node...need not continue.
    }

2.

// ensure temp is not null only then access its value.
while(temp && (temp->value < nodeId->value)) {
        tempPrev = temp;
        temp = temp->next;
    }

Answer 2

The program crashes because in the while loop condition, you don't check whether the temp equals to NULL. In other words, if you try to insert a new node with a greater value than all the others already inside the list, temp reaches to the end of the list (so temp equals to NULL) and you try to get the value of that node! So a fix would be:

while(temp!=NULL && temp->value>newNode->value)
{
    ....
}

As for the id of the nodes, you could extend your while loop condition like this:

while(temp!=NULL && (temp->value<newNode->value || (temp->value==newNode->value && temp->id<newNode->id))
{
    ....
}

Also, the first if-statement, where you check whether firstNode is NULL, is not necessary in your case. If it's NULL, the program will not get into the while-loop and will go directly to the first if-statement after the while-loop.

By the way, nice code for a new programmer in C :-)

Answer 3

for one thing, you have nodeID -> value in there. NodeID is an int, so this won't work.

Answer 4

As a method of debugging, I would create a simple test harness. In other words, a test program you write that runs through all the common scenarios you can think of (aka unit testing). Each unit test checks to ensure that it runs properly and generates the expected output. This way, you can be confident that if everything checks ok, you're good to go. If a unit test fails, you know exactly what's broken.

Answer 5

I would suggest constructing a couple of test cases that check your boundary conditions (e.g. add an element to an empty list; add an element that should end up at the front of an existing list; add an element that shold end up at the end of an existing list; add an element that should end up somewhere in the middle of an existing list). Make a "print" function that will print the elements in the list to the console for debug. That will at least help you narrow down what the context of your crash is. One possibility (I don't know how many adds you're doing) is that the program runs out of memory and malloc fails. You can check for that because I think malloc returns NULL if it fails to allocate the requisite memory.

Node *newNode = (Node*) malloc(sizeof(Node)); 
if(newNode == NULL)
{
  printf("Out of Memory!");
  return;
}