linked list sorted insert

Discussion in 'C Programming' started by Andrew Clark, Jul 10, 2003.

  1. Andrew Clark

    Andrew Clark Guest

    *** post for FREE via your newsreader at post.newsfeed.com ***

    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: sorted linked list insert.

    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) {
    // Your code...

    /* My code */

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

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

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

    comments and advice are welcome.

    andrew


    -----= Posted via Newsfeed.Com, Uncensored Usenet News =-----
    http://www.newsfeed.com - The #1 Newsgroup Service in the World!
    -----== 100,000 Groups! - 19 Servers! - Unlimited Download! =-----
     
    Andrew Clark, Jul 10, 2003
    #1
    1. Advertising

  2. Andrew Clark

    Chris Torek Guest

    In article <Xns93B3D0B54CDA9asdfjkl@208.33.61.211>
    Andrew Clark <> 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) {


    Given that you already copied "*headRef" into a local variable, why
    not use that wherever possible?

    if (curr == NULL || newNode -> data <= curr -> data) {

    > newNode -> next = *headRef;


    newnode -> next = curr;

    > *headRef = newNode;


    (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.
    --
    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.
     
    Chris Torek, Jul 10, 2003
    #2
    1. Advertising

  3. Andrew Clark

    pete Guest

    Chris Torek wrote:

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


    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
     
    pete, Jul 10, 2003
    #3
  4. pete <> wrote:
    > Chris Torek wrote:
    >
    >> 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.

    >
    > 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
     
    Stig Brautaset, Jul 11, 2003
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. massimo

    Sorted Linked List

    massimo, May 24, 2004, in forum: C++
    Replies:
    6
    Views:
    567
    massimo
    May 24, 2004
  2. CR
    Replies:
    5
    Views:
    3,212
    Brian MacBride
    Dec 24, 2003
  3. fool
    Replies:
    14
    Views:
    549
    Barry Schwarz
    Jul 3, 2006
  4. joshd
    Replies:
    12
    Views:
    705
    John Carson
    Oct 2, 2006
  5. SherjilOzair

    Best way to insert sorted in a list

    SherjilOzair, Jun 17, 2011, in forum: Python
    Replies:
    10
    Views:
    1,174
    Vito De Tullio
    Jun 19, 2011
Loading...

Share This Page