Adding to a sorted linked list

Question

I'm trying to get my program to insert a score into a place within an ordered linked list. It compiles fine but crashes when I launch it. Linked lists aren't exactly my speciality so I'm sure I've made an error somewhere. p[i].score and p[i].name are defined just before this piece of code and the list is initially empty.

struct highScore
{
 char name[10];
 int score;
 struct highScore *next;
};
struct highScore *head,*currentScore,*newScore, *temp;
if(head==NULL)
{
 head = currentScore = newScore;
 currentScore->score = p[i].score;
 strcpy(currentScore->name, p[i].name);
}
else
{
 currentScore = head; 
 while (currentScore->next != NULL)
 {
 while(p[i].score < currentScore->score)
 {
 currentScore = currentScore->next;
 if (currentScore->next->score < p[i].score)
 {
 newScore = (struct highScore *)malloc(sizeof(struct highScore));
 newScore->score = p[i].score;
 strcpy(newScore->name, p[i].name);
 temp = currentScore->next;
 currentScore->next = newScore;
 currentScore = newScore;
 currentScore->next = temp;
 }
 }
 }
}

• hmjd: Can you post struct highScore definition?
• hmjd: Is head initialized somewhere, before it is compared to NULL? Also, how is p[i].name populated?
• makes: This question doesn't have enough information to be answered without guesswork. Try composing a small, complete, compilable program demonstrating your problem. Then it will be easier for others to help.
• Tomas Pruzina: @karoma SO handles spaces badly, please use 4 space for indentation next time (it's in FAQ).

Answer 1

Your current code is kind of a mess (as others noted).

What you need, in pseudocode, is something like this:

new_entry = create_new_entry(data); /* allocate the new stuff */
for (some loop to find where new_entry is to insert)
 ... loop contents ...
insert new_entry;

The tricky part with singly-linked lists is that you can only do an "insert before" operation, which looks like:

new_entry->next = what_new_goes_before;
what_new_goes_after->next = new_entry;

and this requires that there be "something that new_entry goes after". This is where the special case test for:

if (head == NULL)

comes from: if head is NULL, there's no existing entry you could go after. Unfortunately, there's also the case where the new entry goes first, so you need to test for both of these:

if (head == NULL || goes_before(new_entry, head)) {
 /* i.e., there is no head yet, or new_entry goes before head */
 new_entry->next = head;
 head = new_entry;
} else {
 /* there is something for new_entry to go after, so find it */
 for (old_entry = head; !goes_before(new_entry, old_entry);)
 prev = old_entry;
 if ((old_entry = old_entry->next) == NULL)
 break;
 new_entry->next = old_entry;
 prev->next = new_entry;
}

However, there's a very useful trick with pointers-to-pointers in C here. Instead of writing a loop that has to run at least once (to set prev above—note that we know the result of !goes_before() on the first trip), we can have a pointer variable pp that will point to some struct highScore * pointer:

struct highScore **pp, *p;

Initially, we'll have this point to head. As we run through the loop trying to find the item that the new entry goes-before, we'll change it to point to each old-entry's struct highScore * pointer called next:

for (pp = &head; !goes_before(new_entry, p = *pp); pp = &p->next)
 continue;

The loop terminates when new_entry goes before *pp (whose value is now in p), so now we need only set the new entry's next and update *pp:

new_entry->next = p;
*pp = new_entry;

and the whole thing is done in four lines (plus the 5th declaration line).

• torek: Also, you need to decide what to do if the new entry goes in "the same place" as some old entry. The loop above puts it in front, on the theory that "same score, but more recently achieved, means bump the old one down". But maybe you'll want something different.

Answer 2

1. Break your code out into functions. For example, "initialize()", "insert()", "find()" and "delete()" might all be useful functions.

2. Don't use global variables. For example, "*head" and "*currentScore" are probably the only variables you'd even consider making global.

3. Write test programs for every function.

4. Single-step through every test program under the debugger.

IMHO .. PSM

PS: For example:

struct *highScore
insert (struct ** head, struct *highScore newScore)
{
 struct *hiScore currentScore;
 // Assumes "newScore" element is already filled in
 if(*head==NULL)
 {
 *head = newScore;
 newScore->next = NULL;
 return newScore;
 }
 else
 {
 currentScore = *head; 
 while (currentScore->next != NULL)
 {
 ...

• Tomas Pruzina: I generally agree with your points, but I don't see how is it relevant. Also you use too small indentation and while we'r betching about practise, 8(4) char indentation, no more than 3(4) levels in loops(worst case in ()). :-* 4) step can be avoided by writing programs without errors (my teacher would say, ik its BS :D).

Answer 3

1. The line

   head = currentScore = newScore;

   You have not initialized newScore - hence the rest of that if statement is doomed.

2. Are you adding items in order, or is the list supposed to end up in order?