CODEWITHSUNDEEP
c
Deepak
Deepak

Reputation: 1545

trying to understand code of a linked list insert function

I am not understanding the some part of this function . I wrote some comments on top of the lines where I am not understanding it.

// perform an ordered insertion of an item into a list
boolean insert( List *list, char *new_string )
{
   boolean rc = true;
   Node *newNode = NULL;
   Node *curr;
   Node *prev;

   newNode = (Node *)malloc( sizeof( Node ) );
   newNode->string = new_string;

   curr = list->top;
   prev = NULL;
   // upto here everything is fine

   //from here 
   // what does this does here? curr->string, new_string < 0 
   // and the if and else statements after that
   while ( NULL != curr && strcmp( curr->string, new_string ) < 0 ) 
   {
      prev = curr;
      curr = curr->next;
   }
   if ( prev == NULL ) 
   {
      newNode->next = list->top;
      list->top = newNode;
   } 
   else 
   {
      newNode->next = curr;
      prev->next = newNode;
   }

  // note that we need to have space for the string as well!
   newNode->string = (char *)malloc( strlen( new_string ) + 1 );
   strcpy( newNode->string, new_string );
   // to here I do not understand
   return rc;
}

Upvotes: 0

Views: 58

Answers (2)

Beta
Beta

Reputation: 99084

This loop:

while ( NULL != curr && strcmp( curr->string, new_string ) < 0 )
{
  prev = curr;
  curr = curr->next;
}

means "advance through the list until either curr is NULL (i.e. we've reached the end of the list), or we've gone just pas the point where the new node ought to be inserted".

If we hit that condition on the first node (and therefore prev is still NULL), the new node belongs at the head:

if ( prev == NULL ) 
{
  newNode->next = list->top;
  list->top = newNode;
}

otherwise splice it in where we did hit that condition:

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

EDIT:

P.S. this bit:

newNode->string = (char *)malloc( strlen( new_string ) + 1 );
strcpy( newNode->string, new_string );

copies new_string into the new node, but that shouldn't be mysterious.

Upvotes: 2

dckuehn
dckuehn

Reputation: 2475

while ( NULL != curr && strcmp( curr->string, new_string ) < 0 ) 
{
   prev = curr;
   curr = curr->next;
}

This code block searches your entire list for the first node that is less than the given string. Because at the end of the loop, curr is set to curr-> next; Eventually you'll get to the end of the list when curr->next == null, your loop will end.

The next if-block: if ( prev == NULL ) . handles the case where your loop never runs, or prev is still as it was defined, or NULL.

The associated else block inserts the new node between the previous node and the next node by setting newNode->prev = prev and newNode->curr, but you also need to set prev->next = newNode and curr->prev = newNode.

For more information on strcmp(), please visit: http://www.cplusplus.com/reference/cstring/strcmp/

Key points of strcmp(str1, str2): A zero value indicates that both strings are equal. A value greater than zero indicates that the first character that does not match has a greater value in str1 than in str2; And a value less than zero indicates the opposite.

Upvotes: 2

Related Questions