Insert a string into a sorted linked list of strings in C

user_6590795 0
Viewed 64

I'm struggling with this problem: I want to insert a string into a sorted linked list of strings but for some reason it doesn't work. Here is the code:

void insert(node** head, const char* word){

  node* newElem = malloc(sizeof(node));
  newElem->data = malloc(sizeof (char)*(wordLenght+1));
  strcpy(newElem->data, word);

  if (*head == NULL || strcmp(newElem->data, (*head)->data) < 0){
      newElem->next = *head;
      *head = newElem;
      return;
  }

  nodo* cursor = *head;
  while (cursor->next != NULL && strcmp(newElem->data, cursor->data) < 0){
      cursor = cursor->next;
  }

  newElem->next = cursor->next;
  cursor->next = newElem;
}

I've tried with this set of strings

7DJL,-kiF, 8F4r, 7D7d, -D7w, -b7f

and it didn't work. The output should be:

-D7w, -b7f, -kiF, 7D7d, 7DJL, 8F4r

Thank you for your help!

function-definition singly-linked-list c-strings sorting c
1 Answers

I do not know what is wordLenght. But in any case using this name within the function does not make a sense and only makes the function unclear because the name is not defined within the function.

There is no need to split the function into two parts. It makes the function error-prone.

Moreover the condition of the while statement

while (cursor->next != NULL && strcmp(newElem->data, cursor->data) < 0){

is incorrect.

If this expression

strcmp(newElem->data, cursor->data) < 0

evaluates to true you need to interrupt the loop.

Also there is a typo

nodo* cursor = *head;

It seems you mean

node* cursor = *head;

The function can look the following way

int insert( node** head, const char* word )
{
    node *newElem = malloc( sizeof( node ) );
    int success = newElem != NULL;

    if ( success )
    {
        success = ( newElem->data = malloc( strlen( word ) + 1 ) ) != NULL;

        if ( success )
        {
            strcpy( newElem->data, word );

            while ( *head != NULL && !( strcmp( word, ( *head )->data ) < 0 ) )
            {
                head = &( *head )->next;
            }

            newElem->next = *head;
            *head = newElem;
        }
        else
        {
            free( newElem );
        }
    }

    return success;
}

Here is a demonstration program.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node
{
    char *data;
    struct node *next;
} node;

int insert( node** head, const char* word )
{
    node *newElem = malloc( sizeof( node ) );
    int success = newElem != NULL;

    if ( success )
    {
        success = ( newElem->data = malloc( strlen( word ) + 1 ) ) != NULL;

        if ( success )
        {
            strcpy( newElem->data, word );

            while ( *head != NULL && !( strcmp( word, ( *head )->data ) < 0 ) )
            {
                head = &( *head )->next;
            }

            newElem->next = *head;
            *head = newElem;
        }
        else
        {
            free( newElem );
        }
    }

    return success;
}

void display( const node *head )
{
    for ( ; head; head = head->next )
    {
        printf( "\"%s\" -> ", head->data );
    }

    puts( "null" );
}

int main (void) 
{
    node *head = NULL;
    const char * data[] =
    {
        "7DJL", "-kiF", "8F4r", "7D7d", "-D7w", "-b7f"
    };
    const size_t N = sizeof( data ) / sizeof( *data );

    for ( size_t i = 0; i < N; i++ )
    {
        insert( &head, data[i] );
    }

    display( head );
}

The program output is

"-D7w" -> "-b7f" -> "-kiF" -> "7D7d" -> "7DJL" -> "8F4r" -> null
user_28772410
Related