doubly linked list in C sorting problems

Question

I am trying to write a method that sorts the elements in a doubly linked list. The list is made up of structs with a forward and backward pointer (flink, blink) to the next element. head->blink should be null, tail->flink should be null (aka not circular). I tried a selection sort approach but I keep getting a segmentation fault. I have isolated the problem into the commented lines. However I included all of my code, the sort method is at the bottom.

//header (dblLinkList.h)

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

typedef struct _DblLinkList {
    struct _DblLinkList *flink;
    struct _DblLinkList *blink;
    int num;
} DblLinkList;

struct _DblLinkList *head, *tail;

struct _DblLinkList *init(int nElements);
void sort(struct _DblLinkList *listNode);
void print(struct _DblLinkList *listNode);

//implementation

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

int main() {
    struct _DblLinkList *list1 = init(2);
    printf("-----Head to Tail------\n");
    print(list1);
    printf("Sorting...\n");
    sort(list1);
    printf("-----Head to Tail------\n");
    print(list1);
}

struct _DblLinkList *init(int nElements) {
    struct _DblLinkList *listNode;
    int i = 0;

    for(i = 0; i < nElements; i++) {
        listNode = (struct _DblLinkList *)malloc(sizeof(struct _DblLinkList));
        listNode->num = random();

        if(head == NULL) {
            head = listNode;
            listNode->blink = NULL;
        } else {
            tail->flink = listNode;
            listNode->blink = tail;
        }
        tail = listNode;
        listNode->flink = NULL;
    }
    return listNode;
}

void print(struct _DblLinkList *listNode) {
    for(listNode = head; listNode != NULL; listNode = listNode->flink) {
        printf("%d\n", listNode->num);
    }
}

void sort(struct _DblLinkList *listNode) {
    //Not working properly
    struct _DblLinkList *listNode2;
    struct _DblLinkList *minNode;
    struct _DblLinkList *temp = (struct _DblLinkList *)malloc(sizeof(struct _DblLinkList));

    //start from the head and traverse the list
    for(listNode = head; listNode != NULL; listNode = listNode->flink) {
        minNode = listNode;
        listNode2 = listNode->flink;
        for(;listNode2 != NULL;  listNode2 = listNode2->flink) {
            if (listNode2->num < minNode->num) {
                minNode = listNode2;
            }
        }
//Problem Lies here vvvvvvvvvvvv
            temp->flink = listNode->flink;
            temp->blink = listNode->blink;  
            listNode->blink = listNode2;
            listNode->flink = listNode2->flink;
            listNode2->flink = temp;
            listNode2->blink = temp->blink; 
        printf("min: %d\n", minNode->num);
        }
    }

You tagged this C and C++...it looks like C to me, though. Which is it, just to be explicitly clear? — Thomas Owens
– Thomas Owens, Commented Jun 7, 2011 at 19:53
If you run your program in a debugger, you should be to identify exactly which line triggered the seg-fault. You should then be able to inspect the variable values at that point, and compare them to what you expect them to be. — Oliver Charlesworth
– Oliver Charlesworth, Commented Jun 7, 2011 at 19:55
@Matt : Will you accept an answer to this question that uses C++ code? — ildjarn
– ildjarn, Commented Jun 7, 2011 at 19:56
Is this some zany professor's homework or is there a specific reason you are sorting a dlinked list? Can you not read it into another structure, sort it, and read it back? — user774340
– user774340, Commented Jun 7, 2011 at 20:03

cnicutar · Accepted Answer · 2011-06-07 19:58:35Z

3

for(;listNode2 != NULL;  listNode2 = listNode2->flink)

This loop only exits when listNode2 is NULL. So we've established that at this point listNode2 == NULL.

Thou shalt not follow the NULL pointer, for chaos and madness await thee at its end.

And here is what you're doing, breaking the second commandment

listNode2->flink = temp;

answered Jun 7, 2011 at 19:58

cnicutar

184k26 gold badges378 silver badges398 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

cnicutar Over a year ago

@Arthur Shipkowski Good call; found another one :))

Arthur Shipkowski Over a year ago

Heh, and here I deleted my comment, figuring you'd just had a typo.

trutheality · Accepted Answer · 2011-06-07 19:57:08Z

2

Looks like listNode2 can be NULL after that for loop. You should check that before you try to access listNode2->flink.

answered Jun 7, 2011 at 19:57

trutheality

23.5k6 gold badges58 silver badges68 bronze badges

1 Comment

Arthur Shipkowski Over a year ago

Not the only problem with the routine, but it looks like the source of the segfault to me.

vhallac · Accepted Answer · 2011-06-07 20:03:39Z

I can see a few problems in the code:

You keep inserting the same chunk of memory, temp when you are moving nodes around.
When you are moving listnode away, listnode->flink->blink (before the move) still points to listnode.
Same as #2, but for listnode->blink->flink
When you move listnode, you potentially skip all the nodes between old position and listnode2, as linstnode->flink is now listnode2->flink, which is not necessarily the old value. This won't cause a crash, but it will leave some nodes unsorted.
When moving nodes around, I didn't see any special handling of head an tail, so they will probably point to weird nodes when you are done. One trick to handle this seamlessly is to make them into concrete _DblLinkList structures, so that the code is not riddled with if statements.

There may be other problems.

Rajivji · Accepted Answer · 2011-06-07 20:52:50Z

FTFY: still pretty ugly hack but should work

--- 2.c 2011-06-07 13:03:48.000000000 -0700
+++ 1.c 2011-06-07 13:49:18.000000000 -0700
@@ -7,7 +7,8 @@
     int num;
 } DblLinkList;

-struct _DblLinkList *head, *tail;
+struct _DblLinkList *head = NULL;
+struct _DblLinkList *tail = NULL;

 struct _DblLinkList *init(int nElements);
 void sort(struct _DblLinkList *listNode);
@@ -35,16 +36,16 @@
     for(i = 0; i < nElements; i++) {
         listNode = (struct _DblLinkList *)malloc(sizeof(struct _DblLinkList));
         listNode->num = random();
+               listNode->flink = NULL;
+               listNode->blink = NULL;

         if(head == NULL) {
             head = listNode;
-            listNode->blink = NULL;
         } else {
             tail->flink = listNode;
             listNode->blink = tail;
         }
         tail = listNode;
-        listNode->flink = NULL;
     }
     return listNode;
 }
@@ -55,29 +56,33 @@
     }
 }

-void sort(struct _DblLinkList *listNode) {
+void sort(struct _DblLinkList *_listNode) {
     //Not working properly
-    struct _DblLinkList *listNode2;
-    struct _DblLinkList *minNode;
-    struct _DblLinkList *temp = (struct _DblLinkList *)malloc(sizeof(struct _DblLinkList));
+       struct _DblLinkList* listNode = head;
+    struct _DblLinkList *listNode2 = NULL;
+    struct _DblLinkList *minNode = head;
+    struct _DblLinkList *temp = NULL;

     //start from the head and traverse the list
-    for(listNode = head; listNode != NULL; listNode = listNode->flink) {
-        minNode = listNode;
+    for(; listNode != NULL; listNode = listNode->flink) {
         listNode2 = listNode->flink;
         for(;listNode2 != NULL;  listNode2 = listNode2->flink) {
             if (listNode2->num < minNode->num) {
                 minNode = listNode2;
             }
-        }
-//Problem Lies here vvvvvvvvvvvv
-            temp->flink = listNode->flink;
-            temp->blink = listNode->blink;
-            listNode->blink = listNode2;
-            listNode->flink = listNode2->flink;
-            listNode2->flink = temp;
-            listNode2->blink = temp->blink;
+                       if (listNode->num > listNode2->num) {
+                               temp = listNode;
+                               listNode = listNode2;
+                               temp->flink = listNode2->flink;
+                               listNode->flink = temp;
+                               listNode->blink = temp->blink;
+                               listNode2 = temp;
+                               listNode2->blink = listNode;
+                               if (head == listNode2)
+                                       head = listNode;
+                       }
         printf("min: %d\n", minNode->num);
         }
     }
+}

yes! thank you. I knew I was on the right track I just couldnt figure out the order of changing the pointers
I should say, its in order but not all the nodes are not there after the sort.

Collectives™ on Stack Overflow

doubly linked list in C sorting problems

4 Answers 4

2 Comments

1 Comment

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

1 Comment

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related