... this is my attemot at #6: sorted linked list insert.
6 0x97 SortedInsert()
[BTW, the character with code 0x97 -- not a printing character in
either ASCII or ISO Latin 1 -- was probably stuck in by some
deficient software. I expanded it for posting purposes.]
Write a SortedInsert() function which given a list that is sorted in
increasing order, and a single node, inserts the node into the correct
sorted position in the list. ...
Just as a general background note, inserting into such a list gives
O(n^2) time behavior on "random" data. It is pretty close to
optimal on reverse-sorted data and pretty much "pessimal" on sorted
data. As such, it is suitable only in relatively rare circumstances,
such as when taking input items one at a time from a human and
displaying the results immediately.
That out of the way, and noting that the problem requires that you
use the function signature that appears in your solution:
void SortedInsert (struct node **headRef, struct node *newNode) {
struct node *prev, *curr = *headRef;
if (*headRef == NULL || newNode -> data <= (*headRef) -> data) {
Given that you already copied "*headRef" into a local variable, why
not use that wherever possible?
if (curr == NULL || newNode -> data said:
newNode -> next = *headRef;
newnode -> next = curr;
(but this has to remain *headRef -- you want to change the lvalue
at *headRef, not a copy of that lvalue's value).
} else {
while (curr && curr -> data <= newNode -> data) {
prev = curr;
curr = curr -> next;
}
prev -> next = newNode;
newNode -> next = curr;
}
}
comments and advice are welcome.
This code works and is reasonably clear. It can, however, be
simplified (more than just the *headRef to curr changes above).
Before I get to that, I will also note that you insert an "equal"
item -- one where newNode->data == curr->data, for some node "curr"
-- after all such equal items (probably the right thing to do).
The problem statement never said what *should* happen in such cases;
the most likely alternative to "insert after equal items" is "fail"
(abort, or return an error indication; the latter would of course
require changing the return type of the function). In some other
languages you could even "throw an exception" -- you can even do
this in C by using the bad kind of goto, spelled longjmp(), but I
consider this a bad idea myself.
One of C's unusual features is the ability to take addresses of
local variables, members of structures, and so on. (Many languages
with pointers forbid this sort of thing -- pointers are created
only with "new"-like keywords, and the only other way to obtain a
pointer is to copy an existing, valid pointer.) We can use
this feature to move various tests.
void SortedInsert(struct node **headRef, struct node *newNode) {
struct node **pp, *curr;
The "pointer to pointer" variable pp here is the one we will use
in this way. The first step is to make sure pp is just a copy of
headRef:
pp = headRef;
This guarantees that *pp is the lvalue -- loosely, the variable --
that must change in order to insert something at the front of the
list, whether or not the list is empty.
Next comes the tricky bit:
while ((curr = *pp) != NULL && curr->data <= newNode->data)
pp = &curr->next;
On the very first trip through this loop, *pp is the same as
*headRef, i.e., the value of the variable that heads the list.
We copy this to curr just for convenience (to avoid writing *pp
each time). If this value is NULL, the list is empty and we
must stop, but if it is not NULL, we need to check whether the
new node goes here, or later in the list.
If the new node goes here -- i.e., curr->data > newNode->data --
we stop, with pp == headRef and curr (aka *pp) not NULL. Otherwise,
we set pp to the *address* of curr->next and repeat the loop.
This time through the loop, pp == &((*headRef)->next), so *pp --
which we copy to curr as usual -- is (*headRef)->next. Again,
this can be NULL, or it might be a valid node; if it is a valid
node we must see if the new node goes here, or later. If the
new node goes later, we set pp to &((*headref)->next->next),
and so on down the line.
The crucial bit is that, no matter what, when the loop stops, *pp
is "the pointer that leads to curr" -- either *headRef itself, or
&((*headRef)->a->b->c->...->next) for some chain of "non-head"
nodes a, b, c, ..., however many it takes to get there. Moreover,
*pp is the pointer that *should* point to the new node, because
the new node goes before the node now in "curr", or at the end of
the list, whichever is the case. Note that curr == *pp, too, so
we have that saved.
So, now we just need to do this:
*pp = newNode;
newNode->next = curr;
and the insertion is complete. If curr == NULL, we have put the
node at the end of the list, because now newNode->next == NULL.
If pp == headRef, we have put the new node at the front of the
list. If both of those are true, we have done both at the same
time -- put the new node at the head, and also at the end; the head
and end are the same thing. If, on the other hand, curr != NULL,
then curr is the node that should come after newNode, and we have
made that happen.
So now we can finish off the function with a close brace, but for
compactness, here it is in its entirety:
void SortedInsert(struct node **headRef, struct node *newNode) {
struct node **pp, *curr;
pp = headRef;
while ((curr = *pp) != NULL && curr->data <= newNode->data)
pp = &curr->next;
*pp = newNode;
newNode->next = curr;
}
Some might prefer the loop as a "for" loop, or moving the initialization
for "pp" up into the declaration line, but the essence of the
algorithm is the same.
