1. ## 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      *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

Where I access the linked list via a single-pointer
void mergeSort(dll_t *dll)

If you compare the two mergesort functions

Original:
Code:
```void mergeSort(struct node **head)
{
// base case: 0 or 1 node
return;

// split head into 'a' and 'b' sublists
struct node *a = *head, *b = NULL;

// recursively sort the sub-lists
mergeSort(&a);
mergeSort(&b);

// merge the two sorted lists together
}```
Attempted port:
Code:
```void mergeSort(dll_t *dll)
{
// base case: 0 or 1 node
{
return;
}
else
{
// split list into 'a' and 'b' sublists
node_t *a = dll->head, *b = NULL;

// sort the sub-lists
mergeSort_sublists(&a);
mergeSort_sublists(&b);

// merge the two sorted lists together

} // else (more than 1 node)
} //mergeSort```
I try to set *head using
Code:
```node_t **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. 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. 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.

4. 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
add it to tail of list_a
if list_inout is not empty
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
add it to tail of list_inout
else if list_a is empty
add it to tail of list_inout
else
add it to tail of list_inout
else
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. 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. 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      *tail;
};
typedef struct dll dll_t;

// function to add a node at the tail of a doubly linked list
{
node_t *node = malloc(sizeof(*node));
if (node == NULL)
{
getchar();
}

node->record = *record;
node->next = NULL;
node->prev = NULL;

if ( dll->tail == NULL )
{
// first node
}
else
{
// insert additional nodes at the tail
node_t  *curr = dll->tail;

dll->tail = node;
node->prev = curr;
curr->next = node;
}

// function to remove head node from list
{

// walk through list
while (curr != NULL)
{
// handle first item
if (curr->prev == NULL)
{
if (curr->next == NULL)
{
// only item?
dll->tail = NULL;
}
else
{
// more items?
}
free(curr);
}
// Only process a single node
break;
}

// Helper function to print nodes of a doubly linked list
void printDLL_fwd(dll_t *dll)
{
printf("Forward\n");

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

// Remove head record from original list

} // split

void merge(dll_t *original_list, dll_t *list_a, dll_t *list_b)
{
// Initialise record
record_t record;

{
// if list_b is empty
{

// remove record from list_a

}
// if list_a is empty
{

// remove record from list_b

}
else
// list_a and list_b both have records
{
{

// remove record from list_a

}
else
{

// remove record from list_b

}
} // 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;

dll_t list_b;

// while the original_list is not empty - split items into two lists: list_a and list_b;
{
// 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
{
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;
record_t record;
record.data = 0;

for (int i = 0; i < n; i++)
{
record.data = keys[i];
}

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. Looking really swish! Are you happy with it?

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) {
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)
{
if(curr == NULL) {
return NULL;
} else if(curr->next == NULL) {
dll->tail = NULL;
} else {
}
curr->next = NULL;
curr->prev = NULL;
return curr;
Then you can chain things together a lot more cleanly:

Code:
```    while(dll->head != NULL) {
}
}```
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) {