How do I add a number in a sorted linklist?

Question

I'm trying to make a function in C to add numbers to an ordered linked list, but I've got the feeling it can be done in a lot less rows. Is there an example?

This example code does not work:

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

struct listNode {
    int number;
    struct listNode *nextPtr;
};

typedef struct listNode LISTNODE;
typedef LISTNODE *LISTNODEPTR;
int main ()
{
    LISTNODE a = {16,NULL};
    LISTNODEPTR ptr = &a;
    printList(&a);
    insert(&ptr,23);
    insert(&ptr,10);
    insert(&ptr,12);
    insert(&ptr,15);
    printList(&a);
    return 0;
}

void insert(LISTNODEPTR *list, int number){
    if((**list).number > number){
    printf("lol2 %d",number);
        LISTNODE *newNode =  malloc(sizeof(LISTNODE));
        (*newNode).number  = number;
        (*newNode).nextPtr  =  (*list);
        *list = newNode;
    }else if((**list).nextPtr == NULL){
    printf("lol %d",number);
        LISTNODE *newNode =  malloc(sizeof(LISTNODE));
        (*newNode).number  = number;
        (*newNode).nextPtr  =  NULL;
        (**list).nextPtr = newNode;

    }else{
    printf("other %d\n",number);
        LISTNODE *listPtr = *list;
        LISTNODE *listPtr1 = (*listPtr).nextPtr;
        while((*listPtr1).number < number && (*listPtr).nextPtr != NULL ){
            printf("%d > %d\n",(*listPtr).number , number);
            listPtr = (*listPtr).nextPtr;
            listPtr1 = (*listPtr).nextPtr;
        }
        LISTNODE *newNode =  malloc(sizeof(LISTNODE));
        (*newNode).number  = number;
        if((*listPtr).nextPtr != NULL){
            (*newNode).nextPtr  =  listPtr1;
        }else{
            (*newNode).nextPtr  =  NULL;
        }
        (*listPtr).nextPtr = newNode;
    }
}

Answer 1

Well, you should probably write a function InsertAfter, which takes a pointer to a list node and a new value, and then

• Allocate a new node with the value in it and with its nextptr set to the nextptr of the old list node
• Change the nextptr of the old list node to point to the new node

Then you have to special-case 'this value is smaller than the value at the start of the list' (in which case you have to return a pointer to the new start-of-list), otherwise you loop along until you get to a number bigger than the value you wanted to insert or the end-of-list, and then insert after the one just before that.

Answer 2

One place to start shortening this code is to look for duplication: the things that you do in multiple places.

For example, no matter where you end up inserting the new node, you are always going to have to allocate it and set its number field, so this code:

    LISTNODE *newNode =  malloc(sizeof(LISTNODE));
    (*newNode).number  = number;

should be done once, at the top of your function.

Answer 3

some pseudocode for insert:

listNode *curNode = *list,*prevNode = 0, *newNode= 0;
while (curNode->nextPtr && number <= curNode->number)
{
   prevNode = curNode;
   curNode = curNode->nextPtr;
}
newNode = CreateNode(number);
newNode->nextPtr = curNode;

if (prevNode)
   prevNode->nextNode = newNode;
else
   *list = newNode;

Answer 4

Yes, it can be done much shorter:

void insert(LISTNODEPTR *list, int number)
{
    LISTNODE *newNode = malloc(sizeof *newNode);
    newNode->number = number;

    while (*list && (*list)->number < number)
    {
        list = &(*list)->nextPtr;
    }

    newNode->nextPtr = *list;
    *list = newNode;
}

Note also that your printList lines in main should be printList(ptr);