Linked Lists – Sorting, Searching, Finding Maximum and Minimum

In one of the previous posts, we discussed in depth the concepts behind linked lists. In this post, we will explore some more programs and applications built on linked lists. Remember that the data structure that we are using is quite simple:

typedef struct linked_list
{
    int data;
    struct linked_list *next;
} Node;

We define a data element and a pointer to the next node. Let’s first start with sorting a linked list.

Sort a linked list

void Sort()
{
    // traverse the entire list
    for (Node *list = head; list->next != NULL; list = list->next)
    {
        // compare to the list ahead
        for (Node *pass = list->next; pass != NULL; pass = pass->next)
        {
            // compare and swap
            if (list->data > pass->data)
            {
                // swap
                int temp = list->data;
                list->data = pass->data;
                pass->data = temp;
            }
        }
    }
}

As you see above, sorting a linked list is not very different that sorting an array.

Search an element in linked list

// finds the first node with the specified value
// assumes that head pointer is defined elsewhere
Node* Find(int value)
{
    // start at the root
    Node *currentNode = head;

    // loop through the entire list
    while (currentNode != NULL)
    {
        // if we have a match
        if (currentNode->data == value)
            return currentNode;
        else // move to the next element
            currentNode = currentNode->next;
    }
}

Find maximum and minimum in a linked list

// finds the maximum and minimum in the list
// assumes that head pointer is defined elsewhere
int MaxMinInList(int *max, int *min)
{
    // start at the root
    Node *currentNode = head;

    if (currentNode == NULL)
        return 0; // list is empty

    // initialize the max and min values to the first node
    *max = *min = currentNode->data;
    
    // loop through the list
    for (currentNode = currentNode->next; currentNode != NULL; currentNode = currentNode->next)
    {
        if (currentNode->data > *max)
            *max = currentNode->data;
        else if (currentNode->data < *min)
            *min = currentNode->data;
    }

    // we found our answer
    return 1;
}

At this point, you should be very comfortable with linked lists and ready to tackle some more complex operations and structures.