Write a program to sort a linked list of integers.

Source Code

Brief explanation is provided after the source code.

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

typedef struct node *LINK;
struct node {
    int item;
    LINK next;
};

void list_add(LINK *head, int item);
void list_prn(LINK head);
void list_sort(LINK head);
void list_delete(LINK head);


int main(int argc, char ** argv) {
    int i;
    LINK head;
    head = NULL; /* empty list */
    // Generate 10 random numbers and store them in a linked list
    for (i = 1; i <= 10; i++) {
        list_add(&head, rand() % 1000);
    }
    // Display content of list
    list_prn(head);

    // List Sort
    list_sort(head);

    // Display content of sorted list
    printf("\nSorted List\n");
    list_prn(head);

    // Delete list
    list_delete(head);
    printf("\nList deleted\n");

    return 0;
}

// Add items to the front or beginning of the list
void list_add(LINK *head, int item) {
    LINK tmp;
    /*allocate space for new node*/
    if ((tmp = malloc(sizeof(*tmp))) == NULL) {
        printf("\nNot enough memory");
        exit(1);
    }
    tmp -> item = item;
    tmp -> next = *head;
    *head = tmp;
}

// Print list beginning with the head
void list_prn(LINK head) {
    LINK tmp = head;
    printf("List items:\n");
    while(tmp != NULL) {
        printf("%d ", tmp->item);
        tmp = tmp->next;
    }
    printf("\n");
}


void list_sort(LINK head) {
    LINK tmp, track_node;
    int min;
    // Find node with smallest value in list
    while (head->next != NULL){
        tmp = head;
        min = tmp->item;
        while(tmp->next != NULL) {
            if(tmp->next->item < min) {
                min = tmp->next->item;
                track_node = tmp->next;
            }
            tmp = tmp -> next;
        }
        // Interchange its data with that at the top of the list
        track_node->item = head->item;
        head->item = min;
        // Assign Node next to the top as new top
        head = head -> next;
        track_node = head;
    }

}

// Loop through each node and free up the space used by that node
void list_delete(LINK head) {
    LINK tmp;
    while (head != NULL) {
       tmp = head -> next;
       free(head);
       head = tmp;
    }
}

When you compile and execute the above program it produces the following result on Linux:

List items:
421 649 492 386 335 793 915 777 886 383 

Sorted List
List items:
335 383 386 421 492 649 777 793 886 915 

List deleted

Brief Explanation

  • A linked list is a collection of linearly connected structures.
  • A variable of type LINK is a pointer to a node on the linked list
  • The function list_sort is used to sort a linked list as follows:
  1. It finds the node with the smallest value in the list.
  2. It interchanges its data with that at the top of the list.
  3. It assigns the node next to the top as the new top.
  4. It repeats steps 1, 2 and 3 until the end of the list.

Add comment


Security code
Refresh