Thread: Sort a double linked list

  1. #1
    Registered User
    Join Date
    Jul 2020
    Posts
    47

    Sort a double linked list

    Hello,

    My aim is to sort a double linked list.

    My understanding is that the sort functions in the standard library sort arrays; to sort a linked list I need to provide my own function/s.

    Rather than re-invent the wheel, I found some code that seems to work well.

    Sort a Doubly Linked List using Merge Sort - Techie Delight

    However the structure of the linked list in their code is as follows;
    Code:
    struct node
    {
        int data;
        struct node *next, *prev;
    };
    Whereas the structure of my linked list is as follows;
    Code:
    struct record
    {
        int data;
    };
    typedef struct record record_t;
    
    struct node
    {
        record_t    record;
        struct node *next;
        struct node *prev;
    };
    typedef struct node node_t;
    
    struct dll
    {
        node_t      *head;
        node_t      *tail;
    };
    typedef struct dll dll_t;
    So I'm trying to modify the sample code to work with my data structure which has head/tail pointers.

    The issue that I have encountered, is that the sample code accesses the linked list via a double-pointer

    e.g. void mergeSort(struct node **head)

    Where I access the linked list via a single-pointer
    void mergeSort(dll_t *dll)
    (e.g. dll->head or dll->tail)

    If you compare the two mergesort functions

    Original:
    Code:
    void mergeSort(struct node **head)
    {
        // base case: 0 or 1 node
        if (*head == NULL || (*head)->next == NULL)
            return;
    
        // split head into 'a' and 'b' sublists
        struct node *a = *head, *b = NULL;
        split(*head, &a, &b);
    
        // recursively sort the sub-lists
        mergeSort(&a);
        mergeSort(&b);
    
        // merge the two sorted lists together
        *head = merge(a, b);
    }
    Attempted port:
    Code:
    void mergeSort(dll_t *dll)
    {
        // base case: 0 or 1 node
        if (dll->head == NULL || dll->head->next == NULL)
        {
            return;
        }
        else                                      
        {
            // split list into 'a' and 'b' sublists
            node_t *a = dll->head, *b = NULL;
            node_t **head;
            *head = dll->head;
    
            split(*head, &a, &b)
    
            // sort the sub-lists
            mergeSort_sublists(&a);
            mergeSort_sublists(&b);
    
            // merge the two sorted lists together
            *head = merge(a, b);
    
        } // else (more than 1 node)
    } //mergeSort
    I try to set *head using
    Code:
    node_t **head;
    *head = dll->head;
    This causes an abend, so obviously not permitted.

    I haven't been able to figure out why this is wrong / how to resolve.

    Would appreciate some suggestions

    Thanks
    VW

  2. #2
    Registered User
    Join Date
    Sep 2020
    Posts
    425
    I have no idea how the merge() and split() work, but your thought process seems sound. They might have a error in them...

    You also need to keep the 'tail' pointer up to date.

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by VeeDub
    My understanding is that the sort functions in the standard library sort arrays; to sort a linked list I need to provide my own function/s.
    Merge sorting a linked list is the right thing to do if you want to optimise both space and time efficiency, but if you have the memory for it and really do want to use qsort, there's the "cheating" method of creating an array of pointers to the nodes, sorting the pointers according to the data in the nodes using qsort with an appropriate comparator, and then recreating the linked list in sorted order (i.e., relinking the nodes) via the sorted pointers.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User
    Join Date
    Sep 2020
    Posts
    425
    I think that the aim is to reinvent the wheel

    You seem to be well down the track, so here's some pseudo code to help you along. You should be able to see what bits you are missing.

    Code:
    mergesort of list_inout:
    
       if list_inout empty 
           return
    
       # Single item in list
       if list_inout's head is list_inout's tail
           return
    
        # Share the items out into two lists
        while list_inout is not empty
           remove head of list_inout
           add it to tail of list_a
           if list_inout is not empty
             remove head of list_inout
             add it to tail of list_b
    
        # Sort each half
        mergesort list_a
        mergesort list_b
    
        # Merge the two halves together in order
        while list_a is not empty and list_b is not empty
            if list_b is empty
               remove head of list_a
               add it to tail of list_inout
            else if list_a is empty
               remove head of list_b
               add it to tail of list_inout
            else
               if list_a.head->data < list_b.head-data
                  remove head of list_a
                  add it to tail of list_inout
               else
                  remove head of list_b
                  add it to tail of list_inout
    As you hopefully see, you only really need two list operations.

    - Take the item out of the head of the list

    - Add an item to the tail of the list.

    If you have them coded correctly, then the rest should fall in line pretty quickly.

  5. #5
    Registered User
    Join Date
    Jul 2020
    Posts
    47
    Hello hamster_nz,

    Thanks for the pseudo code, this is very helpful.

    I think you're right reinventing the wheel is the right option in this instance.

    Cheers!

    VW

  6. #6
    Registered User
    Join Date
    Jul 2020
    Posts
    47
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    struct record
    {
        int data;
    };
    typedef struct record record_t;
    
    struct node
    {
        record_t    record;
        struct node *next;
        struct node *prev;
    };
    typedef struct node node_t;
    
    struct dll
    {
        node_t      *head;
        node_t      *tail;
    };
    typedef struct dll dll_t;
    
    // function to add a node at the tail of a doubly linked list
    void add_tail(dll_t *dll, record_t *record)
    {
        node_t *node = malloc(sizeof(*node));
        if (node == NULL)
        {
            printf("Malloc failed in: add_tail: node\n");
            getchar();
        }
    
        node->record = *record;
        node->next = NULL;
        node->prev = NULL;
    
        if ( dll->tail == NULL )
        {
            // first node
            dll->head = dll->tail = node;
        }
        else
        {
            // insert additional nodes at the tail
            node_t  *curr = dll->tail;
    
            dll->tail = node;
            node->prev = curr;
            curr->next = node;
        }
    
    } // add_tail
    
    // function to remove head node from list
    void remove_head(dll_t *dll)
    {
        node_t *curr = dll->head;
    
        // walk through list
        while (curr != NULL)
        {
            // handle first item
            if (curr->prev == NULL)
            {
                if (curr->next == NULL)
                {
                    // only item?
                    dll->head = NULL;
                    dll->tail = NULL;
                }
                else
                {
                    // more items?
                    dll->head = curr->next;
                    dll->head->prev = NULL;
                }
                free(curr);
            }
            // Only process a single node
            break;
        }
    
    } // remove_head
    
    // Helper function to print nodes of a doubly linked list
    void printDLL_fwd(dll_t *dll)
    {
        printf("Forward\n");
    
        node_t  *curr = dll->head;
    
        while (curr != NULL)
        {
            printf("%d -> ", curr->record.data);
            curr = curr->next;
        }
        printf("null\n\n");
    } //printDLL_fwd
    
    void printDLL_rev(dll_t *dll)
    {
        printf("Reverse\n");
    
        node_t  *curr = dll->tail;
    
        while (curr != NULL)
        {
            printf("%d -> ", curr->record.data);
            curr = curr->prev;
        }
        printf("null\n\n");
    } // printDLL_rev
    
    void split(dll_t *original_list, dll_t *split_list)
    {
        // Initialise record
        record_t record;
    
        // Copy head record from original list
        record = original_list->head->record;
    
        // Remove head record from original list
        remove_head(original_list);
    
        // Add record to split_list
        add_tail(split_list, &record);
    
    } // split
    
    void merge(dll_t *original_list, dll_t *list_a, dll_t *list_b)
    {
        // Initialise record
        record_t record;
    
        while ( (list_a->head != NULL) || (list_b->head != NULL) )
        {
            // if list_b is empty
            if (list_b->head == NULL)
            {
                // read record from list_a (head)
                record = list_a->head->record;
    
                // remove record from list_a
                remove_head(list_a);
    
                // add record to original_list
                add_tail(original_list,&record);
            }
            // if list_a is empty
            else if (list_a->head == NULL)
            {
                // read record from list_b (head)
                record = list_b->head->record;
    
                // remove record from list_b
                remove_head(list_b);
    
                // add record to original_list
                add_tail(original_list,&record);
            }
            else
            // list_a and list_b both have records
            {
                if (list_a->head->record.data < list_b->head->record.data)
                {
                    // read record from list_a (head)
                    record = list_a->head->record;
    
                    // remove record from list_a
                    remove_head(list_a);
    
                    // add record to original_list
                    add_tail(original_list,&record);
                }
                else
                {
                    // read record from list_b (head)
                    record = list_b->head->record;
    
                    // remove record from list_b
                    remove_head(list_b);
    
                    // add record to original_list
                    add_tail(original_list,&record);
                }
            } // else
        } // While list_a is not empty and list_b is not empty
    } //merge
    
    // Function to sort a doubly linked list using merge sort algorithm
    void mergeSort(dll_t *dll)
    {
        // if list empty
        if ( (dll->head == NULL) && (dll->tail == NULL) )
        {
            // do nothing
            return;
        }
    
        // if list has one node
        if ( dll->head == dll->tail )
        {
            // do nothing
            return;
        }
    
        // Initialise two "worker" lists
        dll_t list_a;
        list_a.head = list_a.tail = NULL;
    
        dll_t list_b;
        list_b.head = list_b.tail = NULL;
    
        // while the original_list is not empty - split items into two lists: list_a and list_b;
        while(dll->head != NULL)
        {
            // remove item from original list - add to list_a
            split(dll, &list_a);
    
            // if original list still not empty, remove item from original list - add to list_b
            if(dll->head != NULL)
            {
                split(dll, &list_b);
            }
        } // while original_list is not empty
    
        // Sort each "worker" list
        mergeSort(&list_a);
        mergeSort(&list_b);
    
        // Merge two "worker" lists together in order
        merge(dll,&list_a,&list_b);
    
    } //mergeSort
    
    int main(void)
    {
        int keys[] = { 6, 4, 5, 8, 7, 9, 5, 2, 1 };
        int n = sizeof(keys)/sizeof(keys[0]);
    
        // Initialise list
        dll_t dll;
        dll.head = dll.tail = NULL;
        record_t record;
        record.data = 0;
    
        // add records
        for (int i = 0; i < n; i++)
        {
            record.data = keys[i];
            add_tail(&dll, &record);
        }
    
        printf("Before\n");
        printf("------\n");
        printDLL_fwd(&dll);
        printDLL_rev(&dll);
    
        mergeSort(&dll);
    
        printf("After\n");
        printf("-----\n");
        printDLL_fwd(&dll);
        printDLL_rev(&dll);
    
        return 0;
    }

  7. #7
    Registered User
    Join Date
    Sep 2020
    Posts
    425
    Looking really swish! Are you happy with it?

    Here's a road to improvement..
    If you make a separate function to create nodes:

    Code:
    node_t *node_make(record_t *record) {
        node_t *node = malloc(sizeof(*node));
        if (node == NULL) {
            printf("Malloc failed in: add_tail: node\n");
            getchar();
            return NULL;
        }
        node->record.data = record->data;
        node->next = NULL;
        node->prev = NULL;
        return node;
    }
    and if you make remove_head() return the pointer of the node that was removed from the list, rather than freeing it:

    Code:
    node_t *remove_head(dll_t *dll)
    {
        node_t *curr = dll->head;
        if(curr == NULL) {
           return NULL;
        } else if(curr->next == NULL) {
           dll->head = NULL;
           dll->tail = NULL;
        } else {
           dll->head = curr->next;
           dll->head->prev = NULL;
        }
        curr->next = NULL;
        curr->prev = NULL;
        return curr;
    } // remove_head
    Then you can chain things together a lot more cleanly:

    Code:
        while(dll->head != NULL) {
            add_tail(&list_a, remove_head(dll));
            if(dll->head != NULL) {
                add_tail(&list_b, remove_head(dll));
            }
        }
    Oh, and you will want a function to release the resources in a list, just before you exit.

    Code:
    void empty_list(dll_t *dll) {
       while(dll->head != NULL) {
          free(remove_head(dll));
       }
    }
    What are your thoughts on your code? Are you happy with it?
    Last edited by hamster_nz; 10-06-2020 at 07:18 PM.

  8. #8
    Registered User
    Join Date
    Jul 2020
    Posts
    47
    Quote Originally Posted by hamster_nz View Post
    Looking really swish! Are you happy with it?
    Yes I am, thanks.

    Thought I should share the result since I received assistance.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. sort linked list using quick sort in C
    By Babita Sandooja in forum C Programming
    Replies: 1
    Last Post: 03-04-2014, 09:24 AM
  2. Trouble using Insertion Sort on Double Linked List
    By mattdol in forum C Programming
    Replies: 18
    Last Post: 02-06-2014, 02:57 PM
  3. Dynamic List Char Array & Double Linked List
    By Roadrunner2015 in forum C Programming
    Replies: 18
    Last Post: 10-20-2013, 01:31 PM
  4. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  5. Sort strings in double linked list. (Optimize code)
    By netstar in forum C++ Programming
    Replies: 15
    Last Post: 02-28-2005, 01:40 AM

Tags for this Thread