How can I make an ordered linked list?

Question

I have to make an ordered linked list by organization name and then by size. I have to compare the organization name first and then I have to sort them by size if they are in the same organization. I have added the code that I have so far.

struct tshirt 
{
    char org_name[ORG_NAME_LEN+1];
    char size[SIZE_LEN+1];
    double price;
    int quantity;
    struct tshirt *next;
};
struct tshirt * add_to_inventory(struct tshirt *inventory)
{ 
    struct tshirt *new_node = malloc(sizeof(struct tshirt));

    printf("Enter your student organization name: ");
    read_line(new_org_name, ORG_NAME_LEN);
    printf("Enter the shirt size: ");
    scanf("%s", new_size);
    strcpy(new_node -> org_name, new_org_name);
    strcpy(new_node -> size, new_size);
    for (a = inventory; a != NULL; a = a -> next) 
    {
        if (strcmp (a -> org_name, new_org_name) == 0)
        {
            if (strcmp (a -> size, new_size) == 0) 
            {
                printf("T-shirt already exists in the inventory! \n");
                return inventory;
            }
        }
    }
    printf ("Enter the price: "); 
    scanf("%lf", &new_node -> price);
    printf("Enter the quantity: ");
    scanf("%d", &new_node -> quantity);
    new_node -> next = NULL;
    if (inventory == NULL) 
    {
        return new_node;
    }
    else
    {
        for (a = inventory; a != NULL; a = a -> next)
        {
            if(a -> next == NULL)
            {
                a -> next = new_node;
                break;
            }
        }
    }
    return inventory;
}

Answer 1

Here's a way to do it:

#include <string.h>

#define ORG_NAME_LEN 40
#define SIZE_LEN 40

struct tshirt {
    char org_name[ORG_NAME_LEN+1];
    char size[SIZE_LEN+1];
    double price;
    int quantity;
    struct tshirt *next;
};

void swap_two_adjecent_nodes(struct tshirt * linked_list, int index) {
    struct tshirt * node = linked_list, * prev_node = linked_list;
    
    for (int i = 0 ; i < index + 1; i++) {
        prev_node = node;
        node = node->next;
    }

    char temp_org_name[ORG_NAME_LEN+1];
    char temp_size[SIZE_LEN+1];

    strcpy(temp_org_name, prev_node->org_name);
    strcpy(temp_size, prev_node->size);
    double temp_price = prev_node->price;
    int temp_quantity = prev_node->quantity;

    strcpy(prev_node->org_name, node->org_name);
    strcpy(prev_node->size, node->size);
    prev_node->price = node->price;
    prev_node->quantity = node->quantity;

    strcpy(node->org_name, temp_org_name);
    strcpy(node->size, temp_size);
    node->price = temp_price;
    node->quantity = temp_quantity;
}

void order_by_size(struct tshirt * linked_list) {
    for (int i = 0; i < 4; i++) {
        int index = 0;
        for (struct tshirt *node = linked_list; node->next; node = node->next, index++) {
            if (strcmp(node->size, node->next->size) > 0) {
                swap_two_adjecent_nodes(linked_list, index);
            }
        }
    }
}

void order_by_name(struct tshirt * linked_list) {
    for (int i = 0; i < 4; i++) {
        int index = 0;
        for (struct tshirt * node = linked_list; node->next; node = node->next, index++) {
            if (strcmp(node->org_name, node->next->org_name) > 0) {
                swap_two_adjecent_nodes(linked_list, index);
            }
        }
    }
}



void order(struct tshirt * linked_list) {
    order_by_size(linked_list);
    order_by_name(linked_list);
}

int main() {
    struct tshirt n1 = {"a", "c", 1, 1, NULL};
    struct tshirt n2 = {"b", "b", 2, 2, &n1};
    struct tshirt n3 = {"b", "c", 3, 3, &n2};
    struct tshirt n4 = {"d", "d", 4, 4, &n3};
    order(&n4);
    return 0;
}

Note that in swap_two_adjecent_nodes function I am swapping data, rather than pointers. While it is simpler it is definitely slower. Oh and I forgot to swap 4 in for loops with the size of a linked list. You can get it this way:

int getCount(struct tshirt* linked_list) {
    int count = 0; 
    struct tshirt* node = linked_list;
    while (node != NULL)
    {
        count++;
        node = node->next;
    }
    return count;
}

Answer 2

First of all I suggest that you make smaller functions that does one thing each, and does them well. Here's an example of how a comparison could look:

typedef struct tshirt tshirt;
struct tshirt
{
    char org_name[ORG_NAME_LEN+1];
    char size[SIZE_LEN+1];
    double price;
    int quantity;
    tshirt *next;
};

// A function specialized to only do the comparison of two tshirts:
int tshirt_comp(const tshirt *lhs, const tshirt *rhs) {
    int res = strcmp(lhs->org_name, rhs->org_name);
    if(res != 0) return res;
    return strcmp(lhs->size, rhs->size);
}

You could also insert new tshirts in the linked list in order directly so that the list is always sorted.

typedef struct tshirt_list { // example of a linked list with an extra `count` field
    tshirt *head;
    size_t count;
} tshirt_list;

I'd start by creating a function for finding the right spot for a new tshirt

// a function to find where to link in a tshirt pointer
tshirt **tshirt_list_find_prev(tshirt_list *inv, tshirt* ts) {
    int cmp = -1;
    tshirt *prev = NULL;

    // loop for as long as the tshirts are to be sorted before the new tshirt:
    for(tshirt *curr = inv->head;
        curr && (cmp = tshirt_comp(curr, ts)) < 0;
        prev = curr, curr = curr->next) {}

    if(cmp==0) return NULL;      // equal tshirt found
    if(prev) return &prev->next; // pointer to previous node's next
    return &inv->head;           // no prev node, return pointer to head
}

With that, adding a new tshirt* into the correct place will be simple:

bool tshirt_list_add(tshirt_list *inv, tshirt* ts) {
    tshirt **prev = tshirt_list_find_prev(inv, ts);
    if(prev==NULL) return false; // equal tshirt found, no insert to be done

    // link in the new tshirt*
    ts->next = *prev;
    *prev = ts;
    ++inv->count; // ... and increase `count`

    return true;
}

Demo

Answer 3

First of all, it's better to have an independant list data structure:

struct list {
    void *data; // Generic, can hold any type.
    struct list *next;
};

void list_init(struct list **ls)
{
    *ls = NULL;
}

bool list_push(struct list **ls, void *data)
{
    struct list *node = malloc(sizeof *node);
    if (!node) return false;
    
    node->data = data; // Save a reference to your data, not the data itself.
    node->next = *ls;
    *ls = node;
    
    return true;
}

bool list_pop(struct list **ls, void **data)
{
    if (!*ls) return false;
    
    struct list *rm = *ls;
    *ls = (*ls)->next;
    if (data) *data = rm->data; // You are responsible for the data you own.
    free(rm);
    
    return true;
}

bool list_top(const struct list *ls, void **data)
{
    if (!ls) return false;
    
    *data = ls->data;
    return true;
}

void list_print(const struct list *ls, void print(const struct list*))
{
    for (const struct list *lp = ls; lp; lp = lp->next)
        print(lp);
}

From that, you can write a function that returns the smallest (or the greatest, or whatever...) item of your list. Since it is a generic list, you have to tell it how to compare a given item against another. It's better to make it accept a range (i.e. from where to start to where to stop), because that will be useful in case you wanted to process a portion (*) of your list (or a sub-list):

struct list *list_find_min(struct list *begin, struct list *end, int (*cmp)(const void*, const void*))
{
    struct list *min = begin;
    for (struct list *lp = begin; lp != end; lp = lp->next)
        if (cmp(lp->data, min->data) < 0)
            min = lp;
    
    return min;
}

Next, you want to sort your list. You have to provide a function that does that:

void list_sort_range(struct list *begin, struct list *end, int (*cmp)(const void*, const void*))
{
    if (!begin) return;

    for (struct list *lp = begin; lp != end; lp = lp->next) {
        struct list *min = list_find_min(lp, end, cmp);
        swap(&lp->data, &min->data);
    }
}

void list_sort(struct list *ls, int (*cmp)(const void*, const void*))
{
    list_sort_range(ls, NULL, cmp);
}

swap() is straightforward:

void swap(void **p1, void **p2)
{
    void *tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

I have to make an ordered linked list by organization name and then by size. I have to compare the organization name first and then I have to sort them by size if they are in the same organization.

This can be done by first sorting your list by organization name (criterion 1), then by sorting the sub-lists (*) having the same name by size (criterion 2):

void list_sort_2(struct list *ls, int (*cmp1)(const void*, const void*), int (*cmp2)(const void*, const void*))
{
    // 1. Sort the list according to criterion 1
    list_sort_range(ls, NULL, cmp1);

    // 2. In case there are equal items, sort by criterion 2
    for (struct list *lp = ls; lp; lp = lp->next) {
        struct list *iter = lp->next;
        struct list *same = lp;

        // Find the sub-list of equal items
        for (; iter && cmp1(lp->data, iter->data) == 0; iter = iter->next)
            same = iter;
        
        // Sort the sub-list according to criterion 2
        if (lp != same)
            list_sort_range(lp, iter, cmp2);

        // Next iteration starts from same->next (advanced in for loop above).
        lp = same;
    }
}

Now, define yout tshirt struct, and provide a print function as well as comparison functions:

struct tshirt {
    char name[100];
    char size[100];
    double price;
    int quantity;
};

struct tshirt tshirt_new(const char *name, const char *size)
{
    struct tshirt shirt;
    strncpy(shirt.name, name, 99);
    strncpy(shirt.size, size, 99);
    return shirt;
}

int tshirt_compare_name(const void *s1, const void *s2)
{
    const struct tshirt *shirt1 = s1;
    const struct tshirt *shirt2 = s2;

    return strcmp(shirt1->name, shirt2->name);
}

int tshirt_size_code(const char *size)
{
    if (!strcasecmp(size, "XS")) return 1;
    if (!strcasecmp(size, "S"))  return 2;
    if (!strcasecmp(size, "M"))  return 3;
    if (!strcasecmp(size, "L"))  return 4;
    if (!strcasecmp(size, "XL")) return 5;
    return 0;
}

int tshirt_compare_size(const void *s1, const void *s2)
{
    const struct tshirt *shirt1 = s1;
    const struct tshirt *shirt2 = s2;

    int size_code1 = tshirt_size_code(shirt1->size);
    int size_code2 = tshirt_size_code(shirt2->size);

    return size_code1 == size_code2 ? 0 : (size_code1 < size_code2 ? -1 : 1);
}

void tshirt_print(const struct list *ls)
{
    struct tshirt *shirt = ls->data; // Cast from void*
    
    printf("%s-sized T-Shirts made by %s ", shirt->size, shirt->name);
    if (shirt->quantity != 0)
        printf("(%.2d items left at $%.2lf only!)\n", shirt->quantity, shirt->price);
    else
        printf("(empty stock)\n");
}

Putting it all together:

int main (void)
{
    struct tshirt shirts[] = {
        {"Celio", "XL", 19.99, 15},
        {"Pimkie", "L", 15.75, 10},
        {"LCW", "S", 15.00, 8},
        {"Celio", "M", 30.00, 3},
        {"Pimkie", "XL", 12.00, 20},
        {"LCW", "L", 10.00, 0},
        {"Calvin Klein", "XS", 89.98, 4},
        {"Celio", "XS", 35.50, 7},
        {"Zara", "S", 129.98, 19},
        {"Celio", "L", 19.75, 5}
    };

    struct list *ls;
    list_init(&ls);

    for (int i = 0; i < 10; i++)
        list_push(&ls, &shirts[i]);
    
    puts("Unsorted list:");
    list_print(ls, tshirt_print);

    list_sort(ls, tshirt_compare_name);
    puts("\nSorted by name:");
    list_print(ls, tshirt_print);

    list_sort(ls, tshirt_compare_size);
    puts("\nSorted by size:");
    list_print(ls, tshirt_print);

    list_sort_2(ls, tshirt_compare_name, tshirt_compare_size);
    puts("\nSorted by name and by size:");
    list_print(ls, tshirt_print);
}

Output:

Unsorted list:
L-sized T-Shirts made by Celio (05 items left at $19.75 only!)
S-sized T-Shirts made by Zara (19 items left at $129.98 only!)
XS-sized T-Shirts made by Celio (07 items left at $35.50 only!)
XS-sized T-Shirts made by Calvin Klein (04 items left at $89.98 only!)
L-sized T-Shirts made by LCW (empty stock)
XL-sized T-Shirts made by Pimkie (20 items left at $12.00 only!)
M-sized T-Shirts made by Celio (03 items left at $30.00 only!)
S-sized T-Shirts made by LCW (08 items left at $15.00 only!)
L-sized T-Shirts made by Pimkie (10 items left at $15.75 only!)
XL-sized T-Shirts made by Celio (15 items left at $19.99 only!)

Sorted by name:
XS-sized T-Shirts made by Calvin Klein (04 items left at $89.98 only!)
XS-sized T-Shirts made by Celio (07 items left at $35.50 only!)
L-sized T-Shirts made by Celio (05 items left at $19.75 only!)
M-sized T-Shirts made by Celio (03 items left at $30.00 only!)
XL-sized T-Shirts made by Celio (15 items left at $19.99 only!)
S-sized T-Shirts made by LCW (08 items left at $15.00 only!)
L-sized T-Shirts made by LCW (empty stock)
XL-sized T-Shirts made by Pimkie (20 items left at $12.00 only!)
L-sized T-Shirts made by Pimkie (10 items left at $15.75 only!)
S-sized T-Shirts made by Zara (19 items left at $129.98 only!)

Sorted by size:
XS-sized T-Shirts made by Calvin Klein (04 items left at $89.98 only!)
XS-sized T-Shirts made by Celio (07 items left at $35.50 only!)
S-sized T-Shirts made by LCW (08 items left at $15.00 only!)
S-sized T-Shirts made by Zara (19 items left at $129.98 only!)
M-sized T-Shirts made by Celio (03 items left at $30.00 only!)
L-sized T-Shirts made by Celio (05 items left at $19.75 only!)
L-sized T-Shirts made by LCW (empty stock)
L-sized T-Shirts made by Pimkie (10 items left at $15.75 only!)
XL-sized T-Shirts made by Pimkie (20 items left at $12.00 only!)
XL-sized T-Shirts made by Celio (15 items left at $19.99 only!)

Sorted by name and by size:
XS-sized T-Shirts made by Calvin Klein (04 items left at $89.98 only!)
XS-sized T-Shirts made by Celio (07 items left at $35.50 only!)
M-sized T-Shirts made by Celio (03 items left at $30.00 only!)
L-sized T-Shirts made by Celio (05 items left at $19.75 only!)
XL-sized T-Shirts made by Celio (15 items left at $19.99 only!)
S-sized T-Shirts made by LCW (08 items left at $15.00 only!)
L-sized T-Shirts made by LCW (empty stock)
L-sized T-Shirts made by Pimkie (10 items left at $15.75 only!)
XL-sized T-Shirts made by Pimkie (20 items left at $12.00 only!)
S-sized T-Shirts made by Zara (19 items left at $129.98 only!)