Create a linked list that stores items in ascending order or printing in that order

Question

I have a working linked list here that works to store the numbers and count of the numbers added in but the issue im having is understanding how to change this so that it doesn't add the numbers in just the order they were entered in, is there a way to easily change and fix this or is there a way to change my print function to do this function for me?

CODE

void KnapsackPrint(const listitemptr *knapsack){
   if(*knapsack==NULL)
       printf("knapsack: \n");
   else{
       listitemptr temp=*knapsack;
       while(temp!=NULL){
           printf("knapsack: %d (%d), ",temp->item,temp->count);
           temp=temp->next;
       }
       printf("\n");
   }
}

        listitemptr KnapsackAdd(listitemptr *knapsack, int item){
   if(*knapsack==NULL){//empty list
       listitemptr newest= malloc(sizeof(struct listitem));
       newest->item=item;
       newest->count=1;
       newest->next=NULL;
       *knapsack = newest;
       return newest;
   }else{
       listitemptr current=*knapsack;
       listitemptr prev=NULL;
       while(current!=NULL){
           if(current->item == item){
               current->count=current->count+1;
               break;
           }else if(current -> item > item){
               listitemptr new_node = malloc(sizeof(struct listitem));
               new_node-> item = item;
               new_node-> count= 1;
               new_node-> next = current;
               if(prev != NULL ){
                   prev ->next = new_node;
               }else {
                   current = new_node;
                   break;
               }

           }
           prev=current;
           current=current->next;
       }
       if(current==NULL){
           listitemptr newest= malloc(sizeof(struct listitem));
           newest->item=item;
           newest->count=1;
           newest->next=NULL;
           prev->next=newest;
           return newest;
       }
       return current;
   }
}

Knapsack.h and definitons

/* knapsack.h
 * implements simple knapsack data structure as a linked list 
 * NOTE: a function may update the value of input argument *knapsack if it changes the first node of the knapsack to another node. Such a change include the case when an item is added to an empty knapsack
 */

/* pointer to linked list node data structure */
typedef struct listitem* listitemptr;
/* data structure to use as linked list nodes */
struct listitem {
  int item;           // actual int item
  unsigned int count; // number of the same item in the knapsack; should be >= 1
  listitemptr next;   // pointer to next item 
};

/*
 * adds an item to a knapsack. Nodes should be in ascending order. You must simply increase the "count" if the item already exist in the knapsack; "count" must be set to 1 for previously-nonexisting items
 * @param knapsack: pointer to a listitemptr, itself pointing to the first item in a knapsack; NULL if knapsack has not been created yet 
 * @param item: integer item to add
 * @return pointer to the listitem added/updated; NULL if unsuccessful 
 */
listitemptr KnapsackAdd(listitemptr *knapsack, int item);

/*
 * removes a value from a knapsack; must update the "count" and delete the associated listitem when count becomes 0 
 * @param knapsack: [see KnapsackAdd() params]; updated to NULL if knapsack becomes empty
 * @param item: integer item to remove
 * @return 0 if successful, -1 otherwise (when item not found or knapsack is empty)
 */
int KnapsackRemove(listitemptr *knapsack, int item);

/*
 * prints integer items (in ascending order) and their counts in a knapsack
 * @param knapsack: [see KnapsackAdd() params]
 * @stdout: for example, "" (nothing) when knapsack==NULL, or "-125 (4), 10 (1), 26 (2)" when items include four of -125, one of 10, and two of 26
 * @return void
 */
void KnapsackPrint(const listitemptr *knapsack);

/*
 * returns count of a specific item in a knapsack
 * @param knapsack: [see KnapsackAdd() params]
 * @param item: integer item to search for
 * @return item count, or 0 if it does not exist
 */
unsigned int KnapsackItemCount(const listitemptr *knapsack, int item);

/*
 * total count of items in the knapsack
 * @param knapsack: [see KnapsackAdd() params]
 * @return total item count. For example, 7 in case the items are "-125 (4), 10 (1), 26 (2)" (see SnapsackPrint() description)
 */
unsigned int KnapsackSize(const listitemptr *knapsack);

**Current output given 2 1 **

knapsack: 2(1) 1(1)

**Desired output given 2 1 **

knapsack: 1(1) 2(1)

Answer 1

You're on the right track. Right now, your code works fine for incrementing count on existing items and adding new items. Here's what it looks like in pseudocode (I strongly recommend renaming your previous to current and temp to previous, then proceed with my code under that assumption--it'll make it a lot easier to reason about insertion and traversal):

function KnapsackAdd(knapsack, item) {
    if knapsack is empty {
        make a new knapsack with one item in it
    }
    else { // there are already items in the knapsack
        current = knapsack head
        prev = null

        while current != null {
            if current->item == item {
                current->count++
                break
            }

            previous = current
            current = current->next
        }

        // we're at the end of the list and didn't find the item
        if current == null {
            add new item to end of list
        }
    }
}

How can this be modified to add items such that we preserve sorted order? By adding another comparison during the traversal, we can check to see if the current node is greater than the number we want to insert. If it is, we know we've reached the correct insertion point:

function KnapsackAdd(knapsack, item) {
    if knapsack is empty {
        make a new knapsack with one item in it
    }
    else { // there are already items in the knapsack
        current = knapsack head
        prev = null

        while current != null {
            if current->item == item {
                current->count++
                break
            }
            else if current->item > item { // we're at the sorted insertion point!
                make new_node(item: item, count: 1, next: current)

                if prev != null { // we're inserting in the middle of the list
                    prev->next = new_node
                }
                else { // we're inserting at the beginning of the list
                       // so we need to update the head reference
                    set knapsack pointer to new_node
                }

                break                 
            }

            previous = current
            current = current->next
        }

        // we're at the end of the list and didn't find the item
        if current == null {
            add new item to end of list
        }
    }
}

Let's walk through an example:

knapsack.add(5)  // knapsack is [5]

knapsack.add(3)  // when iterating, we see that 5 > 3 and engage the new code
                 // block. We must update the head. knapsack is now [3 -> 5]

knapsack.add(7)  // knapsack is [3 -> 5 -> 7]. The new code block is not executed.

knapsack.add(6)  // when iterating, we see that 7 > 6 and engage the 
                 // new code block. No need to update the head; we use the
                 // previous element to link in the new 6 node.
                 // knapsack is [3 -> 5 -> 6 -> 7].

Hopefully this is sufficient to convince you that if we start with an empty list and always insert using this ordering scheme, we can guarantee list ordering.

The time complexity is the same as before: O(n).