Inserting to sorted linked list

Hi all.

Been a long time since I posted here and I'm a bit rusty with my C.
I'm trying to write a function that inserts into a linked list where node->name is in alphabetical order.

This is what I have so far and it seems logical to me but I just can't understand why they are not sorted.

Code:

---

void insertProductNode(char *brand, char *name, unsigned price, unsigned qty, ProductNodeType **head){
  ProductNodeType *node = malloc( sizeof(ProductNodeType) );
  ProductNodeType *iter = *head;

  if( node == NULL ){
      fprintf(stderr, "Error allocating memory. addProductNode()");
      exit(EXIT_FAILURE);
  }

  strncpy( node->brand, brand, PRODUCT_BRAND_MAX );
  strncpy( node->name, name, PRODUCT_NAME_MAX );
  node->qty = qty;
  node->price = price;
  node->nextProduct = NULL;

  if( iter == NULL ){
      *head = node;
  }
  else{
      while( iter != NULL ){
        if( iter->nextProduct == NULL ){
            iter->nextProduct = node;
            break;
        }
        else if ( strcmp( node->name, iter->name ) < 0){
            node->nextProduct = iter->nextProduct;
            iter->nextProduct = node;
            break;
        }
        iter = iter->nextProduct;

      }

  }
}

---

Code:

---

typedef struct productNode
{
  char name[PRODUCT_NAME_MAX + 1];
  char brand[PRODUCT_BRAND_MAX + 1];
  unsigned price;
  unsigned qty;
  struct productNode* nextProduct;
} ProductNodeType;

---

Code:

---

        else if ( strcmp( node->name, iter->name ) < 0){
            node->nextProduct = iter->nextProduct;
            iter->nextProduct = node;
            break;
        }
        iter = iter->nextProduct;

---

Your problem is in the comparison. Since you want to add node's after the iter, you have to insert when node->name should appear after iter->name.

That's a pretty simple fix huh?

After I fixed it I got a nice sorted list:

Code:

---

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

#define PRODUCT_NAME_MAX 100
#define PRODUCT_BRAND_MAX (PRODUCT_NAME_MAX)

typedef struct productNode
{
  char name[PRODUCT_NAME_MAX + 1];
  char brand[PRODUCT_BRAND_MAX + 1];
  unsigned price;
  unsigned qty;
  struct productNode* nextProduct;
} ProductNodeType;

void print(ProductNodeType *head)
{
  while(head != NULL)
  {
      printf("%s %s\n", head->brand, head->name);
      printf("Price:\t$%u.%u\n", head->price / 100, head->price % 100);
      printf("Qty: %u\n", head->qty);
      head = head->nextProduct;
  }
}

void insertProductNode(char *brand, char *name, unsigned price, unsigned qty, ProductNodeType **head){
  ProductNodeType *node = malloc( sizeof(ProductNodeType) );
  ProductNodeType *iter = *head;
 
  if( node == NULL ){
      fprintf(stderr, "Error allocating memory. addProductNode()");
      exit(EXIT_FAILURE);
  }
 
  /* add data to newly created node */
  strncpy( node->brand, brand, PRODUCT_BRAND_MAX );
  strncpy( node->name, name, PRODUCT_NAME_MAX );
  node->qty = qty;
  node->price = price;
  node->nextProduct = NULL;
 
  if( iter == NULL ){
      *head = node;
  }
  else{
      while( iter != NULL ){
        if( iter->nextProduct == NULL ){
            iter->nextProduct = node;
            break;
        }
        else if ( strcmp( node->name, iter->name ) > 0){
            printf("node->name %s\niter->name %s\n\n", node->name, iter->name);
            node->nextProduct = iter->nextProduct;
            iter->nextProduct = node;
            break;
        }
        iter = iter->nextProduct;
 
      }
 
  }
}

int main()
{
  ProductNodeType *head = NULL;

  insertProductNode("Wonder", "bread", 129, 10, &head);
  insertProductNode("Uncle Ray's", "potato chips", 99, 12, &head);
  insertProductNode("Prince", "spaghetti", 240, 15, &head);
  insertProductNode("Kellog", "cereal", 129, 10, &head);

  print(head);
 
  while (head != NULL)
  {
      ProductNodeType *del = head;
      head = head->nextProduct;
      free(del);
      del = NULL;
  } 
  return 0;
}

/*
node->name spaghetti
iter->name bread

node->name cereal
iter->name bread

Wonder bread
Price:        $1.29
Qty: 10
Kellog cereal
Price:        $1.29
Qty: 10
Prince spaghetti
Price:        $2.40
Qty: 15
Uncle Ray's potato chips
Price:        $0.99
Qty: 12
*/

---

C code - 85 lines - codepad

Unless this doesn't fit your expectations somehow?

Thanks but I had already tried that and trying again now I still don't get a sorted list. There must be something I'm missing somewhere else in the program.
I'm loading data from a csv file but I can't see the problem being there either.
This is starting to do my head in!

Code:

---

  FILE *fpStock = NULL;
  char line[LINELENGTH];
  char *name = NULL;
  char *brand = NULL;
  char delim[] = ",";
  unsigned price;
  unsigned qty;

  fpStock = fopen("coins.csv", "r");
  if (fpStock == NULL){
      fprintf(stderr, "%s does not exist. Exiting\n", stockFile);
      exit(EXIT_FAILURE);
  }

  while( fgets( line, LINELENGTH, fpStock ) != NULL ){
      name = strtok( line, delim );

      brand = strtok( NULL, delim );

      price = atoi(strtok( NULL, delim ));

      qty = atoi(strtok( NULL, delim ));

      insertProductNode(brand, name, price, qty, &vm->headProduct);

      vm->totalProducts++;

  }
  fclose(fpStock);

---

Code:

---

Twirl,Cadbury,165,5
Snakes Alive,Allens,300,5
Minties,Allens,140,10
Picnic,Cadbury,200,5
Dairy Milk Chocolate (95g),Cadbury,250,4

---

&vm->headProduct is just a ProductNodeType.

What do you get?

In fact, if I use your function, they are inserted in the same order as the csv file.

Perhaps you meant to sort by brand instead? In fact, why are you making me guess as much as possible? :mad:

I'm not sure what else to provide! I'm guessing here too.
Thanks for your help. I'll keep looking

OK, I'm going to stop thinking so hard.

Revert to what you had when you first posted the thread. Now remove the break statements in your insert function. Report back.

If I remove either of the breaks it seems to just hang (or loop infinitely).
I'm starting to think my logic is off a bit here. I think I've been looking at it for too long.

It took me ten seconds to notice that your code does not handle the case of inserting an item at the start of the list when the list is currently non-empty.
At a guess I'd say that is going to be a problem.

Thanks iMalc. As I thought, I need to go back and start again.

Fixed it for anyone interested

Code:

---

void insertProductNode(char *brand, char *name, unsigned price, unsigned qty, ProductNodeType **head){
  ProductNodeType *node = malloc( sizeof(ProductNodeType) );
  ProductNodeType *current = NULL;
  ProductNodeType *previous = NULL;

  if( node == NULL ){
      fprintf(stderr, "Error allocating memory. addProductNode()");
      exit(EXIT_FAILURE);
  }

  strncpy( node->brand, brand, PRODUCT_BRAND_MAX );
  strncpy( node->name, name, PRODUCT_NAME_MAX );
  node->qty = qty;
  node->price = price;
  node->nextProduct = NULL;


  current = *head;
  previous = NULL;

  while( current != NULL && strcmp( current->name, node->name ) < 0 ){
      previous = current;
      current = current->nextProduct;
  }

  node->nextProduct = current;

  if( previous == NULL ){
      *head = node;
  }
  else{
      previous->nextProduct = node;
  }

}

---

Looks great to me!

It really helps when you have all the cases for what it needs to do written down or memorised :wink:. If you ever do any TDD then you'll get really good at identifying the different cases for any algorithm.