Martin Broadhurst > Data Structures > Linked list

Sorting a linked list by turning it into a binary tree

Introduction

A doubly-linked list node has two pointers, previous and next, and a binary tree node also has two pointers, left and right

This means that one way of sorting a linked list is to turn it into a binary tree and then back into a list again.

Turning the list into a binary tree

Turning the list into a tree is just a question of iterating over the list and performing the normal binary tree insertion algorithm. We need to remember to save the current node's next pointer before we insert it, as it will not be available afterwards.

MBlistnode * MBlinkedlist_to_tree(MBlinkedlist * list, MBcmpfn cmpfn)
{
    MBlistnode * root = list->head;
    if (root) {
        MBlistnode * node = root->next;
        root->previous = NULL;
        root->next = NULL;
        while (node != NULL) {
            MBlistnode * next = node->next;
            MBlistnode * current = root, * previous = NULL;
            int result;
            while (current != NULL) {
                previous = current;
                result = cmpfn(current->data, node->data);
                if (result > 0) {
                    current = current->previous;
                }
                else {
                    current = current->next;
                }
            }
            if (result > 0) {
                previous->previous = node;
            }
            else {
                previous->next = node;
            }
            node->previous = NULL;
            node->next = NULL;
            node = next;
        }
    }
    return root;
}

Turning the binary tree back into a list

This involves an inorder traversal of the tree, which is most easily implemented using recursion. We need to look out for the first and last elements; they need to be treated specially as they are the head and tail of the list.

The first element in a binary tree is the one that we encounter the first time we can go left no further. We find the last element by keeping track of the number of elements encountered so far, and comparing it to the number in the list.

void MBlinkedlist_from_tree(MBlinkedlist * list, MBlistnode * root,
        MBlistnode ** previous, unsigned int * count)
{
    if (root) {
        MBlistnode * left = root->previous;
        MBlistnode * right = root->next;
        MBlinkedlist_from_tree(list, left, previous, count);
        if (root->previous == NULL && list->head == NULL) {
            /* We're at the first element */
            list->head = root;
            list->head->previous = NULL;
        }
        else {
            (*previous)->next = root;
            root->previous = *previous;
        }
        if (*count == MBlinkedlist_get_count(list) - 1) {
            /* We're at the last element */
            list->tail = root;
            list->tail->next = NULL;
        }
        *previous = root;
        (*count)++;
        MBlinkedlist_from_tree(list, right, previous, count);
    }
}

The sort function

Our linked list sort function now just needs to combine the two operations:

void MBlinkedlist_sort(MBlinkedlist * list, MBcmpfn cmpfn)
{
    unsigned int count = 0;
    MBlistnode * previous;
    MBlistnode * tree = MBlinkedlist_to_tree(list, (MBcmpfn)strcmp);
    list->head = NULL;
    list->tail = NULL;
    MBlinkedlist_from_tree(list, tree, &previous, &count);
}

Example program

int main(void)
{
    char * elements[] = {"D", "B", "D", "F", "A", "C", "E"};
    const unsigned int n = sizeof(elements) / sizeof(const char *);
    MBlinkedlist * list;
    unsigned int i;

    list = MBlinkedlist_create();
    for (i = 0; i < n; i++) {
        MBlinkedlist_add_tail(list, elements[i]);
    }
    MBlinkedlist_sort(list, (MBcmpfn)strcmp);
    MBlinkedlist_for_each(list, (MBforfn)puts);
    MBlinkedlist_delete(list);

    return 0;
}

Source code

Related links

Copyright (C) 2010 Martin Broadhurst