can't understand sortedlinklist function

Question

found some questions from the Stanford CS library, and this is the question as follows

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.

I found a interesting solution that i have a hard time understanding

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

can someone explain to me how this works? I understand that curr is set to *pp(headRef), curr is set to *pp in the while loop,then checks if the current node is less than the Node to be inserted to, then it sets pp to the next node of the current one. What trips me up is that when the condition fails and jumps to

*pp = newNode;
newNode -> next = curr;

since curr is reset in the while loop to *pp, how does the newNode get connected by the one behind it?? Or am I totally misreading this solution...

You don't need the curr pointer. Also a for loop instead of a while loop will be more readable, IMHO. Whitespace helps, too. — wildplasser
– wildplasser, Commented Apr 13, 2014 at 9:29
And you don't need the pp, either, since you can use headRef. — wildplasser
– wildplasser, Commented Apr 13, 2014 at 9:43

Dabo · Accepted Answer · 2014-04-13 09:41:51Z

1

pp is pointer to pointer, so in this line pp = &curr->next; you assign pp address of pointer (not the address of next element it self) which holds address of next element, so later, here *pp = newNode; you 'enter' the room where stored address of next element, and replace it with address of newNode.

enter image description here

answered Apr 13, 2014 at 9:41

Dabo

2,3832 gold badges21 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

wildplasser · Accepted Answer · 2014-04-13 10:10:30Z

0

Simplified version:

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

        for ( ; *headRef && (*headRef)->data <= newNode->data; headRef = &(*headRef)->next)
            {;}

           /* When we arrive here, headRef points to the ->next pointer
           ** that points to the node that should come after the newNode
           ** , OR it points to the terminal ->next pointer,
           ** which will be NULL.
           ** In the case of an empty list, *headRef will be NULL, and
           ** the loop is never entered.
           */
        newNode->next = *headRef;
        *headRef = newNode;
}

edited Apr 13, 2014 at 10:10

answered Apr 13, 2014 at 9:48

wildplasser

44.5k9 gold badges72 silver badges116 bronze badges

Comments

Ari · Accepted Answer · 2014-04-13 11:05:38Z

0

You mentioned:

"since curr is reset in the while loop to *pp, how does the newNode get connected by the one behind it?? Or am I totally misreading this solution..."

Actually 'curr' is kept assigned to the (new, updated) pp in the beginning of the loop as you see in the code:

while ((curr = *pp) != NULL && curr->data <= newNode->data)
    pp = &curr->next;

The (cur == *pp) is not only for initiation, it is executed for every loop.. and pp is also kept being progressed to the next item (pp = &curr->next) in the list until the end of the list (*pp == NULL)

answered Apr 13, 2014 at 11:05

Ari

925 bronze badges

Collectives™ on Stack Overflow

can't understand sortedlinklist function

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related