Insert sorting by linked list in C?

I tried to find a problem similar to mine, but did not find much help.

I have a linked list of structures of this type:

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

First I create 10 PCB structures interconnected as follows:

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

Then I need to create another 20 PCB structures, but their values reg1should be generated using rand(). I am doing it like this:

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

However, when pasting these PCB structures into a linked list with random values, reg1I need to insert them into the linked list in order (insertion sort). What is the best way to approach this in just one list of links? Thanks

EDIT: Now I am tracking the first structure created to be able to scroll through the linked list from the very 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;
}

, 10 PCB, :

// 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 'next' value curr_two original 'next' value
                curr->next = curr_two->next;
                // change current item '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;
    }

.

+5
2

@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;
}

: , : , , LL. :

  • node :
  • ( ->next.
+3

"" , , . , node, next node, , node next node.


:

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;
    }
}

:

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

All Articles