473,224 Members | 1,410 Online

it's been a while since i have poseted to this newsgroup, but for a long
time i was not programming at all. but now that i am out of college and
facing the prospect of getting a real job, i need to get back into the
game. anyway, i don't know if some of you know the stanford CS library. i
took the problem set a while back and have recently rediscovered it adn
have been trying to solve the problems (in order). this is my attemot at

6 — SortedInsert()
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. While Push() allocates a new node to add to
the list, SortedInsert() takes an existing node, and just rearranges
pointers to insert it into the list. There are many possible solutions to
this problem.

void SortedInsert(struct node** headRef, struct node* newNode) {

/* My code */

void SortedInsert (struct node **headRef, struct node *newNode) {
struct node *prev, *curr = *headRef;

if (*headRef == NULL || newNode -> data <= (*headRef) -> data) {
} else {
while (curr && curr -> data <= newNode -> data) {
prev = curr;
curr = curr -> next;
}

prev -> next = newNode;
newNode -> next = curr;
}
}

andrew
-----= Posted via Newsfeed.Com, Uncensored Usenet News =-----
http://www.newsfeed.com - The #1 Newsgroup Service in the World!

Nov 13 '05 #1
3 22047
In article <Xn*********************@208.33.61.211>
Andrew Clark <an*****@syr.edu> writes:
... 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) {
not use that wherever possible?

if (curr == NULL || newNode -> data <= curr -> data) {
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;
}
}

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

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
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
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

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;

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.
--
In-Real-Life: Chris Torek, Wind River Systems (BSD engineering)
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://67.40.109.61/torek/index.html (for the moment)
Reading email is like searching for food in the garbage, thanks to spammers.
Nov 13 '05 #2
Chris Torek wrote:
void SortedInsert(struct node **headRef, struct node *newNode) {
struct node **pp, *curr;

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.

I like it the way that you have it there.
If it was in a for loop, then one of the optional parts
would be missing, which I think looks funny.
I like to declare and initialize seperately.

--
pete
Nov 13 '05 #3
pete <pf*****@mindspring.com> wrote:
Chris Torek wrote:
void SortedInsert(struct node **headRef, struct node *newNode) {
struct node **pp, *curr;

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.

I like it the way that you have it there.
If it was in a for loop, then one of the optional parts
would be missing, which I think looks funny.
I like to declare and initialize seperately.

Which part would that be?

for (pp = headRef; (curr = *pp) != NULL && curr->data <= newNode->data;
pp = &curr->next)
;
(But I agree -- i prefer the while() version too.)

Stig
--
brautaset.org
Nov 13 '05 #4

This thread has been closed and replies have been disabled. Please start a new discussion.