Bubble Sort on double linked list with

Question

This is my double linked list implementation and the bubble sort on it. Other functions works well but the print function did not give any output after I did bubble sort on the list.

//
//  Double_linked_list.c
//
//
//  Created by Dengke Liu on 9/7/15.
//
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include "list.h"


// initialize the list structure;
void init(slist_t *list){
    list->head=NULL;
    list->tail=NULL;
}

// add a string to the end of the list
void append(slist_t *list, char *val){

    // creating a newItem object
    list_item_t* newItem = (list_item_t*)malloc(sizeof(list_item_t));
    newItem->value = val;
    newItem->next=NULL;

    // if there are no elements, just use newItem as head
    if (!list->head) {
        newItem->prev=NULL;
        list->head=newItem;
        list->tail=newItem;
    }else{
        // otherwise append the node and point the tail at the end
        newItem->prev=list->tail;
        list->tail->next=newItem;
        list->tail=newItem;
    }
}

// print the elements of the list
void print(slist_t *list){

    list_item_t* temp=list->head;
    while (temp!=NULL) {
        printf("%s\n", temp->value);
        temp=temp->next;
    }
}

// empty the list
void empty(slist_t *list){

    list_item_t *temp=list->head;
    while (temp->next!=NULL) {
        temp=temp->next;
        free(temp);
    }
    free(list->head);
}

// sort the elements in list in lexical order using bubble sort
void bubblesort(slist_t *list){

    if (list->head==NULL) {
        printf("this is an empty list");
    }

    // to record the comparision state
    bool swapped=true;
    list_item_t *temp;

    while (swapped) {

        swapped=false;
        temp=list->head;

        // iterate through the list to swap unordered elements
        while (temp!=list->tail) {
            // compare two elements, if they are disordered, then swap
            if(strcmp(temp->value, temp->next->value)>0){

                // swap the elements
                if (temp->prev!=NULL) {
                    temp->prev->next=temp->next;
                }
                if (temp->next->next!=NULL) {
                    temp->next->next->prev=temp;
                }

                temp->next=temp->next->next;
                temp->next->next=temp->prev;
                temp->next->next=temp;
                temp->prev=temp->next;

                // change the swap record
                swapped=true;
            }
            temp=temp->next;
        }

        print(list);
    }
}

int main(){
    slist_t *list;
    init(list);
    append(list, "blue");
    append(list, "yellow");
    append(list, "black");
    append(list, "red");
    append(list, "green");
    print(list);
    bubblesort(list);
    print(list);
    empty(list);
    return 0;
}

The first print function in main() gave the right output, while the second print function did not give any output. Can anyone help me debug it?

Answer 1

Your program looks reasonable in general form, but the more I looked at it the more errors I found in the details. In particular,

1) In function main(), you declare variable list, a pointer, but never initialize it. You then pass this indeterminate value to the init() function, which proceeds to dereference it as if it were a valid pointer. This produces undefined behavior. You could allocate storage dynamically for list, but in this case it's easier to just do this:

int main() {
    slist_t my_list;
    slist_t *list = &my_list;
    /* ... */

2) Your bubblesort() function fails to update list->head and list->tail when it performs swaps involving the nodes those point to. This will cause problems both during the sort procedure and after.

3) Your bubblesort() function does not swap list nodes correctly. There's more than one way you could do it, but what you actually implement is not one of them. It first breaks at temp->next->next=temp->prev, because at that point temp->next has already been updated, with the result that temp->next->next is not one of the pointers you want to modify. One of the easier ways to structure such a swap is as the deletion of node temp from the list, followed by its reinsertion one position later. Keep careful track of which pointer points to what. It could help to draw a diagram of it.

4) Your bubblesort() function should avoid setting temp = temp->next during iterations of the inner loop in which a swap was performed. In those cases, you don't know how temp compares to the new temp->next, or even whether there is a temp->next any more. If there isn't (i.e. if the new temp->next is NULL) then updating temp will be disastrous. You'll be lucky to complete a run of the sort routine without that happening.