How to add a new node to a linked list alphabetically-CodePudding

I am trying to build a music library with five songs using a linked list, and each song has three tags, the songName, the Artist and the Genre. So I take users' input and add it to the linked list, alphabetically with its songName. For example, if I have 3 songs, regardless of the artists and the genre, the song names are Alpha, Zebra and Cool time, then the linked list should be in this order: Alpha, Cool time, Zebra.

The following is my code, but it does not add the new node to the right place if the first letter has an ASCII value that is larger than the Head. It only works when the Head is NULL, or when the ASCII values of all other nodes are <= to that of the new node. Thanks a lot for helping.

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

typedef struct node {
  char *artist;
  char *songName;
  char *genre;
  struct node *next;
} Node;

Node *insert (Node * Head, char *art, char *song, char *gen);
void print (Node * Head);

int main() {
  char art[25], song[25], gen[25];
  Node *Head = NULL;
  
  for (int j = 0; j < 5; j  ) {
    printf("Artst --> ");
    gets(art);
    printf("Song name --> ");
    gets(song);
    printf("Genre --> ");
    gets(gen);
    Head = insert (Head, art, song, gen);
  }

  printf("The elements are:");
  print(Head);
}

Node *insert(Node * Head, char *art, char *song, char *gen) {
  Node *newelement;
  newelement = (Node *)malloc(sizeof(Node));

  newelement->artist = malloc(strlen(art)   1);
  strcpy(newelement->artist, art);

  newelement->songName = malloc(strlen(song)   1);
  strcpy(newelement->songName, song);

  newelement->genre = malloc(strlen(gen)   1);
  strcpy(newelement->genre, gen);

  Node *check;
  check = (Node *)malloc(sizeof(Node));

  if (Head == NULL) {
    Head = newelement;
    Head->next = NULL;
  }
  else {
    check = Head;
      
    char this = newelement->songName[0];
    char that = check->songName[0];
      
    //"this" is the value of the first letter of the new songName;
    //"that" is the value of the first letter of the songName we are comparing to;
    //when "this" has a smaller value then that (ex. this is A, and that is B), then this should go before that.

    //if the head of the linked list has a letter that has a greatere ASCII value, then the newelement should be the new head
    if (this <= that) {
      newelement->next = Head;
      Head = newelement;
      return Head;
    }
    else if (this>that) {
      while (check->next != NULL) {
        check = check->next;
        that = check->songName[0];

        if (this <= that)
          break;
      }
    }

    Node *temp = check->next;
    check->next = newelement;
    newelement->next = temp;
  }

  return Head;
}

void print(Node * Head) {
  while (Head != NULL) {
    printf("\n");
    printf("%s\n", Head->artist);
    printf("%s\n", Head->songName);
    printf("%s\n", Head->genre);
    printf("\n");
    Head = Head->next;
  }
}

CodePudding user response：

For starters this memory allocation

check = (Node *)malloc(sizeof(Node));

does not make a sense and produces a memory leak because the allocated memory is not used and is not freed.

In this code snippet

else if (this>that) {
  while (check->next != NULL) {
    check = check->next;
    that = check->songName[0];

    if (this <= that)
      break;
  }
}

Node *temp = check->next;
check->next = newelement;
newelement->next = temp;

the new node with song name less than the song name of the node check is inserted after the node check.

Also the function gets is not safe and is not supported by the C Standard.

Instead use either scanf like for example

scanf( " $[^\n]", art );

or fgets like

fgets( art, sizeof( art ), stdin );
art[ strcspn( art, "\n" ) ] = '\0';

The function can be declared and defined the following way

Node * insert( Node *Head, const char *art, const char *song, const char *gen ) 
{
    Node *newelement = malloc(sizeof( Node ) );

    newelement->artist = malloc( strlen( art )   1);
    strcpy( newelement->artist, art );

    newelement->songName = malloc( strlen( song )   1 );
    strcpy( newelement->songName, song );

    newelement->genre = malloc( strlen( gen )   1 );
    strcpy( newelement->genre, gen );

    if ( Head == NULL || strcmp( song, Head->songName ) < 0 )
    {
        newelement->next = Head;
        Head = newelement;
    }
    else 
    {
        Node *current = Head;
      
        while ( current->next != NULL && !( strcmp( song, current->next->songName ) < 0 ) )
        {
            current = current->next;
        }

        newelement->next = current->next;
        current->next = newelement;
    }

    return Head;
}

Pay attention to that the parameters that are pointers to strings should have the qualifier const.