Insertion sort on linked list in C?

Question

I've tried searching for a problem similar to mine, but haven't found much help.

I have a linked list of structs of this type:

struct PCB {
    struct PCB *next;
    int reg1, reg2;
};

I first create 10 PCB structs linked together in this way:

for(i=20;i<=30;i++) {
        curr = (struct PCB *)malloc(sizeof(struct PCB));
        curr->reg1 = i;
        curr->next  = head;
        head = curr;
    }

I then need to create 20 more PCB structs, but their reg1 values need to be generated using rand(). I'm currently doing that as so:

for (j = 0;j<20;j++) {
        curr = (struct PCB *)malloc(sizeof(struct PCB));
        curr->reg1 = rand()%100;
        curr->next  = head;
        head = curr;
    }

However, when inserting these PCB structs into the linked list with random reg1 values, I need to be inserting them in the linked list in order (insertion sort). What is the best way to approach this in just a single-link linked list? Thanks

EDIT: I am now keeping track of the first created struct to be able to loop through the linked list from the beginning:

// create root struct to keep track of beginning of linked list
root = (struct PCB *)malloc(sizeof(struct PCB));
root->next = 0;  
root->reg1 = 20;

head = NULL;

// create first 10 structs with reg1 ranging from 20 to 30
for(i=21;i<=30;i++) {
    curr = (struct PCB *)malloc(sizeof(struct PCB));
    // link root to current struct if not yet linked
    if(root->next == 0){
        root->next = curr;
    }
    curr->reg1 = i;
    curr->next  = head;
    head = curr;
}

Then, when I'm creating the additional 10 PCB structs that need to be insertion sorted:

// create 20 more structs with random number as reg1 value
    for (j = 0;j<20;j++) {
        curr = (struct PCB *)malloc(sizeof(struct PCB));
        curr->reg1 = rand()%100;
        // get root for looping through whole linked list
        curr_two = root;
        while(curr_two) {
            original_next = curr_two->next;
            // check values against curr->reg1 to know where to insert
            if(curr_two->next->reg1 >= curr->reg1) {
                // make curr's 'next' value curr_two's original 'next' value
                curr->next = curr_two->next;
                // change current item's 'next' value to curr
                curr_two->next = curr;
            }
            else if(!curr_two->next) {
                curr->next = NULL;
                curr_two->next = curr;
            }
            // move to next struct in linked list
            curr_two = original_next;
        }
        head = curr;
    }

But this immediately crashed my program.

Branson

Answer 1

Here is the simplified version of @Joachim:

void insert(struct PCB **head, const int reg1, const int reg2)
{
    struct PCB *new ;
        /* Find the insertion point */
    for (       ;*head; head = & (*head)->next)
    {
        if ((*head)->reg1 > reg1) break;
    }

    new = malloc(sizeof *new );
    new->reg1 = reg1;
    new->reg2 = reg2;
    new->next = *head;
   *head = new;
}

The idea is simple: there need not be any special cases, in any case: a pointer needs to be changed, this could be the root pointer, or the tail pointer, or some pointer in the midddle of the LL. In any/every case:

• the new node actually steals this pointer:
• it makes it point at itself
• it adopts the previous value as a successor (assigns it to its ->next pointer.

Badillo

But Hey, I only copied the comment from @Joachim! – Badillo

Answer 2

The "best" way would probably be to implement a new function for the insertion. This function would iterate over the list until it finds a node whose next nodes value is less or equal to the node you want to insert, then put the new node before the next node.

---

How about this function:

void insert(struct PCB **head, const int reg1, const int reg2)
{
    struct PCB *node = malloc(sizeof(struct PCB));
    node->reg1 = reg1;
    node->reg2 = reg2;
    node->next = NULL;

    if (*head == NULL)
    {
        /* Special case, list is empty */
        *head = node;
    }
    else if (reg1 < (*head)->reg1)
    {
        /* Special case, new node is less than the current head */
        node->next = *head;
        *head = node;
    }
    else
    {
        struct PCB *current = *head;

        /* Find the insertion point */
        while (current->next != NULL && reg1 < current->next->reg1)
            current = current->next;

        /* Insert after `current` */
        node->next = current->next;
        current->next = node;
    }
}

You would call it like this:

insert(&root, rand() % 100, 0);

Hyozo

but then wouldn't I need a double link to be able to get the nodes both before and after where I'll be inserting? – Branson

No need. When you are looking at a node, also look at the next node. So, for each iteration, you hold two references: one for the current one you are looking at, and another for the next one in the link. Then you compare those two with the node you are inserting. – Southward

@Branson No, because in the loop you have a current node, but you compare against current->next. This way you can insert the new node between current and current->next. – Hyozo

Insert after node when node->next == 0 or node->next->key > key – Akiko

I have edited the original question to show my attempt at implementing this method. However, it immediately crashes when I run it. – Branson

@Branson Why would you set head = a node you just inserted somewhere in the list? And you don't do what I said above. And you have other problems. Code crashes when it's not carefully crafted. – Akiko

@Branson Added a possible function to insert new nodes, in order. – Hyozo

Do people really write code like that? You don't need all those extra cases ... just keep a pointer to the link to insert at rather than to the node; initially it would be &head, then &node->next after each iteration. – Akiko

@JimBalter Apparently people do write code like this, I know of one person who does... Me. :) I think it makes the cases more visible, more separated from each other, and the whole flow more readable. – Hyozo

@JimBalter: My idea. The code can be reduced to 1/3 its initial LOC. – Badillo

en.wikipedia.org/wiki/Don't_repeat_yourself ... even if you write stuff like this, factor out the node construction. "I think it makes the cases more visible" -- A far better strategy is to eliminate special cases by abstraction and generalization. – Akiko

@JoachimPileborg, I copied that method and got it running, but it doesn't seem to work 100% correctly... the end results that are printed aren't always fully sorted. I'm trying to work out why now – Branson

@Branson "I don't think your input is being very constructive at this point. " -- And that's constructive? Whatever, sorry for any attempt to help you. – Akiko

@JimBalter I Would probably have done it a little different if I didn't write this just awoken in the middle of the night. :) At least the node creation I would have done only once. – Hyozo

@Branson Then it's time to use the debugger, and step though the code line by line until you find the error. – Hyozo

And for those who wonder, yes I am verbose in my programming. I generalize when I think it will not be convoluted or harder for others to read and understand. I believe the compiler will make more optimal code than I ever can, so I prefer to write small simple and readable blocks and let the compiler do whatever transformations it want to do. No sometimes it's not optimal, but at least I don't have to spend 15 minutes (or more) to understand my code a year down the road. – Hyozo